↓ Skip to main content
Side Effects
  1. posts/

EnumArray - A Practical Mapping Trick Without Paying Hash-Map Tax

··
Notes Cpp
Table of Contents

EnumArray: a map from enum to data without the hash map
#

I often have an enum and want to map each enumerator to some data. The usual answer is a hash map:

std::unordered_map<Unit, const char*> unitNames {
    { Unit::Grams, "g" },
    { Unit::Meters, "m" },
    { Unit::Liters, "l" },
    { Unit::Items, "pcs" },
};

It works and it reads well. For a table of four items it is also wasteful. It hashes, it follows pointers, it has no locality, it may allocate, and the compiler does not know its size.

An enum is an integer, and an integer is a good array index. So I keep the map interface and back it with std::array. The array needs its size, and the simplest source is an extra enumerator:

enum class Unit {
    Grams,
    Meters,
    Liters,
    Items,

    Count
};

You know this from old C code. It is boring and needs no metaprogramming.

The container:

template<typename Enum, typename T>
class EnumArray {
public:
    EnumArray(std::initializer_list<std::pair<Enum, T>>&& values) {
        for (auto&& [key, val] : values)
            data[std::to_underlying(key)] = val;
    }

    T& operator[](Enum key) {
        return data[std::to_underlying(key)];
    }

    const T& operator[](Enum key) const {
        return data[std::to_underlying(key)];
    }

private:
    static constexpr size_t N = std::to_underlying(Enum::Count);
    std::array<T, N> data{};
};

Usage looks the same as with a map:

EnumArray<Unit, const char*> unitNames {
    { Unit::Grams, "g" },
    { Unit::Meters, "m" },
    { Unit::Liters, "l" },
    { Unit::Items, "pcs" },
};

std::cout << unitNames[Unit::Items] << "\n";  // pcs

What you get
#

The data is compact and cache-friendly. There are no buckets and no load factors. Lookup is O(1) with no collisions and no custom hash function.

The size is known at compile time. There are no hidden allocations, no reserve(), no resizing, and almost everything can be constexpr.

Where I use it
#

An image processing pipeline:

enum class FilterId {
    Gaussian,
    Median,
    Sobel,
    Sharpen,
    Count
};

EnumArray<FilterId, FilterConfig> filters {
    { FilterId::Gaussian, {3, 1.0f} },
    { FilterId::Median,   {5} },
    { FilterId::Sobel,    {1} },
    { FilterId::Sharpen,  {2} }
};

No heap use during processing.

Log levels per channel:

enum class LogChannel {
    Network,
    Storage,
    Rendering,
    Physics,
    Count
};

EnumArray<LogChannel, Level> logLevels {
    { LogChannel::Network,  Level::Info },
    { LogChannel::Storage,  Level::Warning },
    { LogChannel::Rendering,Level::Debug },
    { LogChannel::Physics,  Level::Error },
};

Material constants in a simulation:

enum class Material {
    Steel,
    Concrete,
    Glass,
    Wood,
    Count
};

EnumArray<Material, float> density {
    { Material::Steel,     7850.f },
    { Material::Concrete,  2400.f },
    { Material::Glass,     2500.f },
    { Material::Wood,       600.f },
};

Limits
#

The enum must be contiguous and start at zero. This breaks:

enum class Type {
    A = 10,
    B = 11,
    C = 512,
    Count
};

The array would have 512 entries, most of them unused.

T must be default-constructible, because the array is always full size. EnumArray<Enum, NonDefault> does not compile for this type:

struct NonDefault {
    NonDefault(int);
};

Missing entries get a default value.

EnumArray<Unit, const char*> names {
    { Unit::Grams, "g" },
    { Unit::Liters, "l" }
};

names[Unit::Meters] == nullptr   // default value

Whether that is fine depends on the code.

Duplicate initializers overwrite silently.

EnumArray<Unit, int> values {
    { Unit::Grams, 1 },
    { Unit::Grams, 20 },   // overwrites silently
};

Hash maps do the same, but with an array it is easier to slip.

An out-of-range enum value is undefined behavior.

Unit x = static_cast<Unit>(1000);
names[x];

This indexes outside the array. Add your own check if you need protection.

Variants
#

Store std::optional<T> to avoid default construction:

std::array<std::optional<T>, N> data;

Initialize at compile time:

constexpr EnumArray<Unit, std::string_view> names = {
    { Unit::Grams,  "g" },
    { Unit::Meters, "m" },
    { Unit::Liters, "l" },
    { Unit::Items,  "pcs" },
};

Add a bounds-checked accessor for code where correctness beats speed:

T& at(Enum key) {
    const auto idx = std::to_underlying(key);
    if (idx >= N) throw std::out_of_range("EnumArray");
    return data[idx];
}

EnumArray or a map
#

Use EnumArray when the enum is small and fixed, lookups are frequent, locality matters, you want constexpr initialization, nothing is inserted at runtime, and default construction is acceptable.

Use unordered_map or map when the enum values are not contiguous, you insert or remove at runtime, the dictionary is sparse, or another subsystem controls the enum and may change it.

I use this pattern often. For an enum that is a closed set known at compile time, it gives map syntax with array speed.

Related

Skrypt

·