Determine if there are duplicates in vector

Question

I would like to determine if there are duplicates in a vector. What is the best option here?

sort(arrLinkToClients.begin(), arrLinkToClients.end(), [&](const type1& lhs,const type1& rhs)
{
    lhs.nTypeOfLink < rhs.nTypeOfLink;
});

auto it = unique(arrLinkToClients.begin(), arrLinkToClients.end(), [&](const type1& lhs, const type1& rhs)
{
    lhs.nTypeOfLink == rhs.nTypeOfLink;
});

//how to check the iterator if there are duplicates ?
if (it)
{
  //
}

Possible duplicate of [Checking for duplicates in a vector](https://stackoverflow.com/questions/2860634/checking-for-duplicates-in-a-vector) — Udayraj Deshmukh, Mar 13 '18 at 09:47
If the question is only "are there **any** duplicates", `std::unique` is overkill, since it removes **all** duplicates. That's why you're getting answers that suggest `std::adjacent_find`, which returns when it finds the first duplicate. — Pete Becker, Mar 13 '18 at 12:41
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). Note that the question @UdayrajDeshmukh linked is marked as a duplicate of the question I link. — Graham, Jan 26 '19 at 00:11

score 6 · Accepted Answer · edited Jun 20 '20 at 09:12

The "best" option does not exist. It depends on how you define "best".

Here are some solutions, each with their own advantages and disadvantages:

Using map

template <class T>
auto has_duplicates(const std::vector<T>& v) -> bool
{
    std::unordered_map<T, int> m;

    for (const auto& e : v)
    {
        ++m[e];

        if (m[e] > 1)
            return true;
    }
    return false;
}

Using set

template <class T>
auto has_duplicates(const std::vector<T>& v) -> bool
{
    std::unordered_set<int> s;
    std::copy(v.begin(), v.end(), std::inserter(s, s.begin());
   
    return v.size() != s.size();
}

Using sort and adjacent_find (mutating range)

template <class T>
auto has_duplicates(std::vector<T>& v) -> bool
{
    std::sort(v.begin(), v.end());

    return std::adjacent_find(v.begin(), v.end()) != v.last();
}

Manual iteration with std::find

template <class T>
auto has_duplicates(const std::vector<T>& v) -> bool
{
    for (auto it = v.begin(); it != v.end(); ++it)
        if (std::find(it + 1, v.end(), *it) != v.end())
            return true;
            
    return false;
}

Manual iteration

template <class T>
auto has_duplicates(const std::vector<T>& v) -> bool
{
    for (auto i1 = v.begin(); i1 != v.end(); ++i1)
        for (auto i2 = i1 + 1; i2 != v.end(); ++i2)
            if (*i1 == *i2)
                return true;
    
    return false;
}

score 1 · Answer 2 · answered Mar 13 '18 at 09:50

1

If there are no duplicates, the iterator returned from unique is the end iterator. So:

if (it != arrLinkToClients.end())
    cout << "Some duplicates found!";

answered Mar 13 '18 at 09:50

jrok

54,456
9
109
141

The return value is a forward iterator to the new end of the range, so you cannot do this. – 0xBADF00 Mar 13 '18 at 10:10
@0xBADF00 -- the iterator returned by `std::unique` has the same type as the iterators that the function was called with. There's nothing wrong with this comparison. – Pete Becker Mar 13 '18 at 12:37
@PeteBecker Ok my bad, ofcourse you can do that, but it will not accomplish what the OP wanted. – 0xBADF00 Mar 13 '18 at 13:06
@0xBADF00 — it looks okay to me. Why do you say that it won’t work? – Pete Becker Mar 13 '18 at 15:00
@PeteBecker Ok I am obviously stupid it works great (did not think of the sort) – 0xBADF00 Mar 13 '18 at 15:08

Determine if there are duplicates in vector

2 Answers2

Linked