c++algorithmvectoriteratorerase-remove-idiom

Remove duplicate elements from std::vector but starting from the front?


How can I delete duplicate elements from a vector but starting from the front?

So

2 3 4 5 2 5 would become 3 4 2 5

1 5 3 1 would become 5 3 1

I would like the solution to be easy to read, and it would be nice if it had good performance as well.


Solution

  • If a container supports bidirectional iterators then it is unimportant from which side of the container you are trying to remove duplicate elements because you can use reverse iterators.

    Here is a demonstrative program.

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

    The program output is

    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