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