What are constexpr containers in C++17?

Question

I want to make a class that has methods like std::map, but it should be sorted at compile time. Which constexpr containers are suited to store keys template<class K> and values template<class V>?

std::vector does not meet these requirements.

UPD: We found that std::array has a lot of constexpr methods. And it's enough for my problem to use std::array<std::pair<K, V> >. But the question holds.

Answer 1

Most C++ standard library containers are not useful as constexpr. AFAIK only first 64 bits of std::bitset and std::array (of any length) are fillable compile time.

Do not concentrate on such performance optimizations before the program itself is ready. Filling large std::array compile-time was not too hard in C++11 using variadic template functions.

Example of how to fill array of 4 ints (each representing one of 6 colors) compile time using variadic templates:

constexpr int ColorCount = 6;
constexpr int PositionCount = 4;

using Positions = std::array<int, PositionCount>;

template <int N>
struct PositionsFiller
{
    template <typename T, typename ...Tn>
    static constexpr Positions fill(T packed, Tn ...rest)
    {
        return PositionsFiller<N - 1>::fill(packed / ColorCount, packed % ColorCount, rest...);
    }
};

template <>
struct PositionsFiller<1>
{
    template <typename T, typename ...Tn>
    static constexpr Positions fill(T last, Tn ...rest)
    {
        return Positions{last, rest...};
    }
};

constexpr Positions pos666(PositionsFiller<PositionCount>::fill(666));

In C++17 same can be done with simple loop since requirements to constexpr are relaxed and there variadic templates are not needed:

constexpr int ColorCount = 6;
constexpr int PositionCount = 4;

using Positions = std::array<int, PositionCount>;

static constexpr Positions fillPositions(int packed)
{
    Positions ret{};
    for (Positions::size_type i = ret.size(); i > 0; --i)
    {
        ret[i-1] = packed % ColorCount;
        packed /= ColorCount;
    }
    return ret;
}

constexpr Positions pos666(fillPositions(666));

Note that doing complex preparations compile time can slow down compilations. That may be annoying when module is still under development. Better can be to fill usual mutable array at start of program and later to replace it with optimizations like compile-time filling.