找到可以数到N的最小整数类型

问题描述 投票：0回答：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, "")

你明白了:)

c++ metaprogramming c++03
3个回答
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 来减少ight_int 的专业化计数。但tight_int 仍然有 4 个特化（如果我们算上默认定义）。

我们可以通过引入一个辅助类来将专业化数量减少一半，该辅助类可以根据 bool 参数 try_is_better 在 Try_t 和 Best_t 类型之间进行选择。结果被传递给下一次迭代的Best_t。此更改将为我们留下最小的专业化计数：默认定义（处理所有非专业化类型）和处理 unsigned char 的迭代终止专业化。不幸的是，这种优化会影响可读性，并且往往会掩盖元程序背后的机制。

对于下面的版本，新的帮助器类 type_sel 取代了ight_int 对 try_is_better true 和 false 的专门化。您可能会注意到模板参数列表语法确实开始失控：

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;
};
0
投票

好吧，这不是一个完整的答案，我仍然发布它是为了：

  • 帮助未来的谷歌员工了解Boost如何用于此功能。
  • 也许给他们提供克里斯托弗·奥克斯方式的替代方案。

这是我从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
测试 OK。

正如你所看到的，这很有趣，因为它使用了一系列将比较结果转换为 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 中。但我仍然发布它来展示我最终是如何做到的。原因是它通过分离基本功能来帮助扩展我自己的元库。

享受

0
投票

有点晚了，但这就是我的方法：

#include <cstdint>
#include <utility>
#include <type_traits>

template<std::size_t N>
constexpr auto bits_needed()
{
    auto n = N;
    std::size_t number_of_bits{0ul};
    while( n > 0 )
    {
        n >>= 1;
        number_of_bits++;
    }
    return number_of_bits;
}

template<std::size_t N>
using smallest_type = std::conditional_t<bits_needed<N>() <= 8*sizeof(std::uint8_t), std::uint8_t,
    std::conditional_t<bits_needed<N>() <= 8*sizeof(std::uint16_t), std::uint16_t,
    std::conditional_t<bits_needed<N>() <= 8*sizeof(std::uint32_t), std::uint32_t, std::uint64_t>>>;

int main()
{
    static_assert(std::is_same_v<std::uint8_t,smallest_type<255>>);
    static_assert(std::is_same_v<std::uint16_t,smallest_type<256>>);
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.