Eliminate duplicate elements from a container

(Reader Level : Intermediate)
(Knowledge assumptions : templates, STL)

One of the grandest things about STL is that it keeps us from re-inventing the wheel. In a practical world, it just doesn't make sense for a developer to create a doubly linked list or a queue from scratch. We have STL containers for that purpose. However, with great knowledge comes great responsibility. Its important to know what STL does under the hood, rather than just using it blindly. A lot of books out there have covered this topic but one of the most important ones that springs immediately to mind is The C++ Standard Library - A Tutorial and Reference by Nicolai M. Josuttis.

Enough of the prologue... Let's get down to a problem. There are times when one might have a container with duplicate element values. Whether such a scenario is justifiable or not may depend on a number of things. The first thing, we need to look into is the container itself and ask ourselves - "Is this the right container for the job? Why not use an std::set or an std::map instead?" If redesigning our code to use a more suitable container isn't a viable solution, then read on.

template<class ContainerType>
void RemoveDuplicates( ContainerType& input )
{
 ContainerType::iterator currentPosIter = input.begin();
 currentPosIter;

 for( ContainerType::iterator iter = input.begin(); iter != input.end(); ++iter )
 {
   if( std::find( input.begin(), currentPosIter, *iter ) == currentPosIter )
   { 
     *currentPosIter = *iter;
     ++currentPosIter;
   }
 }

 input.erase(currentPosIter, input.end() );
}

The above function removes duplicates from any STL container as long as that container supports an erase method. Let's take it for a test drive, shall we?

std::deque<int> myDeque;

//Add some values to the deque.
myDeque.push_back(0);
myDeque.push_back(1);
myDeque.push_back(1);
myDeque.push_back(0);
myDeque.push_back(2);
myDeque.push_back(2);
myDeque.push_back(3);
myDeque.push_back(1);

//Before erasing duplicates.
std::cout << "Before erasing duplicates." << "\n";
std::copy( myDeque.begin(), myDeque.end(), std::ostream_iterator<int>( std::cout, "\n" ) );
std::cout << "\n\n";

RemoveDuplicates<std::deque<int> >( myDeque );

//After erasing duplicates.
std::cout << "After erasing duplicates." << "\n";
std::copy( myDeque.begin(), myDeque.end(), std::ostream_iterator<int>( std::cout, "\n" ) );