logo标签列表

找到能够计数到N的最小整数类型

c++metaprogrammingc++03
3

我希望能够得到一种C++03的解决方案，使我能够选择一个类型，该类型能够容纳整数，最大值为N，同时保持尽可能小。

基本上，我只需调用这样的元函数：

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

关于变量声明。

使用boost::mpl有点可行，因为我理解它，但是我的项目中没有它，所以我需要将你的意图转换成我自己的元库。

如果你在有符号/无符号方面存在问题，请只考虑无符号。

一些不变量:

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, "")

你能理解这个想法 :)
编写自己的 std::conditional 版本，结合 <climits> 中适当的宏。请注意，uint8_t 等是 C++11 的内容，因为 C++03 使用的是 C89 标准库。 - T.C.
2
请查看http://www.boost.org/doc/libs/develop/libs/integer/doc/html/index.html，特别是http://www.boost.org/doc/libs/develop/libs/integer/doc/html/boost_integer/integer.html。 - Anycorn
如果这对您有用，我会将其发布为答案。 - Anycorn
1
类似于https://dev59.com/vmw05IYBdhLWcg3wxkmr。 - jcoder
1
@jcoder 谢谢。我看到你是提问者，所以你记得这个问题的存在。当我搜索时，我使用的关键词没有找到你的问题。那里有很好的答案，比如Maxim的答案。最近stackoverflow似乎真的烧毁了。 - v.oddou
显示剩余3条评论
2个回答
1
你可以尝试这样做。UpToN类型在此处作为模板参数，但您可以将其更改为size_t。我这样做是因为unsigned long long可能比size_t更大。为了简单起见，此版本仅生成无符号类型。
此元编程迭代通过无符号整数类型列表，将upto_n转换为候选类型（Try_t），然后再次转换为upto_n的类型（Max_t），并检查它是否与原始upto_n相等。
如果强制转换保留此等式并且Try_t的大小小于或等于Best_t的大小，则使用Try_t替换Best_t继续迭代。 unsigned char特殊化通过候选类型终止迭代。
#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;
}

这段代码使用辅助类next_t来减少tight_int的特化次数。但是，如果计算默认定义，则tight_int仍有4个特化（）。
我们可以通过引入一个辅助类来选择基于布尔参数try_is_better的类型Try_t和Best_t之间的类型，从而将特化计数减半。结果传递给下一次迭代的Best_t。这种改变将使我们保留最少的特化计数：默认定义（处理所有未特化的类型）和一个处理unsigned char的迭代终止特化。不幸的是，这种优化会影响可读性，并且往往会掩盖元编程的底层机制。
对于以下版本，新的辅助类type_sel替换了try_is_better为true和false的tight_int的特化。您可能会注意到，模板参数列表语法确实开始失去控制：
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;
};

我仍然不喜欢类型列表的实现方式（作为next_t）。我不喜欢每个类型都需要两次指定：一次作为特化的模板参数，一次作为next_type::type。相反，我们可以使用一个嵌套自身以形成类型列表的类。下面，Try_t被Trylist_t替换。新的辅助类tpair嵌套在模板类型参数中，以形成迭代的类型列表。现在可以用单行代码定义类型列表：

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

这种类型列表类可以在其他地方用于构建其他类型的列表。(请记住，我们被绑定到C++03规范，因此不支持变参模板参数列表。)
以下是带有tpair类型列表的下一个版本。我没有在模板参数列表中添加换行符，因为现在它已经无法阅读了。
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;
};
真棒。证明它的工作：http://ideone.com/rioQUr，而且没有使用boost :) \o/ 这是Oicles先生接受的答案。 - v.oddou
0

好的，这不是一个完整的答案，但我还是发表它是为了：

  • 帮助未来的谷歌用户理解boost在这个功能中的工作原理。
  • 也许给他们提供一个Christopher Oicles方法的替代方案。

这是我从boost技术中得出的代码：

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

这通过了问题的static_assert测试。

正如您所看到的，它非常有趣，因为它使用一系列从转换为int（0或1）的比较结果中添加来确定类别。
您还可以看到它依赖于一些较低级别的实用程序ConstMax_T。这是numeric_limits的替代品，可在常量表达式中工作。Boost有自己的系统，我也复制了它。

基本上就像这样：

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

你会发现它最终使用了一个更低级别的实用程序TIntegralConstant，这相对容易做到。因此，这个答案使用了比Christopher的答案更多的代码，并且不能轻松地粘贴到ideone中。但我仍然发布它来展示我最终是如何做到的。原因是它有助于扩展我的元库，通过分离基本函数。

享受吧！

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接