CODEWITHSUNDEEP
c++keystdstdmapcompound-key
danijar
danijar

Reputation: 34255

Map with multiple keys in C++

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.

Upvotes: 6

Views: 13791

Answers (2)

Clint Chelak
Clint Chelak

Reputation: 242

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

Upvotes: 0

Chad
Chad

Reputation: 19052

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

Upvotes: 5

Related Questions