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.

What do you mean by a _constexpr container_? Here is a list of all the [containers](http://en.cppreference.com/w/cpp/container). — Ron, Mar 18 '18 at 21:19
Ok, but what about `int array[const N]`? I solved one problem where I made a lot of matrices at compile time. The only possible options for K and V are `string` and `int`. — InFamous X, Mar 18 '18 at 21:20
So it sounds like you are looking for something like `std::array`, a `constexpr` function to create pre-sorted from an initializer list, and a few extra functions to do lookups based on a particular field of the elements (same field used for sorting)? — Ben Voigt, Mar 18 '18 at 21:24
@InFamousX Why assemble matrices at compile time ? Loading from a file is much more natural. — llllllllll, Mar 18 '18 at 21:25
@liliscent: If there is a recursive definition, generation in code is quite natural. — Ben Voigt, Mar 18 '18 at 21:26
@liliscent Because I study c++ and that was a problem from a book. — InFamous X, Mar 18 '18 at 21:27
Closely related: https://stackoverflow.com/q/19559808/103167 — Ben Voigt, Mar 18 '18 at 21:28
@BenVoigt Using compile time computation to compute data (matrix) is really crazy IMO. I'd rather compute them in Python and copy it to source code. — llllllllll, Mar 18 '18 at 21:28
@liliscent: That only means you like python better than C++. It doesn't mean the rest of the world needs to do it the same way. — Ben Voigt, Mar 18 '18 at 21:29
@liliscent, You can accomplish a lot just by sticking `constexpr` in front of functions. Compile-time calculations aren't as crazy as they used to be. — chris, Mar 18 '18 at 21:40
I also enjoy template programming, but here my point is the computation of pure data, like matrix. I don't think it worth slowing down compilation with no realistic gain. Loading data from file is the correct choice. @chris — llllllllll, Mar 18 '18 at 21:49
@liliscent If you have a small LUT with a recursive definition as Ben mentioned, it can be a self-documenting and very clear option. You are entitled to your opinion but "there is no purpose for compile-time arrays" is a stretch. — miradulo, Mar 18 '18 at 22:11

Öö Tiib · Answer 1 · 2019-10-25T07:28:36.880

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.

I haven't had any problems using std::array in constexpr functions with any number of elements. That would include thinks like make_sorted_array which would allow one to pass elements as parameter and return sorted array object. Even std::map like tree should be possible to implement using tuple as memory allocator. (never tried tuple allocator but basic idea seems to be workable for any constexpr stl like container) — Pauli Nieminen, Oct 24 '19 at 19:31
Any size limit is entirely implementation specific - remember that constexpr is a hint, not a directive. The compiler may choose not to actually execute it at compile time, for any reason. — Richard1403832, Dec 14 '22 at 12:07

What are constexpr containers in C++17?

1 Answers1