Find the smallest integer type that can count up to N
I needed a solution in C ++ 03 that would allow me to choose a type that is capable of holding integers up to N
while staying as small as possible.
Basically, I would just need to call the meta-focus like this:
meta::tight_int<UpToN>::type n(0); // UpToN a size_t from a template. or static const
to declare a variable. The usage boost::mpl
is kind - OK because I understand it, however I don't have it in my project, so I'll have to convert your intent to my own meta-library.
if you have a / unsigned problem, only consider unsigned ones.
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 :)
source to share
You can try something like this. The UpToN type here is a template parameter, but you can simply change it to size_t. I did this because unsigned long long can be larger than size_t. For simplicity, this version only generates unsigned types.
This metaprogram iterates over unsigned integers, casting upto_n to candidate type (Try_t), then back to upto_n type (Max_t), and tests it for equality with the original upto_n.
If the cast retains this equality, and the size of Try_t is less than or equal to the size of Best_t, then iteration continues with Try_t replacing Best_t.
Unsigned char specializations end up iterating over 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 next_t helper class to decrease the value of the round_int specialization. But tight_int still has 4 specializations (if we calculate the default definition).
We can cut the specialization cost in half by introducing a helper class that can choose between Try_t and Best_t based on the bool try_is_better parameter. The result is passed to the next Best_t iteration. This change will leave us with a minimal amount of specialization: a default definition (handling all non-specialized types) and a trailing specialization passing in an unsigned char. Unfortunately, such optimizations affect readability and tend to hide the underlying mechanisms of the metaprogram.
For the version below, the new helper class type_sel replaces the tight_int specializations for try_is_better true and false. You may notice that the syntax of the template parameter list is really starting to get out of hand:
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 of implementing a list of types (like next_t). I don't like how each type has to be specified twice: as a specialized template parameter and also as type_type :: type. Instead, we could use a class that nests to form a list of types. Below, Try_t is replaced by Trylist_t. The new tpair of the helper class is in the template type parameter to form a repeated type list. The type list can now be defined with one line, for example:
tpair<unsigned long long, tpair<unsigned long, tpair<unsigned int, ... > >
And this type list class can be used elsewhere to create lists of other types of types. (Keep in mind that we're tied to C ++ 03, so template parameter variable lists are not available.)
So, here is the next version with type tpair. I didn't bother with line breaks in template parameter lists, because now everything is unreadable:
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;
};
source to share
Ok, this is not a complete answer, I posted it for:
- helps future googlers understand how amplification works for this feature.
- could give them an alternative to the path of Christopher Oycles.
This is the code I got from the boost method:
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
OK question test .
As you can see, it's kind of funny in that it uses a series of padding from non-int (0 or 1) comparison results to determine the category.
You will also see that it depends on some utilities lower level ConstMax_T
. It is a replacement for numeric_limits
which works in constant expressions. Boost has its own system which I copied as well.
it basically ends up like this:
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 can see that it is again using another smaller utility TIntegralConstant
that is really easy to do. Thus, this answer uses a lot more code than Christopher and cannot be easily pasted into an ideal. But still I post it to show how I did it at the end. The reason is that it helps to extend my own meta-library by separating the core functionality.
enjoy
source to share