C++/STL which algorithm should I use to check if a container has duplicates?

Question

Is there any STL algorithm that would tell if a container has duplicated elements (using the operator== or a given predicate)?

Let's consider those two vectors:

std::vector<int> v1{ 1, 2, 3 };
std::vector<int> v2{ 1, 2, 1 };

I would expect a function like that:

std::is_exclusive( v1.begin(), v1.end() ); // returning true
std::is_exclusive( v2.begin(), v2.end() ); // returning false

Is there such a simple function? I could not find any (found std::unique, but this modifies the vector...)

Note: I'm not asking how to "check if a container has duplicates", I know how I can do that (basically, I can do ( std::set<int>( v1.begin(), v1.end() ).size() == v1.size() ) and there may exist many other options. I'm asking if there is a STL algorithm function that would do it in a smarter way because I'm surprised I could not find any...

Answer 1

One way of implementing your STL-like is_exclusive template function would be by using a std::unordered_map which keeps the counting of the elements in the range. The function template could return false as soon as the count for any element is over one:

#include <unordered_map>

template<typename ForwardIt>
bool is_exclusive(ForwardIt first, ForwardIt last) {
    std::unordered_map<typename ForwardIt::value_type, unsigned> count;

    for (auto it = first; it != last; ++it)
        if (++count[*it] > 1)
            return false;

    return true;
}

For your example:

int main() {
    std::vector<int> v1{ 1, 2, 3 };
    std::vector<int> v2{ 1, 2, 1 };


    assert(is_exclusive(v1.begin(), v1.end()));
    assert(!is_exclusive(v2.begin(), v2.end()));
}