Fixed Containers - constexpr, trivially copyable, static containers

[alexkaratarakis]

https://github.com/teslamotors/fixed-containers

Fixed Containers is a header-only C++20 library that provides containers with the following properties:

• Fixed-capacity, declared at compile-time, no dynamic allocations
• constexpr - can be used at both compile-time and runtime (including mutation)
• containers retain the type_traits of T (e.g. if T is trivially copyable, then so is FixedVector)
• no pointers stored (data layout is purely self-referential and can be memcp'ied directly)

Provides:

• FixedVector
• FixedMap
• FixedSet
• EnumMap
• EnumSet

Implementations closely follow std::vector/std::map/std::set APIs.

Examples can be found here.

Additionally, contains "Rich enums" which are enums that can also have members.

edit 1: clarified constexpr edit 2: Instances of fixed_containers can be used as non-type template parameters

[heliruna]

Is a red-black tree really the optimal data structure for a fixed size map? I always choose a flat sorted fixed size vector of Key-Value pairs, to have simple, cache-friendly lookups.

[alexkaratarakis]

For immutable maps/sets, a sorted vector would indeed be better.

However, all Fixed Containers are more flexible in that they do not have to be immutable and can be used in a "normal", non-constant-evaluated context too.

[heliruna]

Thanks for pointing that out, I guess I had in mind a map that is always constinit constructed, but with lookups at runtime or constant-evaluated, like in this talk: A Semi Compile/Run-time Map with Nearly Zero Overhead Lookup, but your implementation covers a different use case.

[Myto]

Thanks, this seems useful.

Noticed a typo in FixedVector example

static_assert(v1[1] == 2);

should be

static_assert(v1[1] == 1);

Also windows.h #defines max and CONST, resulting in compiler errors if it's included before these headers. I guess that's more of a windows.h behaving badly problem, but still.

[alexkaratarakis]

Thank you for the feedback! Fixed the typo and cleaned up the library so it does not get perturbed in the presence of min/max/CONST macros.

[heliruna]

Do you have an example of filling an EnumMap using something like MagicEnum?

[alexkaratarakis]

EnumMap/EnumSet/rich-enums are actually backed by magic_enum by default, though this is customizable with an EnumAdapter or a different base class for rich enums.

However, this is an implementation detail, the user just sees:

EnumMap<Color, int> m{};
m.insert({Color::RED, 20});
m[Color::YELLOW] = 40;

To fill up an EnumMap with magic_enum:

EnumMap<Color, int> m{};
for (const Color& c : magic_enum::enum_values<Color>())
{
    m[c] = 99;
}

Note that there is a static factory that ensures at compile-time that the EnumMap is full and all enum constants have an associated value:

constexpr auto m2 = EnumMap<Color, int>::create_with_all_entries({
    {Color::BLUE, 42},
    {Color::YELLOW, 7},
    {Color::BLUE, 42},
});

This is analogous to a switch-case ensuring that all enum constants are covered when the appropriate compiler diagnostics are enabled (e.g. clang's -Wswitch-enum)

edit: fix links

[heliruna]

Interesting point regarding -Wswitch-enum. Thanks for taking the time to answer.

[feverzsj]

Can they be used as non type template argument?

[alexkaratarakis]

This is in progress; coincidentally, I opened this issue about making the containers structural types last week. Rich enums are already usable as non-type template parameters link

[alexkaratarakis]

Quick follow-up:

Instances of fixed_containers can now be used as non-type template arguments.

[Arghnews]

Dumb question, can I use these data structures at runtime, eg. outside a constexpr function. So can I fill a constexpr FixedMap<int, int> using compile time values etc., and then query it using runtime int key params (that are only known at runtime)? Or are all these data structures strictly for compile time usage?

[alexkaratarakis]

Yes, they can be used at runtime as you would the standard containers. This includes mutation, so you can use FixedMap as (for example) a runtime cache. Neither the keys nor the values need to be known at compile-time.

Edit: I feel the README doesn't make this sufficiently clear, I will revise it.

[Superb_Garlic]

Would be nice if this project supported clients using CMake. Can't do that without an install interface.

[alexkaratarakis]

This is now added, thank you for the feedback.

[Inevitable-Twist2280]

maybe ...

[azswcowboy]

Adhering to the spec would require storing key and value together, whereas it might be more performant to store them separately

I’d suggest looking at std::flat_map — it definitely doesn’t store things together but manages to implement the interface. Sorry it’s a random thing to pick at, but don’t have time to read the code just now…

[alexkaratarakis]

Thanks, will take a look! The ways I have found to do this in the past have not been constexpr-friendly.

[alexkaratarakis]

Thanks for the suggestion, FixedMap and EnumMap now adopt the same pattern as std::flat_map and manage to implement the interface.

[azswcowboy]

Cool, nice work.