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).

I find the `Map` to be elegant. The problem seems to be the maintainability of `InverseMap`. — John Dibling, Sep 27 '14 at 15:23

score 27 · Answer 1 · answered Sep 27 '14 at 22:57

27

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");

answered Sep 27 '14 at 22:57

zch

14,931
2
41
49

So the sacrifice for having any general key domain is that a search be made for inverse and non-inverse look-ups? – prestokeys Sep 27 '14 at 23:42
@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`). – zch Sep 27 '14 at 23:50
1

Is it possible to generate compile error if the key is not found, rather than throwing an exception at runtime? – user877329 Jun 12 '16 at 11:06
@user877329, using `std::integral_constant::value` should work. – zch Jun 13 '16 at 10:47

score 5 · Answer 2 · answered Sep 27 '14 at 15:03

5

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.

answered Sep 27 '14 at 15:03

Alexandre C.

55,948
11
128
197

Thanks! Just curious, any way to achieve this without using macros? – prestokeys Sep 27 '14 at 15:07
@prestokeys: I don't know. Probably, but this would likely be more complex. – Alexandre C. Sep 27 '14 at 16:55

H Walters · Accepted Answer · 2014-09-28T01:15:25.767

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.

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. — prestokeys, Sep 28 '14 at 00:21

zch · Answer 4 · 2014-09-27T15:23:35.123

3

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");

edited Sep 27 '14 at 15:23

answered Sep 27 '14 at 15:18

zch

14,931
2
41
49

Beautiful! I don't see how the last static_assert can turn out false though. – prestokeys Sep 27 '14 at 15:39
@prestokeys, it can't, it's there for testing and demonstration. – zch Sep 27 '14 at 15:50
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. – StilesCrisis Sep 27 '14 at 17:13
@ StilesCrisis. What would be the order relation in the binary search? The mapped values do not follow the same ordering as the keys. – prestokeys Sep 27 '14 at 17:38
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. – prestokeys Sep 27 '14 at 17:45
@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. – zch Sep 27 '14 at 21:10
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. – StilesCrisis Sep 27 '14 at 22:17

score 2 · Answer 5 · answered Aug 09 '19 at 18:27

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).

StilesCrisis · Answer 6 · 2014-09-27T23:20:53.620

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;
}

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? — prestokeys, Sep 27 '14 at 22:41
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. — StilesCrisis, Sep 27 '14 at 22:53
Simplified the code a bit, but no real change in the complexity. — StilesCrisis, Sep 27 '14 at 23:21

Compile-time map and inverse map values

6 Answers6

Linked

Related