检查 std::vector 是否有重复项

Question

我想检查一个整数向量是否有任何重复项，如果有，则必须返回 true。所以我尝试做这样的事情：

 vector<int> uGuess = {1,2,3,3,4,5}
vector<int> a = uGuess;
sort(a.begin(), a.end());
bool d = unique(a.begin(), a.end());

这不起作用，因为 unqiue 不能分配为布尔值。我应该如何着手呢？如果我要编写一个 for 循环来执行相同的操作，我应该怎么做？

原文由 rrc 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

在 google 上查找 std::unique 我找到了这个页面 std::unique 。我看了看它做了什么：

从范围 [first, last) 中的每个连续等效元素组中消除除第一个元素之外的所有元素

所以它看起来像你想要的 - 删除重复项。

然后我看看它返回的内容……

…为范围的新逻辑结束返回一个过去的迭代器

因此 std::unique 的结果是一个序列，它与整个 vector 不一定相同。

如果没有删除任何内容，则返回值将是 vector 的结尾。

所以你要：

 vector<int>::iterator it = std::unique(a.begin(), a.end());
bool wasUnique = (it == a.end());

或者对于 C++11：

 auto it = std::unique(a.begin(), a.end());
bool wasUnique = (it == a.end());

最后，为了使独特的功能起作用，需要对 vector 进行排序，因此完整的代码为：

 sort(a.begin(), a.end());
auto it = std::unique(a.begin(), a.end());
bool wasUnique = (it == a.end());

原文由 mksteve 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

如果您的向量很小，例如 < 32 个对象，或者如果由于缺少移动或复制构造函数/赋值而复制和排序对象很昂贵或不可能，那么直接 O(n^2) 将所有内容与其他所有内容进行比较算法是要走的路。

这是我的解决方案：

 template <typename Iterator>
bool has_duplicates( Iterator first, Iterator end ) {
    for (auto i = first; i != end; ++i) {
        for (auto j = first; i != j; ++j) {
            if (*i == *j) return true;
        }
    }
    return false;
}

template <typename Container>
bool has_duplicates(const Container &v) {
    for (const auto & i : v) {
        for (const auto & j : v) {
            if (&i == &j) break;
            if (i == j) return true;
        }
    }
    return false;
}

原文由 Goswin von Brederlow 发布，翻译遵循 CC BY-SA 4.0 许可协议