How to optimize erasing from multimap

Question

I have two multimaps defined so multimap phoneNums; and multimap numPhones; they are some kind of phone registry - phoneNums contains Key name, and second argument phonenumber, numPhones contain Key phonenumber and second is name. I want to optimize erase from both of them when i want to delete string Key form phoneNums, which is also second element in numPhones. When i enter data it is entered in both multimaps so they are actually the same but with swapped first and second when i put it on tests it says that erasing is too slow - N*N and must be only N

cin>>stringToErase;
                    phoneNums.erase(stringToErase);
                    multimap<string, string>::iterator it;
                    multimap<string, string>::iterator tmpr;
                    for(it = numPhones.begin(); it != numPhones.end();it++)
                    {

                        if(it->second == tringToErase)
                        {   
                            tmpr = it;      
                            numPhones.erase(it,tmpr);                           
                        }                       
                    }

Answer 1

More generally, for this kind of problem, you can use the following technic:

• A container, which holds the data
• Several indexes, which point to the data aforementioned

If you place reverse indexes along the data (so as to point to the places in the indexes that refer to this item), then you can efficiently remove any item:

• Look it up using the most suitable index (depending on the info you have)
• Delete the references in the various indexes (you have iterators to them, so it's efficient)
• Delete the data itself

This may seem tedious, but it's what Boost.MultiIndex is for :)

For the very specific case you are speaking of, there is a wrapper above the MultiIndex library called Boost.Bimap as mentioned by Jack.

Answer 2

Why didn't you use a more suitable/specific data structure for your problem like a Bimap?

Boost has one..