How to remove duplicates from unsorted std::vector while keeping the original ordering using algorithms?
Sounds like a job for std::copy_if. Define a predicate that keeps track of elements that already have been processed and return false if they have.
If you don't have C++11 support, you can use the clumsily named std::remove_copy_if and invert the logic.
This is an untested example:
template <typename T>
struct NotDuplicate {
bool operator()(const T& element) {
return s_.insert(element).second; // true if s_.insert(element);
}
private:
std::set<T> s_;
};
Then
std::vector<int> uniqueNumbers;
NotDuplicate<int> pred;
std::copy_if(numbers.begin(), numbers.end(),
std::back_inserter(uniqueNumbers),
std::ref(pred));
where an std::ref
has been used to avoid potential problems with the algorithm internally copying what is a stateful functor, although std::copy_if
does not place any requirements on side-effects of the functor being applied.
The naive way is to use std::set
as everyone tells you. It's overkill and has poor cache locality (slow).
The smart* way is to use std::vector
appropriately (make sure to see footnote at bottom):
#include <algorithm>
#include <vector>
struct target_less
{
template<class It>
bool operator()(It const &a, It const &b) const { return *a < *b; }
};
struct target_equal
{
template<class It>
bool operator()(It const &a, It const &b) const { return *a == *b; }
};
template<class It> It uniquify(It begin, It const end)
{
std::vector<It> v;
v.reserve(static_cast<size_t>(std::distance(begin, end)));
for (It i = begin; i != end; ++i)
{ v.push_back(i); }
std::sort(v.begin(), v.end(), target_less());
v.erase(std::unique(v.begin(), v.end(), target_equal()), v.end());
std::sort(v.begin(), v.end());
size_t j = 0;
for (It i = begin; i != end && j != v.size(); ++i)
{
if (i == v[j])
{
using std::iter_swap; iter_swap(i, begin);
++j;
++begin;
}
}
return begin;
}
Then you can use it like:
int main()
{
std::vector<int> v;
v.push_back(6);
v.push_back(5);
v.push_back(5);
v.push_back(8);
v.push_back(5);
v.push_back(8);
v.erase(uniquify(v.begin(), v.end()), v.end());
}
*Note: That's the smart way in typical cases, where the number of duplicates isn't too high. For a more thorough performance analysis, see this related answer to a related question.
Fast and simple, C++11:
template<typename T>
size_t RemoveDuplicatesKeepOrder(std::vector<T>& vec)
{
std::set<T> seen;
auto newEnd = std::remove_if(vec.begin(), vec.end(), [&seen](const T& value)
{
if (seen.find(value) != std::end(seen))
return true;
seen.insert(value);
return false;
});
vec.erase(newEnd, vec.end());
return vec.size();
}