c++ - vector 中的第一个重复项

Question

我有以下代码，可以在整数 vector 中查找第一个重复项:

#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;
}

我想知道是否有更简洁的方法来使用 C++ std 库算法编写此代码？

find_duplicate 不应修改输入 vector 也不应复制它。

Answer 1

C++ 标准库是围绕迭代器而不是索引构建的。如果您更改您的 find_duplicate返回迭代器的函数，可以简洁地写为:

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

请注意unordered_set<T>::insert返回 pair<iterator, bool> ，其中bool如果我们插入一个新元素，则为 true；如果该元素已在集合中，则为 false。

这是否是好的代码是有争议的。使用标准算法阅读代码时的一个常见期望是 lambda 不会改变事物，而这个 lambda 会改变 numbers作为其流程的一部分。

---

如果您想保留find_duplicate函数的签名相同，您仍然可以这样做:

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