symmetrical associative array search by key and value

I need to describe an associative array in which to search, you can use the key and value. With functions add, delete, getBy1st (search by key), getBy2nd (search by value). For example in C++:

symmap<std::string, int> m;  
m.insert(make_pair<std::string,int> ("hello", 1));
m.insert(make_pair<开发者_运维知识库;std::string,int> ("wow", 2));
...
m.getBy1st("hello"); // returns 1
m.getBy2nd(2);// returns "wow"

It should work for O(log(n)) and store in std::pair . I can not decide what the data structure used to store. Maybe i can use some variation of rb-tree to store it?

This sounds a lot like Boost.Bimap.

Why not use a pair of hashtables to store the data - one hashing from T1 to T2 and the other hashing in the other direction?