Compile-Time Map and Inverse Map Values

Compile-time map and inverse map values

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.

How to build a compile-time key/value store?

In C++11:

template <int kk, int vv>
struct kv
{
    static const int k = kk, v = vv;
};

template <int dflt, typename...>
struct ct_map;

template <int dflt>
struct ct_map<dflt>
{
    template<int>
    struct get
    {
        static const int val = dflt;
    };
};

template<int dflt, int k, int v, typename... rest>
struct ct_map<dflt, kv<k, v>, rest...>
{
    template<int kk>
    struct get
    {
        static const int val =
            (kk == k) ?
            v :
            ct_map<dflt, rest...>::template get<kk>::val;
    };
};

typedef ct_map<42, kv<10, 20>, kv<11, 21>, kv<23, 7>> mymap;

#include <iostream>
int main()
{
    std::cout << mymap::get<10>::val << std::endl;
    std::cout << mymap::get<11>::val << std::endl;
    std::cout << mymap::get<23>::val << std::endl;
    std::cout << mymap::get<33>::val << std::endl;
}

Compile-Time Lookup-Table with initializer_list

@Barry's answer pinpointed me in the right direction. Always explicitly listing pair in the list is undesirable. Moreover, I want to be able to partially specialize the template argument list of map. Consider the following example:

// for the sake of the example, suppose this works
constexpr map n({{1, "1"}, {2, "2"}});
              // -> decltype(n) == map<int, const char*, 2>

// the following won't work
constexpr map<std::size_t, const char*> m({{1, "1"}, {2, "2"}});

However, perhaps the user wants that the map contains std::size_t as key, which does not have a literal. i.e. s/he would have to define a user-defined literal just to do that.

We can resolve this by offloading the work to a make_map function, allowing us to partially specialize the map:

// deduction guide for map's array constructor
template<class Key, class Value, std::size_t Size>
map(cxpair<Key, Value>(&&)[Size]) -> map<Key, Value, Size>;

// make_map builds the map
template<typename Key, typename Value, std::size_t Size>
constexpr auto make_map(cxpair<Key, Value>(&&m)[Size]) -> map<Key, Value, Size>
{ return map<Key, Value, Size>(std::begin(m), std::end(m)); }

// allowing us to do:
constexpr auto mapr = make_map<int, std::string_view>({ {1, "1"},
                                                        {2, "2"},
                                                        {3, "3"} });

Invert Map | Values --- Keys

Do it like this. Basically, it employs a merge function which concatenates values for a duplicate key.

• Create a new map
• Use the values of the old map for the keys to the new
• If the new map does not have a value for the key, put the value in the new map
• Otherwise, concatenate the value to the old value for that key

        HashMap<String, String> cities = new HashMap<String, String>();

        cities.put("Manchester", "UK");
        cities.put("London", "UK");
        cities.put("New York", "US");
        cities.put("Chicago", "US");

        Map<String,String> inverted = new HashMap<>();
        for (String key : cities.keySet()) {
            String newKey = cities.get(key);
            String value = inverted.get(newKey);
            if (value == null) {
                inverted.put(newKey, key);
            } else {
                value = value + ", " + key;
                inverted.put(newKey, value);
            }

        }
        for (Entry<String,String> e : inverted.entrySet()) {
            System.out.println(e.getKey() + " -> " + e.getValue());
        }

It prints

UK -> Manchester, London
US -> New York, Chicago

Since you didn't specify how to handle duplicate keys. I could also have stored it in a Map<String,List<String>>

Invert Map with list value MapKey, ListValue to Map Value, Key in Java 8

You can use

Map<Integer, String> mapNumberToType = mapOfIntList.entrySet().stream()
    .collect(HashMap::new, (m,e)->e.getValue().forEach(v->m.put(v,e.getKey())), Map::putAll);

You may recognize the similarity to the forEach based code of this answer within the second function passed to collect (the accumulator) function. For a sequential execution, they do basically the same, but this Stream solution supports parallel processing. That’s why it needs the other two functions, to support creating local containers and to merge them.

See also the Mutable reduction section of the documentation.

reverse map value c++

You can iterate over your map forward and backwards at the same time:

std::map<int, int>::const_iterator forwardIt = mapOriginal.begin();
std::map<int, int>::const_reverse_iterator reverseIt = mapOriginal.rbegin();
for ( ;
    forwardIt != mapOriginal.end() ;
    ++forwardIt, ++reverseIt)
{
    mapReverse[forwardIt->first] = reverseIt->second;
}

However, that seems like an unusual use of maps. Are you sure a vector would not fulfill your needs?

std::vector<int> vec { 3, 2, 1 };

std::vector<int> reverseVec;
std::reverse_copy(vec.begin(), vec.end(), std::back_inserter(reverseVec));
// or, if you want to reverse in-place:
std::reverse(vec.begin(), vec.end());

Compile-time population of data structures other than arrays?

Not easily, no. If you tried to do your first example using malloc, obviously it wouldn't work at compile time. Since every single standard container utilizes new (well, std::allocator<T>::allocate(), but we'll pretend that it's new for now), we cannot do this at compile time.

That having been said, it depends on how much pain you are willing to go through, and how much you want to push back to compile time. You certainly cannot do this using only standard library features. Using boost::mpl on the other hand...

#include <iostream>

#include "boost/mpl/map.hpp"
#include "boost/mpl/for_each.hpp"
#include "boost/mpl/string.hpp"
#include "boost/mpl/front.hpp"
#include "boost/mpl/has_key.hpp"

using namespace boost::mpl;

int main()
{
    typedef string<'One ', 'fish'> strone;
    typedef string<'Two ', 'fish'> strtwo;
    typedef string<'Red ', 'fish'> strthree;
    typedef string<'Blue', 'fish'> strfour;

    typedef map<pair<int_<555>, strone>,
        pair<int_<666>, strtwo>,
        pair<int_<451>, strthree>,
        pair<int_<626>, strfour>> m;

    std::cout << c_str<second<front<m>::type>::type>::value << "\n";
    std::cout << has_key<m, int_<666>>::type::value << "\n";
    std::cout << has_key<m, int_<111>>::type::value << "\n";
}

Swift: map set of values A to B and B to A

A bijective function from a set to itself is a permutation. If the set consists of consecutive integers starting at zero then the permutation can be represented as an array.

In your case, the mapping from [0, 1, 2] to itself defined by

0 -> 1, 1 -> 2, 2 -> 0

would be represented as the array [1, 2, 0]. The “left-to-right” mapping then becomes a subscript operation:

let perm = [1, 2, 0]

print(perm[1]) // 2

The “right-to-left” mapping is the inverse permutation, and can also be represented as an array:

func inversePermution(of perm: [Int]) -> [Int]? {
    var inverse: [Int] = Array(repeating: -1, count: perm.count)
    for (idx, elem) in perm.enumerated() {
        // Check for valid entries:
        guard elem >= 0 && elem < perm.count else { return nil }
        // Check for duplicate entries:
        guard inverse[elem] == -1 else { return nil }
        // Set inverse mapping:
        inverse[elem] = idx
    }
    return inverse
}

(This is just to demonstrate the general idea. Of course you can make this an Array extension method, or define a Permutation type with this and more methods.)

In your example:

if let invPerm = inversePermution(of: perm) {
    print(invPerm) // [2, 0, 1]

    print(invPerm[2]) // 1
}

---

Related Topics