How can I remove specific duplicates from a multimap?

user_6275216 0
Viewed 287

I have a multimap with duplicates (duplicate keys) from which I like to delete every duplicate except for the one that was recently added to the multimap.

Let's say I have

multimap<int, int> multi;
multi.insert(pair<int, int>(1, 1));
multi.insert(pair<int, int>(1, 12));
multi.insert(pair<int, int>(2, 500));
multi.insert(pair<int, int>(2, 789));
multi.insert(pair<int, int>(1, 888));

I have iterated over this map and it looks like this:

1 : 1
1 : 12
1 : 888
2 : 500
2 : 789

Now I like to have the duplicates removed 1 : 1 and 1 : 12 because the last added pair was 1 : 888. Also remove 2 : 500 because 2 : 789 was most recently added to the map.

But how can I do this? I have tried to put each element of this multimap into a normal map because it's removing duplicates by itself. The problem is that it doesn't keep the most recently added duplicate :c

data-structures c++11 dictionary algorithm c++
2 Answers

You can use std::map instead because it is:

... a sorted associative container that contains key-value pairs with unique keys.

std::map::insert won't work because it:

... inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key.

However, you can workaround this behavior by using operator[] instead because it doesn't perform check whether key already exists.

By doing the following only the last value will be kept in the map:

#include <map>
#include <iostream>

int main() {
    std::map<int, int> my;
    my[1] = 1;
    my[1] = 12;
    my[2] = 500;
    my[2] = 789;
    my[1] = 888;
    return 0;
}

Now, the std::map would look like:

1 888
2 789

UPDATE

If you are able to use C++17, you can make a use of std::map::insert_or_assign that does the same thing as operator[] prior C++17.

You can use it like:

std::map<int, int> my;
my.insert_or_assign(1, 1);
my.insert_or_assign(1, 12);
my.insert_or_assign(2, 500);
my.insert_or_assign(2, 789);
my.insert_or_assign(1, 888);

and the result would be the same.

user_55173780

You can do it for example the following way

#include <iostream>
#include <map>
#include <iterator>

int main() 
{
    std::multimap<int, int> multi;
    multi.insert( { 1, 1 } );
    multi.insert( { 1, 12 } );
    multi.insert( { 2, 500 } );
    multi.insert( { 2, 789 });
    multi.insert( { 1, 888 } );

    for ( const auto &item : multi )
    {
        std::cout << "{ "  << item.first << ", " << item.second << " } ";
    }

    std::cout << '\n';

    if ( !multi.empty() )
    {
        for ( auto prev = std::begin( multi ), 
                   next = std::begin( multi ),  
                   last = std::end( multi );  
              ++next != last; )
        {
            if ( next->first == prev->first ) prev = multi.erase( prev );
            else ( ++prev );
        }             
    }

    for ( const auto &item : multi )
    {
        std::cout << "{ "  << item.first << ", " << item.second << " } ";
    }

    std::cout << '\n';

    return 0;
}

The program output is

{ 1, 1 } { 1, 12 } { 1, 888 } { 2, 500 } { 2, 789 } 
{ 1, 888 } { 2, 789 }

If you want to create a copy with unique keys then you can use the standard algorithm std::unique_copy. For example

#include <iostream>
#include <map>
#include <iterator>
#include <algorithm>

int main() 
{
    std::multimap<int, int> multi;
    multi.insert( { 1, 1 } );
    multi.insert( { 1, 12 } );
    multi.insert( { 2, 500 } );
    multi.insert( { 2, 789 });
    multi.insert( { 1, 888 } );

    for ( const auto &item : multi )
    {
        std::cout << "{ "  << item.first << ", " << item.second << " } ";
    }

    std::cout << '\n';
    std::multimap<int, int> multi2;

    std::unique_copy( std::rbegin( multi ), std::rend( multi ),
                      std::inserter( multi2, std::end( multi2 ) ),
                      []( const auto &a, const auto &b ) 
                      { 
                         return a.first == b.first ; 
                      } );

    for ( const auto &item : multi2 )
    {
        std::cout << "{ "  << item.first << ", " << item.second << " } ";
    }

    std::cout << '\n';

    return 0;
}

The program output is the same as shown above

{ 1, 1 } { 1, 12 } { 1, 888 } { 2, 500 } { 2, 789 } 
{ 1, 888 } { 2, 789 }
user_28772410
Related