Find the smallest integer type that can count up to N

Question

I would like a solution in C++03 that would allow me to select a type that is capable of holding integers up to N while remaining the smallest as possible.

basically I would just have to call a metafunction like that:

meta::tight_int<UpToN>::type n(0);  // UpToN a size_t from a template. or static const

for a variable declaration. Using boost::mpl is kind-of OK because I understand it, however I don't have it in my project, so I will have to convert your intent into my own meta library.

if you have a problem with signed/unsigned, consider only unsigned.

some invariants:

static_assert(meta::is_same<meta::tight_int<255>::type, uint8_t>::value, "")
static_assert(meta::is_same<meta::tight_int<256>::type, uint16_t>::value, "")
static_assert(meta::is_same<meta::tight_int<65536>::type, uint32_t>::value, "")

you get the idea :)

Answer 1

You could try something like this. The UpToN type is a template parameter here, but you could just change it to size_t. I did this because unsigned long long might be larger than size_t. For simplicity, this version only generates unsigned types.

This metaprogram iterates through a list unsigned integer types, casting upto_n to the candidate type (Try_t), then back to upto_n's type (Max_t) and checks this for equality with the original upto_n.

If the cast preserves this equality and Try_t's size is smaller or equal to the size of Best_t, then iteration continues with Try_t replacing Best_t.

The unsigned char specializations terminate iteration through candidate types.

#include <iostream>

template <typename T> struct next_t {};
template <> struct next_t<unsigned long long> { typedef unsigned long type; };
template <> struct next_t<unsigned long>      { typedef unsigned int type; };
template <> struct next_t<unsigned int>       { typedef unsigned short type; };
template <> struct next_t<unsigned short>     { typedef unsigned char type; };

template <typename Max_t, Max_t upto_n, typename Best_t=Max_t, typename Try_t=unsigned long long, bool try_is_better = (sizeof(Try_t) <= sizeof(Best_t) && upto_n == Max_t(Try_t(upto_n)))>
struct tight_int {
    typedef typename tight_int<Max_t, upto_n, Best_t, typename next_t<Try_t>::type>::type type; 
};

template <typename Max_t, Max_t upto_n, typename Best_t, typename Try_t>
struct tight_int<Max_t, upto_n, Best_t, Try_t, true>  {
    typedef typename tight_int<Max_t, upto_n, Try_t, typename next_t<Try_t>::type>::type type; 
};

template <typename Max_t, Max_t upto_n, typename Best_t>
struct tight_int<Max_t, upto_n, Best_t, unsigned char, true>  {
    typedef unsigned char type; 
};

template <typename Max_t, Max_t upto_n, typename Best_t>
struct tight_int<Max_t, upto_n, Best_t, unsigned char, false> {
    typedef Best_t type; 
};

int main() {
    typedef tight_int<size_t, 255>::type tight_255_t;
    typedef tight_int<size_t, 256>::type tight_256_t;
    typedef tight_int<size_t, 65535>::type tight_65535_t;
    typedef tight_int<size_t, 65536>::type tight_65536_t;
    std::cout << "255   : " << sizeof(tight_255_t) << std::endl;
    std::cout << "256   : " << sizeof(tight_256_t) << std::endl;
    std::cout << "65535 : " << sizeof(tight_65535_t) << std::endl;
    std::cout << "65536 : " << sizeof(tight_65536_t) << std::endl;
}

This code uses the helper class next_t to reduce tight_int's specialization count. But tight_int still has 4 specializations (if we count the default definition).

We can cut the specialization count in half by introducing a helper class which can select between the types Try_t and Best_t based on the bool parameter try_is_better. The result is passed to the next iteration's Best_t. This change will leave us with the minimum specialization count: The default definition (handling all unspecialized types) and an iteration-terminating specialization handing unsigned char. Unfortunately, this kind of optimization impacts readability and tends to obscure the mechanisms underlying a metaprogram.

For the version below the new helper class type_sel replaces tight_int's specializations for try_is_better true and false. You might notice that template parameter list syntax is really starting to get out of control:

template <typename T> struct next_t {};
template <> struct next_t<unsigned long long> { typedef unsigned long type; };
template <> struct next_t<unsigned long>      { typedef unsigned int type; };
template <> struct next_t<unsigned int>       { typedef unsigned short type; };
template <> struct next_t<unsigned short>     { typedef unsigned char type; };

// helper class type_sel which selects one of two types based on a static bool
template <bool, typename True_t, typename False_t>
struct type_sel                         { typedef True_t  type; };
template <typename True_t, typename False_t>
struct type_sel<false, True_t, False_t> { typedef False_t type; };

// default definition of tight_int, handling all Try_t except unsigned char
template <typename Max_t, Max_t upto_n, typename Best_t = Max_t,
    typename Try_t = unsigned long long,
    bool try_is_better=(sizeof(Try_t)<=sizeof(Best_t) && upto_n==Max_t(Try_t(upto_n)))>
struct tight_int {
    typedef typename tight_int<Max_t, upto_n,
        typename type_sel<try_is_better, Try_t, Best_t>::type,
        typename next_t<Try_t>::type>::type type; 
};
// unsigned char specialization of tight_int terminates iteration through types
template <typename Max_t, Max_t upto_n, typename Best_t, bool try_is_better>
struct tight_int<Max_t, upto_n, Best_t, unsigned char, try_is_better>  {
    typedef typename type_sel<try_is_better, unsigned char, Best_t>::type type;
};

One thing I still don't like is the lame way the type list is implemented (as next_t). I don't like how each type needs to be specified twice: as a specialized template parameter and also as the next_type::type. Instead, we could use a class which nests itself to form a list of types. Below, Try_t is replaced by Trylist_t. The new helper class tpair nests itself in a template type parameter to form the iterated list of types. A type list can now be defined with a single line like:

tpair<unsigned long long, tpair<unsigned long, tpair<unsigned int, ... > >

And this type list class can be used elsewhere to build lists of other kinds of types. (Keep in mind that we are spec-bound to C++03, so variadic template parameter lists are not available.)

So here is the next version, with a tpair type list. I didn't bother with line breaks in template parameter lists because it's all unreadable now anyway:

template <typename My_t, typename Next_t=void>
struct tpair { typedef My_t type; typedef Next_t next_tpair; } ;

template <bool, typename True_t, typename False_t>
struct type_sel                         { typedef True_t  type; };
template <typename True_t, typename False_t>
struct type_sel<false, True_t, False_t> { typedef False_t type; };

template <typename Max_t, Max_t upto_n, typename Best_t = Max_t, typename Trylist_t = tpair<unsigned long long, tpair<unsigned long, tpair<unsigned int, tpair<unsigned short, tpair<unsigned char> > > > >, bool try_is_better=(sizeof(Trylist_t::type)<=sizeof(Best_t) && upto_n==Max_t((typename Trylist_t::type) upto_n))>
struct tight_int {
    typedef typename tight_int<Max_t, upto_n, typename type_sel<try_is_better, typename Trylist_t::type, Best_t>::type, typename Trylist_t::next_tpair>::type type; 
};

template <typename Max_t, Max_t upto_n, typename Best_t, bool try_is_better>
struct tight_int<Max_t, upto_n, Best_t, typename tpair<unsigned char>, try_is_better>  {
    typedef typename type_sel<try_is_better, unsigned char, Best_t>::type type;
};

Answer 2

Ok, this is not a complete answer, I still post it for the sake of:

• helping future googlers understanding how boost works for this feature.
• maybe give them an alternative to Christopher Oicles way.

This is the code I derived from the boost technique:

namespace detail
{
    template< int Category > struct UintLeastHelper {}; // default is empty

    //  specializatons: 1=u64, 2=u32, 3=u16, 4=u8,
    //  no specializations for 0 and 5: requests are errors
    template<> struct UintLeastHelper<1> { typedef u64 Least; };
    template<> struct UintLeastHelper<2> { typedef u32 Least; };
    template<> struct UintLeastHelper<3> { typedef u16 Least; };
    template<> struct UintLeastHelper<4> { typedef u8  Least; };
}

//! finds the type that is the smallest that can bear numbers up-to-and-containing MaxValue.
template< u64 MaxValue >
struct TightestUInt_T
{
    typedef typename detail::UintLeastHelper
    < 
        1 + // (MaxValue <= IntegerTraits<u64>::ConstMax_T::value) <- this is always true of course.
        (MaxValue <= IntegerTraits<u32>::ConstMax_T::value) +
        (MaxValue <= IntegerTraits<u16>::ConstMax_T::value) +
        (MaxValue <= IntegerTraits<u8>::ConstMax_T::value)
    >::Least  Value_T;
};

This passes the static_assert tests of the question OK.

As you can see, it is quite funny in the fact it uses a serie of additions from comparison results casted to int (0 or 1) to determine the category.
You also see it depends on some lower level utility, ConstMax_T. This is a replacement for numeric_limits that works in constant expressions. Boost has its own system that I also copied.

basically it ends up like that:

template <class T>
class IntegerTraits
{
public:
    typename typedef TIsIntegral<T>::ValueType_t IsIntegral_T;
};

namespace detail
{
    template <class T, T MinVal, T MaxVal>
    class IntegerTraitsBase
    {
    public:
        typedef TIntegralConstant<bool, true>::ValueType_t IsIntegral_T;
        typedef TIntegralConstant<T, MinVal> ConstMin_T;
        typedef TIntegralConstant<T, MaxVal> ConstMax_T;
    };
}

template<>
class IntegerTraits<char>
    : public detail::IntegerTraitsBase<char, CHAR_MIN, CHAR_MAX>
{ };

template<>
class IntegerTraits<signed char>
    : public detail::IntegerTraitsBase<signed char, SCHAR_MIN, SCHAR_MAX>
{ };
// etc. for next types

you see it ends up using again one even lower level utility TIntegralConstant that is realtively easy to do. So this answer uses much much more code than Christopher's answer, and it can't be easily pasted in ideone. But still I post it to show how I did it in the end. The reason is that it helps extends my own meta library, by dissociating basic functions.

enjoy