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...

https://stackoverflow.com/questions/2769174/determining-if-an-unordered-vectort-has-all-unique-elements — Edgar Rokjān, Aug 22 '18 at 09:57
@EdgarRokjān: I suppose this means the answer is "No there isn't"...;-) — jpo38, Aug 22 '18 at 09:59
Such a function would be O(n^2), that's probably why there is none. — alain, Aug 22 '18 at 09:59
@alain Do you mean naive implementation? For with additional hashset it runs in average O(N), with O(N) space. — bipll, Aug 22 '18 at 10:03
@JesperJuhl That is one option, not the best in time but the best in space, albeit destructive. — bipll, Aug 22 '18 at 10:04
Possible duplicate of [Determining if an unordered vector has all unique elements](https://stackoverflow.com/questions/2769174/determining-if-an-unordered-vectort-has-all-unique-elements) — Arne Vogel, Aug 22 '18 at 13:18

score 4 · Answer 1 · answered Aug 22 '18 at 10:22

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()));
}

score 2 · Answer 2 · edited Aug 22 '18 at 10:22

2

The only thing I can thing is https://en.cppreference.com/w/cpp/algorithm/adjacent_find, but it requires that the elements are sorted as it will check in the adjacent element.

EDIT:

There is no stl algorithm that can do that as you ask, the other alternative is use std::any_of.

edited Aug 22 '18 at 10:22

jpo38

20,821
10
70
151

answered Aug 22 '18 at 10:06

Ch1v1

121
1
7

1

I'm not asking how to "check if a container has duplicates"....there's many ways to do that (using adjacent_find is one of them). I'm looking for a function taking two iterators and returning true/false.... – jpo38 Aug 22 '18 at 10:08
Then I will say there are any like you are looking for. – Ch1v1 Aug 22 '18 at 10:13

score 2 · Accepted Answer · answered Aug 22 '18 at 10:43

2

STL is about efficiency and universality. There seems to be no universal and efficient way to check if a container has duplicates without modifying it. Hence, no wonder that no such algorithm exists in STL.

answered Aug 22 '18 at 10:43

Evg

25,259
5
41
83

1

Err, `unordered_set` would work fine in most cases and gives average O(n) complexity (requires hash and equality comparison, and possibly copy c'tor). Another possibility with worst case O(n log n) complexity, for forward iterator ranges, is to make a vector of iterators or pointers and sort these (requires less-than-comparable type). A generic solution has to allocate O(N) additional memory, though, and impose certain constraints on types, which is the more likely reason there is no such algorithm yet. – Arne Vogel Aug 22 '18 at 13:27

PilouPili · Answer 4 · 2018-08-22T10:22:21.310

0

One way of doing this is to use std::set.

Copy your vector into the set and compare if the number of elements are the same.

If yes you have no duplicate, if no you can guess the number of duplicates.

#include <iostream>
#include <iterator>
#include <vector>
#include <set>
int has_duplicate(const std::vector<int> & v)
{
    std::set<int> s(v.begin(), v.end());
    return v.size() - s.size();
}

int
main()
{

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

for v1 the output is 0 -> you have no duplicate for v2 the output is 1 -> you have one duplicate

The algorithm costs O(N*log(N))

edited Aug 22 '18 at 10:22

answered Aug 22 '18 at 10:16

PilouPili

2,601
2
17
31

You could simplify by passing the iterators directly into the constructor of the set. – eerorika Aug 22 '18 at 10:18
1

That's what I said in the "Note" of my question. – jpo38 Aug 22 '18 at 10:21

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

4 Answers4