Here's an interesting article called "How to Remove Elements from a Sequence Container in C++". At some point, the author also explains how to remove duplicates from a container, but only with the very restrictive condition that those duplicates are adjacent. I've given a bit of thoughts on how to make a generic algorithm that would work on any duplicate in the container, and it's a bit more complicated that one might think at first.
The naively obvious solution is:
template <typename Iterator>
Iterator remove_duplicates(Iterator first, Iterator last) {
auto it = std::next(first);
while (first != last) {
it = std::find(it, last, *first);
if (it == last) it = std::next(++first);
else std::rotate(it, std::next(it), last--);
}
return last;
}
and it looks a lot like an implementation of a STL's algorithm, but it also is a polynomial-time algorithm, which is only acceptable if there is no alternative. But you generally keep track of already encountered values in a separate container in order to attain linear or almost-linear time. Sets are good candidates but they come in two flavors, and the std::unordered_set
being more efficient than the simple std::set
must be used when possible.
I've used concepts (gcc > 6.3 && -fconcepts
) to dispatch to the most efficient overload:
template <typename T>
concept bool Hashable = requires {
std::hash<T>();
};
template <typename T>
concept bool Comparable = requires (T a, T b) {
{ a == b } -> bool;
};
template <typename T>
concept bool Orderable = requires (T a, T b) {
{ a < b } -> bool;
};
unordered_set
s require the key to be hashable and comparable, and set
s that it be orderable. After code factorization it gives:
template <typename Iterator, typename Set>
Iterator remove_duplicates_impl(Iterator first, Iterator last, Set& known_values) {
while (first != last) {
if (known_values.find(*first) != known_values.end()) std::rotate(first, std::next(first), last--);
else known_values.insert(*first++);
}
return last;
}
template <typename Iterator>
Iterator remove_duplicates(Iterator first, Iterator last)
requires Orderable<Value_type<Iterator>> && !Hashable<Value_type<Iterator>>
{
std::set<Value_type<Iterator>> known_values;
return remove_duplicates_impl(first, last, known_values);
}
template <typename Iterator>
Iterator remove_duplicates(Iterator first, Iterator last)
requires Hashable<Value_type<Iterator>> && Comparable<Value_type<Iterator>>
{
std::unordered_set<Value_type<Iterator>> known_values;
return remove_duplicates_impl(first, last, known_values);
}
So what's missing here, be it optimizations or corner-cases handling?
A minimal working example:
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <set>
#include <iterator>
#include <type_traits>
template <typename Iterator>
using Value_type = typename std::iterator_traits<Iterator>::value_type;
template <typename T>
concept bool Hashable = requires {
std::hash<T>();
};
template <typename T>
concept bool Comparable = requires (T a, T b) {
{ a == b } -> bool;
};
template <typename T>
concept bool Orderable = requires (T a, T b) {
{ a < b } -> bool;
};
template <typename Iterator>
Iterator remove_duplicates(Iterator first, Iterator last) {
auto it = std::next(first);
while (first != last) {
it = std::find(it, last, *first);
if (it == last) it = std::next(++first);
else std::rotate(it, std::next(it), last--);
}
return last;
}
template <typename Iterator, typename Set>
Iterator remove_duplicates_impl(Iterator first, Iterator last, Set& known_values) {
while (first != last) {
if (known_values.find(*first) != known_values.end()) std::rotate(first, std::next(first), last--);
else known_values.insert(*first++);
}
return last;
}
template <typename Iterator>
Iterator remove_duplicates(Iterator first, Iterator last)
requires Orderable<Value_type<Iterator>> && !Hashable<Value_type<Iterator>>
{
std::set<Value_type<Iterator>> known_values;
return remove_duplicates_impl(first, last, known_values);
}
template <typename Iterator>
Iterator remove_duplicates(Iterator first, Iterator last)
requires Hashable<Value_type<Iterator>>
{
std::unordered_set<Value_type<Iterator>> known_values;
return remove_duplicates_impl(first, last, known_values);
}
struct Foo {};
bool operator==(Foo, Foo) { return true; }
int main() {
std::vector<int> data{ 1,2,3,4,5,6,7,8,9,8,7,6,5,2,4,3,1,8 };
std::vector<int> unik(data.begin(), remove_duplicates(data.begin(), data.end()));
for (auto i : unik) std::cout << i << ' ';
std::cout << std::endl;
std::vector<std::pair<int, int>> test{ {1,2}, {3,4} , {5,6} , {7,8}, {7, 8} };
[[maybe_unused]]
auto it = remove_duplicates(test.begin(), test.end());
std::vector<Foo> test2{ Foo(), Foo(), Foo() };
[[maybe_unused]]
auto it2 = remove_duplicates(test2.begin(), test2.end());
}
std::rotate
is likely to dominate the work. Two obvious test cases suggest themselves - one with all elements different (e.g. usingstd::iota()
andstd::shuffle()
) and one with all elements identical. Obviously, the timings will depend on the element type, and the cost of its move assignment, so that immediately doubles the test cases to try. \$\endgroup\$ – Toby Speight Sep 19 '18 at 15:43O(n log n)
by usingstd::sort
followed bystd::unique
. That's what I'd go for unless I found that it was causing a problem \$\endgroup\$ – Justin Sep 19 '18 at 19:30