How to remove a specific pair from a 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));

Say I now want to remove one of the pairs I have just added to the map.

I have examples to remove an entire key entry, which for key 'b' would remove both 'b',15 and 'b',20.

But what is the code to remove just, say, the pair 'b',20?

Charles Salvia · Accepted Answer · 2010-10-17T08:23:23.873

50

You can use std::multimap<char, int>::equal_range, which will give you an iterator range containing all pairs which have a certain key. So if you look for 'b', you will get an iterator range containing all pairs which have 'b' as the key.

You can then simply iterate over the range, and erase any pair you see fit, by erasing the iterator.

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

edited Oct 17 '10 at 08:23

answered Oct 17 '10 at 08:00

Charles Salvia

52,325
13
128
140

1

Thanks for this! Also note that there can be more than one pair that has matching key AND value (e.g. more than one ('b',15) pair), so you might not want to break after finding only the first hit. Also note that with multimap, apparently the erase() function doesn't invalidate other iterators (except the erased iterator), so you can keep on iterating (or at least that's what I gather from this page: http://www.cplusplus.com/reference/map/multimap/erase/) – Jamin Grey May 18 '13 at 19:27
3

You can keep on iterating yes, but the actual erased iterator is invalidated, so you need to first retrieve an iterator to the next element. – Charles Salvia May 21 '13 at 17:07
2

Won't this turn out to have linear complexity if all the keys are same? For example, let's say we insert the following pairs - ('k', 1), ('k', 2), ('k', 3), ('k', 4) Now, if I want to delete the pair ('k', 4), I'll be looping through all the pairs till I find ('k', 4). – Gautham May 06 '18 at 14:34
@Gautham I would look if boost bimap or multiindex can do it efficiently, I believe yes. I was going to try to create an example, but I don't have the patience to fight Boost docs now. – Ciro Santilli OurBigBook.com Jan 08 '20 at 17:40

score 5 · Answer 2 · answered Feb 01 '21 at 11:26

In case you need to continue iterating after the first match you need to first retrieve an iterator to the next element since the erased iterator gets invalidated.

One way to achieve this, starting from C++11, is to use the return value of the erase function which is an iterator to the element that follows the last element removed (or multimap::end, if the last element was removed). Beware the key based version returns the number of elements erased, not an iterator.

Building on top of the valuable Charles Salvia answer, showing how to erase (b,15 ) pair, you get

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

How to remove a specific pair from a C++ multimap?

2 Answers2

Linked