Question: 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.

Answer: 
If I got the question correctly, all you need is a [map](http://en.cppreference.com/w/cpp/container/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;

```
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.