Как я могу удалить указанные c дубликаты из мультикарты?

Question

У меня есть мультикарта с дубликатами (дублирующими ключами), из которой я хотел бы удалить все дубликаты, кроме того, который был недавно добавлен к мультикарте.

Допустим, у меня есть

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

Я перебрал эту карту, и она выглядит так:

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

Теперь мне нравится удалять дубликаты 1 : 1 и 1 : 12, потому что последняя добавленная пара была 1 : 888. Также удалите 2 : 500, поскольку 2 : 789 был недавно добавлен на карту.

Но как я могу это сделать? Я попытался поместить каждый элемент этой мультикарты в карту нормалей, потому что он сам удаляет дубликаты. Проблема в том, что он не сохраняет самую последнюю добавленную копию: c

Answer 1

Вместо этого вы можете использовать std::map, потому что это:

... отсортированный ассоциативный контейнер, содержащий пары ключ-значение с уникальными ключами.

std::map::insert не будет работать, потому что:

... вставляет элемент (-ы) в контейнер, если контейнер еще не содержит элемент с эквивалентным ключом.

Однако вы можете обойти это поведение, используя вместо этого operator[], поскольку он не выполняет проверку, существует ли ключ.

Путем выполнения следующие только последние значения будут сохранены на карте:

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

Теперь std::map будет выглядеть так:

1 888
2 789

ОБНОВЛЕНИЕ

Если вы можете использовать C ++ 17, вы можете использовать std::map::insert_or_assign, который делает то же самое, что и operator[] до C ++ 17.

Вы можете использовать его как:

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

, и результат будет таким же.

Answer 2

Вы можете сделать это, например, следующим образом

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

Вывод программы:

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

Если вы хотите создать копию с уникальными ключами, вы можете использовать стандартный алгоритм std::unique_copy. Например

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

Вывод программы такой же, как показано выше

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