Removing duplicates in an array while preserving the order in C++

Question

Possible Duplicate:
How to make elements of vector unique? (remove non adjacent duplicates)

Is there any standard algorithm which is provided as part of STL algorithms which can remove duplicates from an array while preserving the order. For example, if I have an array like int a[] = {2,1,3,1,4,2}; after the removal of duplicates it should be a[] = {2,1,3,4};. I can not use std::unique as the array is not sorted. Other solutions like inserting it into an std::set I lose the order as the elements will get sorted. Is there any other combination of algorithms I can use or do I have to code my own?

Answer 1

Since the problem is relatively "complex", I wouldn't try to force a solution by using standard algorithms only (since there is no special algorithm to solve your problem. You could probably hack something with remove_if, find and bind2nd or something). For implementing the algorithm yourself, you have basically two options, with the usual memory vs. speed tradeoff. The first solution would be to iterate the vector and search and remove duplicates for the current item. This is the cpu-intensive approach. A maybe faster approach would be creating a second vector (of the same size as the first to minimize memory reallocations) and storing the found items in there. Then, for each iteration of the original vector, only the shorter second vector needs to be searched through to find out whether the current item should be deleted or not. The first approach works with every iterator, while the second is limited to random access iterators. Here are the implementations:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

template<typename T>
void remove_duplicates_ordered_mem_intensive(T &container)
{
   std::vector<typename T::value_type> items;
   items.reserve (container.size());

   typename T::iterator i = container.begin();
   while (i != container.end())
   {
      if (find (items.begin(), items.end(), *i) != items.end())
         i = container.erase(i);
      else
      {
         items.push_back(*i);
         ++i;
      }
   }
} 

template<typename T>
void remove_duplicates_ordered_slow(T &container)
{
   typename T::iterator i = container.begin();
   while (i != container.end())
   {
      typename T::iterator f = i;
      ++f;
      while (f != container.end())
      {
         if (*f == *i)
            f = container.erase(f);
         else
            ++f;
      }
      ++i;
   }
} 

int main ()
{
   vector<int> v;
   v.push_back (2);
   v.push_back (1);
   v.push_back (3);
   v.push_back (1);
   v.push_back (4);
   v.push_back (2); 

   cout << "Old:\n";
   for (vector<int>::const_iterator i = v.begin(); i != v.end(); ++i)
      cout << *i << endl;


   vector<int> a (v), b (v);
   remove_duplicates_ordered_mem_intensive (a);
   remove_duplicates_ordered_slow (b); 

   cout << "\nRemoved duplicates with intensive memory usage:\n";
   for (vector<int>::const_iterator i = a.begin(); i != a.end(); ++i)
      cout << *i << endl; 

   cout << "\nRemoved duplicates somewhat slower, without copying:\n";
   for (vector<int>::const_iterator i = b.begin(); i != b.end(); ++i)
      cout << *i << endl;
}

Answer 2

There is no standard algorithm for this, but it's fairly easy to implement. The principle is to keep a std::set of the items you've seen so far, and skip duplicates while copying to a new vector or array. This operates in O(n lg n) time and O(n) memory. If you're using C++0x, you can get it down to O(n) time by using std::unordered_set for the seen-items set; this uses a hash table instead of binary trees and should be faster.

Answer 3

remove duplicates from an array

This is technically impossible, because arrays cannot change size.