How to remove / erase duplicate elements from std :: vector while maintaining order?

Question

Is there a way to remove duplicate elements from a vector container containing string elements while maintaining order.

So far I have used the set method, but it does not preserve order.

I do not know how to use remove_if in relation to this problem.

Answer 1

How to use a temporary container:

std::vector< int >::iterator i , j ; std::set< int > t_set; for( i = v.begin() , j = v.begin() ; i != v.end() ; ++i ) if( t_set.insert( *i ).second) *j++ = *i ; v.erase( j , v.end() ); 

Using std::remove_if , I can think of this:

 std::set<int> t_set; std::vector<int> res; //Resultant vector remove_copy_if(v.begin(), v.end(), std::back_inserter(res), [&t_set](int x){ return !t_set.insert(x).second; } ); 

Answer 2

You can create an empty array, then iterate over the original vector and only copy the first instance of each element in the vector. You can monitor whether you have seen an element in the vector by adding it to the set and checking for the presence of elements in the set before adding it to the new array.

Answer 3

You can do it:

  std::vector<int> v = { 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 8 }; // 1 2 2 3 4 5 6 7 8 9 8 for(size_t i=0;i<v.size();i++) { for(size_t j=0;j<v.size();j++) { if(v[i] == v[j] && i != j) { v.erase(v.begin()+j); j--; // Fix for certain datasets ie: } // 1 2 1 1 } } // Produces: // 1 2 3 4 5 6 7 8 9 

Answer 4

A simple solution

 std::vector<int>::iterator it; it = std::unique (myvector.begin(), myvector.end()); 

This iterator will point to the item next to the last item. You cannot use this iterator if it is not required.

See THIS for further reference.

EDIT:

Since I thought the vector would be sorted, a new solution could be:

  vector<int> vec= {5,1,2,3,5,4,2,1,1,4,3,2,4,5,2,1,3,5,2,3,5,2,3,2,3,5,2,1,3}; set<int> s; vector<int>::iterator vecIter=vec.begin(); vector<int>::iterator vecIterCopy; for(;vecIter!=vec.end(); vecIter++) { if(s.find(*vecIter)==s.end()) { s.insert(*vecIter); *vecIterCopy++ = *vecIter; } } 

Answer 5

O (n * log (n)) solution:

 vector<string> V={"aa","bb","aa","cc","cc"}; set<string> S; auto i=V.begin(); auto j=i; for(; i!=V.end(); ++i) { if(S.insert(*i).second && i!=j++) *j = std::move(*i); } V.erase(j,V.end()); 

Also changed version of POW from std::remove_copy_if . But here without extraneous times:

 set<string> S; V.erase( copy_if( make_move_iterator(V.begin()), make_move_iterator(V.end()), V.begin(), [&](const string& x){ return S.insert(x).second;} ), V.end() );