Допустим есть контейнер, содержащий элементы
{ 1, 2, 3, 4, 5, 4, 3, 2, 1 }
Нужно из этого контейнера удалить дублирующиеся элементы (не меняя порядок следования элементов) кроме последних дублирующихся элементов, то есть в итоге получить контейнер, содержащий элементы
{ 5, 4, 3, 2, 1 }
Добавление в задание условия сохранения последних дублирующихся элементов, а не первых, на первый взгляд усложняет задание, и, порой, у программистов (не только начинающих) вызывает сложности по сравнению с условием сохранения первых дублирующихся элементов.
На самом деле достаточно написать функцию/алгоритм, который удаляет дублирующиеся элементы кроме первых дублирующихся элементов, а затем просто использовать реверсивные итераторы при условии, конечно, что контейнер поддерживает реверсивные итераторы!
Вот как может выглядеть соответствующий алгоритм.
template <typename ForwardIterator>
ForwardIterator remove_duplicates( ForwardIterator first, ForwardIterator last )
{
for ( ; first != last; ++first )
{
last = std::remove( std::next( first ), last, *first );
}
return last;}
Ниже приведена демонстрационная программа с использованием контейнера
std::vector<int>.
Сначала в программе показано, как использовать алгоритм для удаления дублирующихся элементов кроме первых дублирующихся элементов. А затем демонстрируется, как удалить дублирующиеся элементы кроме последних дублирующихся элементов с помощью реверсивных итераторов.
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
template <typename ForwardIterator>
ForwardIterator remove_duplicates( ForwardIterator first, ForwardIterator last )
{
for ( ; first != last; ++first )
{
last = std::remove( std::next( first ), last, *first );
}
return last;
}
int main()
{
std::vector<int> v = { 1, 2, 3, 4, 5, 4, 3, 2, 1 };
for ( const auto &item : v ) std::cout << item << ' ';
std::cout << '\n';
v.erase( remove_duplicates( std::begin( v ), std::end( v ) ), std::end( v ) );
for ( const auto &item : v ) std::cout << item << ' ';
std::cout << '\n';
std::cout << '\n';
v.assign( { 1, 2, 3, 4, 5, 4, 3, 2, 1 } );
for ( const auto &item : v ) std::cout << item << ' ';
std::cout << '\n';
v.erase( std::begin( v ), remove_duplicates( std::rbegin( v ), std::rend( v ) ).base() );
for ( const auto &item : v ) std::cout << item << ' ';
std::cout << '\n';
}
Вывод программы на консоль:
1 2 3 4 5 4 3 2 1
1 2 3 4 5
1 2 3 4 5 4 3 2 1
5 4 3 2 1