CODEWITHSUNDEEP
c++c++11templates
Borph
Borph

Reputation: 933

Template: How to select smallest int type which holds n bits?

For an own implementation of std::bitset (std forbidden) I used uint_fast32_t, since it's faster on 64bit CPUs. A review remark was to save space for small sets, e.g. bitset<6> shouldn't use 8 bytes. The waste is even more if you consider alignment in a struct.

To use C++11 is fine. I would like to elegantly select:

as storage type in my class:

template<size_t Size>
struct BitSet {
    typedef <expression> StorageType;
    // an array of that storage type...
};

I can just think of rather clumsy helper templates, but maybe there is something more elegant in C++11.

Edit: to clarify: uint_fast8_t would be fine for the original class, the compiler may choose whatever is fast. Imagine Size==1000000. But it would be 64 bit on some machines, and when size matters in some use-cases, e.g. Size==4 it means 7 bytes would be wasted.

Upvotes: 2

Views: 1579

Answers (6)

Victor Bogado da Silva Lins
Victor Bogado da Silva Lins

Reputation: 1

Simple solution:

template<std::size_t MAX_VAL>
using min_unsigned_type = std::tuple_element_t<
    bit_width(MAX_VAL), // See bellow.
    std::tuple<
         std::uint8_t,
         std::uint16_t,
         std::uint32_t,
         std::uint64_t
>>;

This is simply using the bit_width, ie. the minimum number of bits that can fit the maximum value needed to index the std::tuple of all the types you want to use.

C++20 has a std::bit_width that is constexpr, but if needed it's easy to write your own version.

Upvotes: 0

Anonymous
Anonymous

Reputation: 18631

You can also make use of constexpr if if your compiler supports it - might be the easiest one to read. Example based on code from here:

template<size_t S>
static constexpr auto _findStorageType() {
    static_assert(S > 0, "Invalid storage size");

    if constexpr (S <= sizeof(uint8_t) * CHAR_BIT) return uint8_t{};
    else if constexpr (S <= sizeof(uint16_t) * CHAR_BIT) return uint16_t{};
    else if constexpr (S <= sizeof(uint32_t) * CHAR_BIT) return uint32_t{};
    else if constexpr (S <= sizeof(uint64_t) * CHAR_BIT) return uint64_t{};
    else return __uint128_t{};
}

Upvotes: 0

eerorika
eerorika

Reputation: 238401

You can use a recursive template class with a non-type template argument for the bit limit, and a member type alias for the corresponding integer type.

You don't need to write such template yourself though, Boost has you covered: boost::uint_t<N>::least (or boost::uint_t<N>::fast if you're not looking for the smallest, but fastest).

P.S. If you plan to implement the template yourself, and you want the smallest integer type (as per the question in the title), then you should use std::uint_leastN_t instead of uint_fastN_t or uintN_t. The former is not necessarily the smallest type, and the latter is not guaranteed to exist on all systems.

Furthermore uint_fast32_t is not guaranteed to be able to represent more bits than 32, so it is a rather poor choice for Size > 32. I would recommend uint_least64_t instead.

Upvotes: 1

balki
balki

Reputation: 27684

A verbose solution with less magic. Ref: https://gcc.godbolt.org/z/P2AGZ8

#include<cstdint>

namespace helper { namespace internal {

enum class Size {
    Uint8,
    Uint16,
    Uint32,
    UintFast32,
};

constexpr Size get_size(int s) {
    return (s <= 8 ) ? Size::Uint8:
           (s <= 16) ? Size::Uint16:
           (s <= 32) ? Size::Uint32: Size::UintFast32;
}

template<Size s>
struct FindTypeH;

template<>
struct FindTypeH<Size::Uint8> {
    using Type = std::uint8_t;
};

template<>
struct FindTypeH<Size::Uint16> {
    using Type = std::uint16_t;
};

template<>
struct FindTypeH<Size::Uint32> {
    using Type = std::uint32_t;
};

template<>
struct FindTypeH<Size::UintFast32> {
    using Type = std::uint_fast32_t;
};
}

template<int S>
struct FindType {
    using Type = typename internal::FindTypeH<internal::get_size(S)>::Type;
};
}

template<int S>
struct Myclass {
    using Type = typename helper::FindType<S>::Type;
};

Upvotes: 0

HolyBlackCat
HolyBlackCat

Reputation: 96579

Given the small selection of possible types, I'd just hardcode the conditions:

using StorageType = std::conditional_t<Size <=  8, uint8_t,
                    std::conditional_t<Size <= 16, uint16_t,
                    std::conditional_t<Size <= 32, uint32_t, uint_fast32_t>>>;

Alternatively, using a trick similar to one from @Caleth's answer:

using StorageType = std::tuple_element_t<(Size > 8) + (Size > 16) + (Size > 32),
                        std::tuple<uint8_t, uint16_t, uint32_t, uint_fast32_t>>;

Upvotes: 10

Caleth
Caleth

Reputation: 63019

With a helper

namespace detail {

    template <int overload>
    struct StorageType;

    template <>
    struct StorageType<0>{ using type = uint8_t; };

    template <>
    struct StorageType<1>{ using type = uint16_t; };

    template <>
    struct StorageType<2>{ using type = uint32_t; };

    template <>
    struct StorageType<3>{ using type = uint_fast32_t; };
}

We can then sum constexpr booleans

template<size_t Size>
struct BitSet {
    typedef typename detail::StorageType<(Size > 8) + (Size > 16) + (Size > 32)>::type StorageType;
    // an array of that storage type...
};

Upvotes: 4

Related Questions