向量中的第一个副本

html5 • • 问答

我有以下代码在整数向量中找到第一个重复项：

#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 不应修改输入向量，也不应复制它。

回答

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返回 a 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;
}

  • I'd be inclined to put the `unordered_set` into the predicate: `[numbers = std::unordered_set<int>()](int num) mutable { ... }`: it doesn't have any business outside the predicate. A potential caveat is that the standard library doesn't make any promise on how the predicate gets copied...
以上是向量中的第一个副本的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>