如何从C++ multimap中删除特定的一对元素？

Question

#include <map>

...

multimap<char,int> mymap;

mymap.insert(pair<char,int>('a',10));
mymap.insert(pair<char,int>('b',15));
mymap.insert(pair<char,int>('b',20));
mymap.insert(pair<char,int>('c',25));

假设我现在想要删除我刚刚添加到映射表中的一对键值。

我知道如何移除整个键入口，例如，如果我的键是 'b'，那么它将同时删除 'b', 15 和 'b', 20。

但是如果我只想删除 'b', 20 这一对，应该怎么编写代码呢？

- Jim Blackler

Answer 1

你可以使用 std::multimap<char, int>::equal_range，这将给你一个迭代器范围，其中包含所有具有特定键的键值对。因此，如果要查找 'b'，则会得到一个包含所有具有 'b' 作为键的 键值对 的迭代器范围。

然后，您可以简单地遍历该范围，并通过擦除迭代器来删除任何您认为合适的键值对。

multimap<char,int> mymap;

mymap.insert(pair<char,int>('a',10));
mymap.insert(pair<char,int>('b',15));
mymap.insert(pair<char,int>('b',20));
mymap.insert(pair<char,int>('c',25));

typedef multimap<char, int>::iterator iterator;
std::pair<iterator, iterator> iterpair = mymap.equal_range('b');

// Erase (b,15) pair
//
iterator it = iterpair.first;
for (; it != iterpair.second; ++it) {
    if (it->second == 15) { 
        mymap.erase(it);
        break;
    }
}

- Charles Salvia

---

谢谢！还要注意，可能会有多个具有匹配键和值的对（例如，多个（'b'，15）对），因此您可能不希望在找到第一个命中后中断。还要注意，使用multimap时，显然erase()函数不会使其他迭代器无效（除了被删除的迭代器），因此您可以继续迭代（或者至少这是我从这个页面上获得的信息：http://www.cplusplus.com/reference/map/multimap/erase/）。 - Jamin Grey

您可以继续迭代，但实际上已经被擦除的迭代器已经失效，因此您需要先获取到下一个元素的迭代器。 - Charles Salvia

如果所有的键都相同，这不会导致线性复杂度吗？例如，假设我们插入以下键值对 - ('k', 1), ('k', 2), ('k', 3), ('k', 4)现在，如果我想删除键值对 ('k', 4)，我将循环遍历所有键值对，直到找到 ('k', 4)。 - Gautham

@Gautham 我会查看boost bimap或multiindex是否可以高效地完成它，我相信可以。我本来想尝试创建一个示例，但现在我没有耐心去与Boost文档斗争了。 - Ciro Santilli OurBigBook.com

Answer 2

如果您需要在首次匹配后继续迭代，则需要先检索到下一个元素的迭代器，因为已擦除的迭代器将无效。

从C++11开始，一种实现方法是使用erase函数的返回值，该返回值是指向上一个被删除元素之后的元素的迭代器（如果最后一个元素已被删除，则为multimap::end）。请注意，基于键的版本返回被删除元素的数量，而不是迭代器。

在有价值的Charles Salvia回答的基础上，展示如何擦除(b, 15)对，您可以得到以下代码：

multimap<char,int> mymap;

mymap.insert(pair<char,int>('a',10));
mymap.insert(pair<char,int>('b',15));
mymap.insert(pair<char,int>('b',20));
mymap.insert(pair<char,int>('c',25));

typedef multimap<char, int>::iterator iterator;
std::pair<iterator, iterator> iterpair = mymap.equal_range('b');

// Erase (b,15) pair
//
iterator it = iterpair.first;
for (; it != iterpair.second; ) {
    if (it->second == 15) { 
        it=mymap.erase(it);
    }
    else
        ++it;
}

- Paz