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 :)
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;
};