The simple solution is to iterate the vector and for each statement, we delete all its duplications from the vector if present. You can either write your own routine for this or use the std:: remove algorithm that makes the code elegant.
Time complexity:
This approach takes the constant space but runs in O(n^2) time.
Example code:
You can use the additional set to mark the unique values.
#include <iostream>
#include <algorithm>
#include <vector>
template <typename ForwardIterator>
ForwardIterator remove_duplicates( ForwardIterator first, ForwardIterator last )
{
auto new_last = first;
for ( auto current = first; current != last; ++current )
{
if ( std::find( first, new_last, *current ) == new_last )
{
if ( new_last != current ) *new_last = *current;
++new_last;
}
}
return new_last;
}
int main()
{
std::vector<int> v = { 1, 3, 2, 1, 4, 3 };
for ( int x : v ) std::cout << x << ' ';
std::cout << std::endl;
v.erase( remove_duplicates( v.begin(), v.end() ), v.end() );
for ( int x : v ) std::cout << x << ' ';
std::cout << std::endl;
return 0;
}
Output:
The output of the above code is ;
1 3 2 1 4 3
1 3 2 4
