Effective bidirectional scoped enum mapping

Question

Having:

enum class A : int {
    FirstA,
    SecondA,
    InvalidB
};

enum class B : int {
    FirstB,
    SecondB,
    InvalidB
};

How to enable something like this?

B b = mapper[A::FirstA];
A a = mapper[B::SecondB];

One possible solution is to create a Mapper template class, which allows to specify the mapping via initializer list in the constructor, something like:

Mapper<A, B> mapper(
     {
     {A::FirstA,   B::SecondB},
     {A::SecondA,  B::FirstB}
     },
     {A::InvalidA, B::InvalidB} // this is for conversions, where no mapping is specified
);

But internally this will require compromises - either two maps (from A to B and from B to A) or one map, e.g. from A to B and a linear search for B to A conversions).

Is it possible to implement this in standard C++14 so, that:

no double containers are used
lookup performance is equally good in both directions
defining and using the mapping is relatively straightforward (internal implementation does not need to be)

With the requirements, that:

it is not identity mapping (i.e. the values from A are not mapped to the same underlying values of B
underlying types of A and B may differ
mapping is known during compile-time

?

Why do you need to avoid using two maps? It only consumes 2 times as much memory as 1 map, which is not much assume they're enum value (have the size of about an int), and especially you don't care too much about the internal implementation? — user202729, Mar 26 '19 at 15:47
@user202729, this is in the embedded domain, and needed for mapping between not only two enums, but more, so having the `2 * [mappings_for_one_enum * 2 * int_size]` is relevant. — nVxx, Mar 26 '19 at 15:52
@user202729 if by `constant-time` you mean `compile-time`, then yes. — nVxx, Mar 26 '19 at 15:53
Is the integer value of the enums guaranteed to be consecutive? — user202729, Mar 26 '19 at 15:53
@Timo, well, that's the solution I also proposed in the question, but it has caveats. — nVxx, Mar 26 '19 at 15:54
Maybe [boost::bimap](https://www.boost.org/doc/libs/1_66_0/libs/bimap/doc/html/index.html) — NathanOliver, Mar 26 '19 at 15:56
@user202729, yes, also can be guaranteed that the values start from `0` - the enums are generated from specification document, so it's possible to ensure that. — nVxx, Mar 26 '19 at 15:57
@NathanOliver, I also stumbled upon `boost::bimap` when searching for a solution first, but unfortunately boost is not an option, should be by the means of standard C++. — nVxx, Mar 26 '19 at 15:58
If the two enums have the same value you can just cast between them — Alan Birtles, Mar 26 '19 at 16:00
In that case you can either use some template metaprogramming so the mapper will consume O(1) memory, or array lookup (they will consume O(N) memory where N = number of enum items) Either way would have O(1) lookup. — user202729, Mar 26 '19 at 16:02
Then please provide a [mcve], your example can be implemented with a cast — Alan Birtles, Mar 26 '19 at 16:04
I am tempted to close for duplicate with https://stackoverflow.com/questions/21760343/is-there-a-more-efficient-implementation-for-a-bidirectional-map — Pixelchemist, Mar 26 '19 at 16:12
@Pixelchemist In this case the values are enums in a range and known in const time so more efficient solution exists. — user202729, Mar 26 '19 at 16:17
@Pixelchemist, missed that other question when searching, but although the answer is accepted, it doesn't address the doble-map issue, though it improves the original solution in the other post... — nVxx, Mar 26 '19 at 16:17
To be perfectly clear: Is compile-time lookup sufficient? Or is it required that the mapping can also be specified at runtime? — Max Langhof, Mar 26 '19 at 16:29
@MaxLanghof, updated the question (mentioned in the comment earlier) - the mapping is known at compile-time. — nVxx, Mar 26 '19 at 16:31

score 2 · Answer 1 · answered Mar 26 '19 at 16:37

You can do this pretty easily using function templates and full specialization. You make the primary template return the invalid case and then the specializations would return the mappings that you want.

If you have

template<A>
B mapper() { return B::InvalidB; }
template<B>
A mapper() { return A::InvalidA; }

then you can add all of the mapped values like

template<>
B mapper<A::FirstA>() { return B::SecondB; }
template<>
B mapper<A::SecondA>() { return B::FirstB; }
template<>
A mapper<B::FirstB>() { return A::SecondA; }
template<>
A mapper<B::SecondB>() { return A::FirstA; }

and then you would call it like

B b = mapper<A::FirstA>();
A a = mapper<B::SecondB>();

This leaves you with no containers at all. You can even make some macros to make this easier like

#define MAKE_ENUM_MAP(from, to) \
template<from> \
auto mapper() { return to::Invalid; } \
template<to> \
auto mapper() { return from::Invalid; }


#define ADD_MAPPING(from_value, to_value) \
template<> \
auto mapper<from_value>() { return to_value; } \
template<> \
auto mapper<to_value>() { return from_value; }

and then you would use them like

MAKE_ENUM_MAP(A, B)
ADD_MAPPING(A::FirstA, B::SecondB)
ADD_MAPPING(A::SecondA, B::FirstB)

to generate all the code for you. The above version uses a single enum value of Invalid for the invalid case of the mappings. If you don't want that you can add to the macro what from and to values to use for invalid mappings like

#define MAKE_ENUM_MAP(from, from_value, to, to_value) \
template<from> \
auto mapper() { return to_value; } \
template<to> \
auto mapper() { return from_value; }

and you would call it like

MAKE_ENUM_MAP(A, A::InvalidA, B, B::InvalidB)

Max Langhof · Answer 2 · 2019-03-26T18:18:32.400

Nathan's solution is hard to beat in terms of implementation elegance. But if you desperately need a solution that doesn't rely on macros or that can also be used at run-time, here is one where you specify the mapping in a simple pair list.

At the core of it, we are using the fact that both enums should have contiguous underlying integral values (starting at zero), which means we can represent the mappings in both directions as simple arrays. This is all constexpr so zero overhead in the compile-time case. For usage at runtime this does store the info twice to allow instant lookup, but only takes N (sizeof(A) + sizeof(B)) storage. I don't know any data structure that does better (i.e. does not store any additional data beyond one of the two arrays and is better than linear search in both directions). Note that this is takes the same storage as storing the pairs themselves (but is not gaining anything from the bijectivity of the mapping).

template<class TA, class TB, class ... Pairs>
struct Mapper
{
    constexpr static std::array<TA, sizeof...(Pairs)> generateAIndices()
    {
        std::array<TA, sizeof...(Pairs)> ret{};
        ((void)((ret[static_cast<std::size_t>(Pairs::tb)] = Pairs::ta), 0), ...);
        return ret;
    }
    constexpr static std::array<TB, sizeof...(Pairs)> generateBIndices()
    {
        std::array<TB, sizeof...(Pairs)> ret{};
        ((void)((ret[static_cast<std::size_t>(Pairs::ta)] = Pairs::tb), 0), ...);
        return ret;
    }

    constexpr TB operator[](TA ta)
    {
        return toB[static_cast<std::size_t>(ta)];
    }
    constexpr TA operator[](TB tb)
    {
        return toA[static_cast<std::size_t>(tb)];
    }

    static constexpr std::array<TA, sizeof...(Pairs)> toA = generateAIndices();
    static constexpr std::array<TB, sizeof...(Pairs)> toB = generateBIndices();
};

(This uses fold expressions + comma operator to assign values the array elements, see e.g. here).

User code provides a list of mapping pairs to use and is done:

using MyMappingList = PairList<
    MyMappingPair<A::A1, B::B2>,
    MyMappingPair<A::A2, B::B3>,
    MyMappingPair<A::A3, B::B4>,
    MyMappingPair<A::A4, B::B1>
    >;

auto mapper = makeMapper<A, B>(MyMappingList{});

Demo including full compile-time test cases and maximally efficient runtime code (literally just mov).

Here is a previous version that works only at compile-time (see also revision history): https://godbolt.org/z/GCkAhn

@Hiroki Don't worry, I initially had a different one and deleted it while I worked on the same one as you. — Max Langhof, Mar 26 '19 at 18:24
@Hiroki However, I have a hunch that using some overly clever xor trickery, one might be able to halve the required storage space (think of xor-doubly linked list). Maybe you've got an idea? — Max Langhof, Mar 26 '19 at 18:26
@ MaxLanghof Ah I understand. You are clever at that point :). — Hiroki, Mar 26 '19 at 18:33

Hiroki · Answer 3 · 2019-03-27T00:25:08.970

If you need to perform the run-time lookup, the following method would work with the complexity O(1) in both directions.

Since all your enumerators of A and B are not initialized, the first enumerator has the value of zero, the second one has the value of 1, and so on. Regarding these zero-starting integers as indices of arrays, we can construct a bidirectional map using two arrays. For instance, assuming the current mapping as

A::FirstA  (=0) <--> B::SecondB (=1),
A::SecondA (=1) <--> B::FirstB  (=0),

, then let us define the following two arrays

A arrA[2] = {A::SecondA, A::FirstA},
B arrB[2] = {B::SecondB, B::FirstB},

where arrA[i] is the enumerator of A corresponding to i-th enumerator of B, and vice versa. In this setup, we can perform a lookup from A a to B as arrB[std::size(a)], and vice versa, with the complexity O(1).

The following class biENumMap is an implementation example of the above bidirectional method with C++14 and over. Please note that since the extended constexpr is available from C++14, here the ctor also can be a constant expression. Two overloads operator() are lookup functions from A and B, respectively. These can also be constant expressions and this class enables us to perform bidirectional lookup at both compile-time and run-time:

template<std::size_t N>
class biENumMap
{
    A arrA[N];
    B arrB[N];

public:
    constexpr biENumMap(const std::array<std::pair<A,B>, N>& init) 
        : arrA(), arrB()
    {        
        for(std::size_t i = 0; i < N; ++i)
        {
            const auto& p = init[i];
            arrA[static_cast<std::size_t>(p.second)] = p.first;
            arrB[static_cast<std::size_t>(p.first) ] = p.second;
        }
    }

    constexpr A operator()(B b) const{
        return arrA[static_cast<std::size_t>(b)];
    }

    constexpr B operator()(A a) const{
        return arrB[static_cast<std::size_t>(a)];
    }
};

We can use this class as follows:

DEMO

// compile-time construction.
constexpr biEnumMap<3> mapper({{
    {A::FirstA  , B::SecondB },
    {A::SecondA , B::FirstB  },
    {A::InvalidA, B::InvalidB} }});

// compile-time tests, A to B.
static_assert(mapper(A::FirstA  ) == B::SecondB );
static_assert(mapper(A::SecondA ) == B::FirstB  );
static_assert(mapper(A::InvalidA) == B::InvalidB);

// compile-time tests, B to A.
static_assert(mapper(B::FirstB  ) == A::SecondA );
static_assert(mapper(B::SecondB ) == A::FirstA  );
static_assert(mapper(B::InvalidB) == A::InvalidA);

// run-time tests, A to B.
std::vector<A> vA = {A::FirstA, A::SecondA, A::InvalidA};
assert(mapper(vA[0]) == B::SecondB );
assert(mapper(vA[1]) == B::FirstB  );
assert(mapper(vA[2]) == B::InvalidB);    

// run-time tests, B to A.
std::vector<B> vB = {B::FirstB, B::SecondB, B::InvalidB};
assert(mapper(vB[0]) == A::SecondA );
assert(mapper(vB[1]) == A::FirstA  );
assert(mapper(vB[2]) == A::InvalidA);

Effective bidirectional scoped enum mapping

3 Answers3