Compile-time map and inverse map values

Question

Can someone recommend a more elegant way to achieve these compile-time constants?

template <int> struct Map;
template <> struct Map<0> {static const int value = 4;};
template <> struct Map<1> {static const int value = 8;};
template <> struct Map<2> {static const int value = 15;};

template <int> struct MapInverse;
template <> struct MapInverse<4> {static const int value = 0;};
template <> struct MapInverse<8> {static const int value = 1;};
template <> struct MapInverse<15> {static const int value = 2;};

The values need to be constexpr in my program, yet the inverse mapped values are getting tedious to update (and easy to make mistakes or forget to do even).

Gesso

I find the Map to be elegant. The problem seems to be the maintainability of InverseMap. – Mukden

Answer 1

Another TMP approach for a linear search using C++11:

#include <type_traits>

// === Types:
// Usage:
//    Function<Map<x1,y1>,Map<x2,y2>,...>
template<int D, int R> struct Map { enum { domain=D, range=R }; };
template<typename ...A> struct Function {};

// === Metafunctions:
// Usage:
//    ApplyFunction<x,F>::value
template<int I, typename M> struct ApplyFunction;
// Usage:
//    ApplyFunctionInverse<x,F>::value
template<int I, typename M> struct ApplyFunctionInverse;

// ==== Example:
// Define function M to the mapping in your original post.
typedef Function<Map<0,4>,Map<1,8>,Map<2,15>> M;

// ==== Implementation details
template<typename T> struct Identity { typedef T type; };
template<int I, typename A, typename ...B> struct ApplyFunction<I, Function<A,B...> > {
   typedef typename
      std::conditional <I==A::domain
                       , Identity<A>
                       , ApplyFunction<I,Function<B...>> >::type meta;
   typedef typename meta::type type;
   enum { value = type::range };
};
template<int I, typename A> struct ApplyFunction<I, Function<A>> {
   typedef typename
       std::conditional <I==A::domain
                        , Identity<A>
                        , void>::type meta;
   typedef typename meta::type type;
   enum { value = type::range };
};
// Linear search by range
template<int I, typename A> struct ApplyFunctionInverse<I, Function<A>> {
   typedef typename
       std::conditional <I==A::range
                        , Identity<A>
                        , void>::type meta;
   typedef typename meta::type type;
   enum { value = type::domain };
};
template<int I, typename A, typename ...B> struct ApplyFunctionInverse<I, Function<A,B...> > {
   typedef typename
       std::conditional <I==A::range
                        , Identity<A>
                        , ApplyFunctionInverse<I,Function<B...>> >::type meta;
   typedef typename meta::type type;
   enum { value = type::domain };
};

// ==============================
// Demonstration
#include <iostream>
int main()
{
   // Applying function M
   std::cout << ApplyFunction<0,M>::value << std::endl;
   std::cout << ApplyFunction<1,M>::value << std::endl;
   std::cout << ApplyFunction<2,M>::value << std::endl;

   // Applying function inverse M
   std::cout << ApplyFunctionInverse<4,M>::value << std::endl;
   std::cout << ApplyFunctionInverse<8,M>::value << std::endl;
   std::cout << ApplyFunctionInverse<15,M>::value << std::endl;
}

I prefer zch's C++11 solution for this application, but maybe someone will find value in this approach.

Gourmont

Thanks for joining in. This looks to be the most general MTP solution so far. I knew variadic templates would come into the picture sooner or later. – Gesso

Answer 2

In this C++11 solution all map items are kept in constexpr array and there are constexpr recursive functions to search by either key or value.

#include <utility>

using Item = std::pair<int, int>;
constexpr Item map_items[] = {
    { 6, 7 },
    { 10, 12 },
    { 300, 5000 },
};
constexpr auto map_size = sizeof map_items/sizeof map_items[0];

static constexpr int findValue(int key, int range = map_size) {
    return
            (range == 0) ? throw "Key not present":
            (map_items[range - 1].first == key) ? map_items[range - 1].second:
            findValue(key, range - 1);
};

static constexpr int findKey(int value, int range = map_size) {
    return
            (range == 0) ? throw "Value not present":
            (map_items[range - 1].second == value) ? map_items[range - 1].first:
            findKey(value, range - 1);
};

static_assert(findKey(findValue(10)) == 10, "should be inverse");

Aenneea

So the sacrifice for having any general key domain is that a search be made for inverse and non-inverse look-ups? – Gesso

@prestokeys, I'm not even sure if that is much of a sacrifice. I would expect compilers to do memoization of constexpr call and eliminate compilation time penalty. Additionally, constexpr functions often compile much faster than tons of template instantiations. I'm only leaving my original solution because it works in C++03 (excluding static_assert). – Aenneea

Is it possible to generate compile error if the key is not found, rather than throwing an exception at runtime? – Threat

@user877329, using std::integral_constant<int, findKey(10)>::value should work. – Aenneea

Answer 3

I'd use a macro for this:

template <int> struct Map;
template <int> struct MapInverse;

#define MAP_ENTRY(i, j) \
    template <> struct Map<i> {static const int value = j;}; \
    template <> struct MapInverse<j> {static const int value = i;};

MAP_ENTRY (0, 4)
MAP_ENTRY (1, 8)
MAP_ENTRY (2, 15)

This keeps both maps in sync.

Merriweather

Thanks! Just curious, any way to achieve this without using macros? – Gesso

@prestokeys: I don't know. Probably, but this would likely be more complex. – Merriweather

Answer 4

Solution without macros, but using the assumption that keys are from interval [0, MAP_SIZE).

Recursive template FindInverse scans Map from end to the beginning searching for given value.

template <int> struct Map;
template <> struct Map<0> {static const int value = 4;};
template <> struct Map<1> {static const int value = 8;};
template <> struct Map<2> {static const int value = 15;};
const int MAP_SIZE = 3;

template <int x, int range> struct FindInverse {
    static const int value = (Map<range - 1>::value == x)?
                                (range - 1):
                                (FindInverse<x, range - 1>::value);
};

template <int x> struct FindInverse<x, 0> {
    static const int value = -1;
};

template <int x> struct MapInverse: FindInverse<x, MAP_SIZE> {
    static_assert(MapInverse::value != -1, "x should be a value in Map");
};

static_assert(MapInverse<Map<1>::value>::value == 1, "should be inverse");

Aenneea

Beautiful! I don't see how the last static_assert can turn out false though. – Gesso

@prestokeys, it can't, it's there for testing and demonstration. – Aenneea

With large maps, you might hit compiler template expansion limits using this approach. I wonder if the search could do something smarter like binary search. – Murtha

@ StilesCrisis. What would be the order relation in the binary search? The mapped values do not follow the same ordering as the keys. – Gesso

But a binary search might, if such exists, remove the (restrictive) condition that the keys be 0,1,2,...MAP_SIZE-1. My gut tells me that there is still room for improvement to zch's solution. – Gesso

@StilesCrisis, I find it not likely. Gcc and clang use default template depth of 512, which should probably be enough. But if you want it's possible to go make depth logarithmic. Removing 0, ...,MAP_SIZE - 1 constraint might also be possible with some SFINAE, but resulting solution might be significantly more complex. – Aenneea

I experimented with a binary searching version and it was extremely slow to compile. It was better once I limited the search space but I don't believe there's any way to make it perform any better than a simple linear probe. – Murtha

Answer 5

Here's my C++17 implementation of a generic constexpr map

#include <type_traits>
#include <tuple>

//tag for typenames
template <class T>
struct tag_type
{
    using type = T;
};

//tag for autos
template <auto val>
struct tag_auto
{
    constexpr static decltype(val) value = val;
};

//generic pair
template <typename key_tag, typename val_tag>
struct cexpr_pair
{
    using key = key_tag;
    using value = val_tag;
};

template <class ... cexpr_pairs>
class cexpr_generic_map
{
    template <typename cexpr_tag_key, size_t iter = 0>
    constexpr static auto Find()
    {
        //failed to find by key
        if constexpr (iter == sizeof...(cexpr_pairs))
            return cexpr_pair<cexpr_tag_key, void>();
        else
        {
            typedef std::tuple_element_t<iter, std::tuple<cexpr_pairs...>> cur_pair;
            if constexpr (std::is_same_v<cexpr_tag_key, cur_pair::key>)
                return cur_pair();
            else 
                return Find<cexpr_tag_key, iter + 1>();
        }
    }

public:

    template <typename tag_key>
    using found_pair = decltype(Find<tag_key>());
};

Since (I assume) one value can be used only in one combination (in your case it's 4 - 15, can't be 15 - 88) there's really no need to use "two different maps", you can simply add both initial and inversed values there.

Usage example:

typedef cexpr_generic_map<
//initial values
cexpr_pair<tag_auto<0>, tag_auto<4>>,
cexpr_pair<tag_auto<1>, tag_auto<8>>,
cexpr_pair<tag_auto<2>, tag_auto<15>>,

//inversed values
cexpr_pair<tag_auto<4>, tag_auto<0>>,
cexpr_pair<tag_auto<8>, tag_auto<1>>,
cexpr_pair<tag_auto<15>, tag_auto<2>>
> map_inverse;

//find initial
static_assert(map_inverse::found_pair<tag_auto<0>>::value::value == 4);
static_assert(map_inverse::found_pair<tag_auto<1>>::value::value == 8);
static_assert(map_inverse::found_pair<tag_auto<2>>::value::value == 15);

//find inversed
static_assert(map_inverse::found_pair<tag_auto<4>>::value::value == 0);
static_assert(map_inverse::found_pair<tag_auto<8>>::value::value == 1);
static_assert(map_inverse::found_pair<tag_auto<15>>::value::value == 2);

You can also add a lookup by value (to find the first matching pair), or you can modify it to be "not so generic" and substitute tags with just autos in cexpr_pair's template declaration (likewise modify key and value definitions).

Kickoff

Answer 6

Here's a template metaprogramming technique that utilizes a binary search. I suspect it's less efficient than the linear search approach, but I figured it might be interesting to others. I'm sure this solution could be improved.

#include <iostream>

template <int> struct Map { static const int value = INT_MIN; };

template <> struct Map<0> { static const int value = 4; };
template <> struct Map<1> { static const int value = 8; };
template <> struct Map<2> { static const int value = 15; };

// This searches the Map at POS 0 +/- a DELTA of 0x100
template
<
    int x,
    int POS = 0,
    int DELTA = 0x100
>
struct MapInverse
{
    typedef  MapInverse<x, POS - (DELTA >> 1), (DELTA >> 1)> LEFT;
    typedef  MapInverse<x, POS + (DELTA >> 1), (DELTA >> 1)> RIGHT;

    static const int MATCH_POS =
              (Map<POS>::value == x)? POS:
                        (DELTA == 0)? INT_MIN:
        (LEFT::MATCH_POS != INT_MIN)? LEFT::MATCH_POS:
                                      RIGHT::MATCH_POS;
};

int main(int argc, const char * argv[])
{
    // insert code here...
    std::cout
    << MapInverse<0>::MATCH_POS << std::endl
    << MapInverse<1>::MATCH_POS << std::endl
    << MapInverse<2>::MATCH_POS << std::endl
    << MapInverse<3>::MATCH_POS << std::endl
    << MapInverse<4>::MATCH_POS << std::endl
    << MapInverse<5>::MATCH_POS << std::endl
    << MapInverse<6>::MATCH_POS << std::endl
    << MapInverse<7>::MATCH_POS << std::endl
    << MapInverse<8>::MATCH_POS << std::endl
    << MapInverse<9>::MATCH_POS << std::endl
    << MapInverse<10>::MATCH_POS << std::endl
    << MapInverse<11>::MATCH_POS << std::endl
    << MapInverse<12>::MATCH_POS << std::endl
    << MapInverse<13>::MATCH_POS << std::endl
    << MapInverse<14>::MATCH_POS << std::endl
    << MapInverse<15>::MATCH_POS << std::endl
    << MapInverse<16>::MATCH_POS << std::endl
    << MapInverse<17>::MATCH_POS << std::endl;

    return 0;
}

Murtha

Regardless of what performance it gives, this is definitely worth studying. Thanks for your interest. With only 3 elements in the map, the linear search may appear faster, but perhaps your binary search wins out when the map is large? – Gesso

In its current state, it does the search in tree order, but there isn't any good way to terminate the search early. Anyway, all the "performance" results only affect compilation speed; the generated code should have the exact result at its disposal with no overhead. Still, it's a fun experiment for me. – Murtha

Simplified the code a bit, but no real change in the complexity. – Murtha