First duplicate in a vector

user_15933749 0
Viewed 101

I have the following code that finds first duplicate in a vector of integers:

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int find_duplicate(const vector<int> &v)
{
    unordered_set<int> numbers;
    
    for(const auto num : v)
    {
        if (numbers.count(num) > 0)
        {
            return num;
        }
        else
        {
            numbers.insert(num);
        }
    }
    
    return -1;
}

int main()
{
    std::vector<int> v = {1, 3, 4, 5, 3, 2, 3, 6, 2};
    cout << find_duplicate(v);
    return 0;
}

I am wondering if there is a more concise way of writing this using C++ std library algorithms?

find_duplicate should not modify the input vector nor make a copy of it.

c++17 c++
1 Answers

The C++ standard library is built around iterators rather than indices. If you change your find_duplicate function to return an iterator, this can be concisely written as:

auto find_duplicate(const vector<int> &v)
{
    unordered_set<int> numbers;

    return std::find_if(v.begin(), v.end(),
        [&](int num) { return !numbers.insert(num).second; });
}

Note that unordered_set<T>::insert returns a pair<iterator, bool>, where the bool is true if we inserted a new element and false if the element was already in the set.

Whether this is good code is debatable. A common expectation when reading code using standard algorithms is that the lambda doesn't mutate things, and this lambda mutates numbers as part of its process.

If you want to keep the find_duplicate function's signature the same, you can still do that:

int find_duplicate(const vector<int> &v)
{
    unordered_set<int> numbers;

    auto it = std::find_if(v.begin(), v.end(),
        [&](int num) { return !numbers.insert(num).second; });

    return it == v.end() ? -1 : *it;
}
user_18961690
Related