CODEWITHSUNDEEP
c++stl
JT1
JT1

Reputation: 453

Need a quick way to find an object using two keys

What is an idiomatic way in C++ to have an object store that can be searched with respect to two keys? Essentially what I would like is to store things of type A in a binary search tree (BST) with the BST constructed using the order relation on A.key. However, each A also has a unique A.otherval and I essentially need to delete keys based on this value.

In C I would typically just have a BST with parent pointers and a hash table based with the other values as a key storing pointers to nodes of the BST. I can delete keys through the hash table by getting the node and calling tree delete on that node.

I'm looking for how to do this correctly using STL containers.

Upvotes: 1

Views: 104

Answers (2)

bgoldst
bgoldst

Reputation: 35314

I would recommend two maps, one to map the key to the instance of A (the primary map), and another to map the otherVal to the key:

typedef ... Key;
typedef ... OtherVal;
struct A { Key key; OtherVal otherVal; ... };

typedef std::map<Key,A> KeyToAMap;
typedef std::map<OtherVal,Key> OtherValToKeyMap;

KeyToAMap keyToAMap;
OtherValToKeyMap otherValToKeyMap;

This way you can work with keyToAMap without any additional complexity, but when it comes time to delete, you just need an additional lookup.

To ease the usage, I would also recommend writing functions for wrapping insertion and deletion in both maps:

void insertNewA(const A& a) {
    keyToAMap.insert(std::make_pair(a.key, a ));
    otherValToKeyMap.insert(std::make_pair(a.otherVal, a.key ));
}

void deleteByOtherVal(const OtherVal& otherVal) {
    OtherValToKeyMap::iterator it1 = otherValToKeyMap.find(otherVal);
    if (it1 == otherValToKeyMap.end()) { /* error */ }
    Key& key = it1->second;
    KeyToAMap::iterator it2 = keyToAMap.find(key);
    if (it2 == keyToAMap.end()) { /* error */ }
    keyToAMap.erase(it2);
    otherValToKeyMap.erase(it1);
}

An advantage of this solution is it only requires two maps, as opposed to a multi-level map solution, which requires 1+N maps, where N is the number of entries in the primary map.

Upvotes: 0

SingerOfTheFall
SingerOfTheFall

Reputation: 29966

If I got the question correctly, all you need is a map in a map, so

std::map<first_key_type, std::map<second_key_type, value_type>> map;
map[key1][key2] = something;

Edit:

I assume that all the values that have the same first key are the same, and the second key is only used as an additional search/remove criteria. In that case, to get the value by the first key only you can use something like

map.at(key).cbegin()->second;

Upvotes: 1

Related Questions