A Map with Two Types of Keys in C++

Published November 27, 2020

The need to associate keys to values is pretty common in computer programming. (That is a very general sentence, isn’t it?)

In C++, the standard tools to achieve that are std::map and std::multimap that use comparisons on keys and std::unordered_map and std::unordered_multimap that use hashing. Boost adds flat_map, that offers a different performance trade-off and bimap to look up keys and values. For more on flat maps, check out Björn Fahller’s article on Playful Programming.

While offering different approaches to the concept of a map, these structures have one thing in common: they associate one type of key to one type of value. For example the unique type of key in std::map<int, std::string> is int.

Why not associate two types of key to a type of value?

One use case for this is when we know two representations of the key when we insert it, and we want to be able to query the map on either one of them.

For instance, in pseudo-code:

// this map accepts keys in the form of char and int, and associates them to strings
m.insert(key1 = 0, key2 = '0', value = "zero")
m.insert(key1 = 1, key2 = '1', value = "one")
m.insert(key1 = 2, key2 = '2', value = "two")

...

EXPECT_TRUE(m[1] == "one")
EXPECT_TRUE(m['1'] == "one")

This seems like a problem that can be tackled by different angles, particularly since it can have different implementations and different interfaces. The only constraints are:

the two representations of the keys should be inserted at the same time,
the value should be queryable by either type of key.

Given the variety of solutions to this problem, let’s make this an collaborative experience and benefit from everyone’s point of view. By this I mean that anyone who thinks of a solution to implement the double-key map can put it forward. I’ll compile all the proposals into another article.

Here is my own proposal down here, followed by how to propose your own.

And a big thanks to Elom for showing me this interesting problem!

One implementation for the double-key map

Rationale

One idea to have a map with two keys is to hold two maps internally. One that maps the first key to the second key, and the other one that maps the second key to the value. An insertion into the double-key map actually inserts two associations in the internal maps:

map1: 1 -> '1'
map2: '1' -> "one"

Then a lookup on key1 one does two lookups internally: first finding the corresponding key2 to key1, and then finding the value corresponding to key2. And a lookup on key2 does only one lookup on the second map to find the corresponding value.

Since there is not one iterator in the collection, I can’t offer the conventional find method from std::map that returns an iterator to a pair key-value. But on the other hand, we can’t always return the value obtained by the internal lookups, because this value may not be present in the map.

So we can instead have an interface using optional. The find method returns an optional<Value>, which can be nullopt if the queried key isn’t in the map. To make it obvious that this structure doesn’t follow the STL’s convention, let’s not call it find. Let’s call it getValue for example.

Finally, this solution doesn’t allow for the practical operator[] of std::map, because in the case the key does not exist, it should insert it and return a reference to it. But here, if one representation of the key doesn’t exist in the map, the operator[] cannot insert it because it doesn’t know the other representation to insert along with it.

Code

Here is the code corresponding to the above rationale:

template <typename Key1, typename Key2, typename Value>
class doublekey_map
{
public:
    auto size() const
    {
        return key1_key2_.size();
    }
    
    void insert(std::tuple<Key1, Key2, Value> const& entry)
    {
        key1_key2_.insert(std::make_pair(std::get<0>(entry), std::get<1>(entry)));
        key2_value_.insert(std::make_pair(std::get<1>(entry), std::get<2>(entry)));
    }

    std::optional<Value> getValue(Key1 const& key1)
    {
        auto key2 = key1_key2_.find(key1);
        if (key2 == end(key1_key2_)) return std::nullopt;
        
        auto value = key2_value_.find(key1_key2_.find(key1)->second);
        if (value == end(key2_value_)) return std::nullopt;
        
        return key2_value_.find(key1_key2_.find(key1)->second)->second;
    }

    std::optional<Value> getValue(Key2 const& key2)
    {
        auto value = key2_value_.find(key2);
        if (value == end(key2_value_)) return std::nullopt;

        return value->second;
    }

private:
    std::map<Key1, Key2> key1_key2_;
    std::map<Key2, Value> key2_value_;
};

Discussion

This solution has the following drawbacks:

it doesn’t follow the conventions of the STL (no begin, end, find, operator[] nor aliases), which is bad because it isn’t compatible with STL algorithms,
the lookup of the first key takes more time that the lookup of the second one, although both are in log(N).

Show me how you would approach this problem

Let’s make this a collaborative exploration! Implement your own solution and link to it in a comment below.

To submit your own solution about how to implement the double-key map, you can get started with this Godbolt template. It contains a couple of basic test cases that the structure should satisfy, but feel free to adapt them to your interface to make them compile.

Once you’ve coded it up, click the “Share” button to get a link and post it in the comment section below. Please, follow the Rationale-Code-Discussion structure like above to add a few words to explain your solution, and thus make it easier to browse the various ideas.

I hope you find this interesting! If you like this sort of collaborative experience, let me know as well.