Efficient way to remove duplicates in a multimap?

Question

What is the best way to remove duplicates in a large multimap in C++? For instance, I have a multimap, key <1,4> with its value 9 appears twice, how to get rid of it quickly? Thanks

...
<1,2> --> 3
<1,3> --> 7
<1,4> --> 9
<1,4> --> 9
...

I want it to to be

...
<1,2> --> 3
<1,3> --> 7
<1,4> --> 9
...

What map are you using? `std::map` doesn't allow duplicates. — chris, Mar 05 '14 at 05:24
the decision on what you're *keeping* from the duplicates in a multimap would seem somewhat important to address first. If you want the last item inserted for each distinct key in the multimap, just copy it. Is the *value* identical for each identical key ? — WhozCraig, Mar 05 '14 at 05:26
can you be more clear on exactly what you want to remove, what counts as a "duplicate" in your mind — Cheers and hth. - Alf, Mar 05 '14 at 05:30
Sorry newbie here. Since `<1,4> --> 9` appear twice, they are exactly the same, why should I care which one to be removed? — Daniel, Mar 05 '14 at 05:32
Looks like you want to have multiple values, but just not duplicates so why not use map and save the values themselves in set — , Mar 05 '14 at 05:50
**Advice:** resolve the source issue, why is this item added twice to the list in the first place ? What you're asking for is a work-around, which is worse than having an Error in your code .. since it will conceal a deep issue that you won't be able to resolve later — Khaled.K, Mar 05 '14 at 06:04

score 2 · Answer 1 · answered Nov 23 '16 at 00:02

You can use "set".

map<Point, set<int>> mymap;
mymap[1,2].insert(3);
mymap[1,3].insert(7);
mymap[1,4].insert(9);
mymap[1,4].insert(9);
//Print result.
for(auto itr = mymap.begin(); itr!=mymap.end(); itr++) {
  cout<<itr->first.x<<" "<< itr->first.y<<" ";
  for(set<int>::iterator vitr = itr->second.begin(); vitr != itr->second.end(); vitr++){
      cout<<(*vitr) +1<<" ";
  }
cout<<endl;
}

score 1 · Answer 2 · answered Mar 05 '14 at 05:56

One approach that would take O(n) time is to copy your original map to a new map. For example,

multimap<T,U> original_map; 
multimap<T,U> new_map; 

while (original_map.size() > 0) 
{ 
    auto element = *(original_map.begin()); 
    new_map.insert(make_pair(element.first,element.second)); 
    original_map.erase(element.first); 
}

NOTE: This is assuming that criteria for duplicate entries are entries having only the same key.

score 1 · Answer 3 · edited May 23 '17 at 12:07

1

this Erasing elements in a multimap while iterating is similar to what you are asking. Here is the in-place solution without additional allocations.

if (mymap.size() > 1) {
  auto prev_key = mymap.begin()->first;
  auto it = mymap.begin(); 
  for (++it; it != mymap.end();) {
    if (it->first == prev_key) {
      it = mymap.erase(it);
    } else {
      prev_key = it->first;
      ++it;
   }
}

edited May 23 '17 at 12:07

Community

1
1

answered Mar 05 '14 at 11:12

Roman

1,351
11
26

1

Just a note/caution: this erases entries where keys match, regardless of whether their values match. It's unclear from the question whether that's what's wanted, or only duplicates for both key and value should be erased. – Tony Delroy May 12 '18 at 02:48
1

I agree with Tony Delroy, this answer doesn't remove only duplicate, but all key duplicate. Better to use a map in this case. – Kafka Feb 04 '21 at 10:51

Efficient way to remove duplicates in a multimap?

3 Answers3