c++ - 如何优化从 multimap 删除

Question

我定义了两个 multimap，因此 multimap phoneNums；和 multimap numPhones；它们是某种电话注册表——phoneNums 包含 key 名称和第二个参数电话号码，numPhones 包含 key 电话号码，第二个是名称。当我想从 phoneNums 中删除字符串键时，我想优化它们的删除，这也是 numPhones 中的第二个元素。当我输入数据时，它被输入到两个多映射中，所以它们实际上是相同的，但交换了第一个和第二个当我对它进行测试时，它说删除速度太慢 - N*N 并且必须只有 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

更一般地，对于这类问题，您可以使用以下技术:

• 保存数据的容器
• 多个索引，指向上述数据

如果你沿着数据放置反向索引(以便指向索引中引用该项目的位置)，那么你可以有效地删除任何项目:

• 使用最合适的索引查找(取决于您拥有的信息)
• 删除各种索引中的引用(你有指向它们的迭代器，所以效率很高)
• 删除数据本身

这可能看起来很乏味，但这就是Boost.MultiIndex是为了:)

对于您所说的非常具体的情况，MultiIndex 库上方有一个名为 Boost.Bimap 的包装器如 Jack 所述。