Map with multiple keys in C++

Question

I want to store data by both, their name and their index. In other words, I want to map string names to objects and also give them a custom order.

What I came up with first is a std::vector of pairs of the string key and the object. The order was given by the position in the vector.

std::vector<std::pair<std::string, object> >

But this approach seems to be suboptimal since it doesn't automatically check for the uniqueness of string names. Moreover it feels wrong to group the objects by their order first, because logically their first order distinction is the name.

I need a data structure that allows access by both name and index.

std::magic<std::string, unsigned int, object> collection;

// access by either string or unsigned int key
collection.insert("name", 42, new object());
collection["name"]
collection[42]

Is there a data structure for this use case already? If not, how can I put one together, preferably using the standard library? Also I would like a way to insert new elements at the position after a given element without moving all further elements around.

@n.m. I don't need to order by string name. So basically I need a `std::vector` for order and an `std::unordered_map` for names. But my question is if there is already a solution or at least a preferable way. — danijar, Apr 06 '13 at 17:46
`unordered_map` is a possibility if you are using C++11. For the indices, a choice between `vector` and `map`/`unordered_map` is dictated by what should happen when you remove things from your collection. If you don't care about stable indices, you can use `vector`. I think two containers *is* the preferable way. — n. m. could be an AI, Apr 06 '13 at 17:51
Maybe http://www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/index.html — , Apr 06 '13 at 18:16
Look at `boost::multiindex`, it was made just for this purpose. — Chad, Apr 06 '13 at 18:16
@Chad That's what I was looking for! If you would write an answer I'll mark it as accepted. — danijar, Apr 06 '13 at 19:08

score 5 · Accepted Answer · answered Apr 08 '13 at 01:06

5

Boost provides a set of containers just for this purpose, see: boost::multiindex

answered Apr 08 '13 at 01:06

Chad

18,706
4
46
63

score 0 · Answer 2 · answered Dec 09 '22 at 19:49

I'm trying to write a solution using std library, as requested in the original post. I will not have access to boost in my resource-constrained system. I've drafted a two-map system mentioned in the comments.

A big downside is that you'll have to wrap each public function that a std::map or std::vector normally offers, and my wrapper might not be as optimal.

But, this is a start. Let me know of improvements to my answer in the comment, and I'll edit the response when I can

#include <unordered_map>
#include <string>
#include <iostream>

struct Object
{
    int val;
};

template <typename T>
class MultiKeyMap
{
    std::unordered_map<std::string, uint> nameToIdMap;
    std::unordered_map<uint, T> idToValMap;

public:
    T& find(const std::string& name)
    {
        return find(nameToIdMap[name]);
    }

    T& find(const uint id)
    {
        return idToValMap[id];
    }

    T& operator[](const std::string& name) { return find(name); }
    T& operator[](const uint id) { return find(id); }

    void insert(uint id, const std::string& name, T&& val)
    {
        nameToIdMap[name] = id;
        idToValMap[id] = val;
    }
};

int main()
{
    MultiKeyMap<Object> mkmap;
    mkmap.insert(1, "one", Object{11});
    mkmap.insert(2, "two", Object{22});

    std::cout << "key=1: val=" << mkmap[1].val << "\n";
    std::cout << "key='one': val=" << mkmap["one"].val << "\n";
    std::cout << "key=2: val=" << mkmap[2].val << "\n";
    std::cout << "key='two': val=" << mkmap["two"].val << "\n";
}

Map with multiple keys in C++

2 Answers2

Linked