C++/STL中，我应该使用哪个算法来检查容器是否有重复项？

Question

有没有STL算法可以检测容器中是否存在重复元素（使用operator==或给定的谓词）？

让我们来考虑这两个向量：

std::vector<int> v1{ 1, 2, 3 };
std::vector<int> v2{ 1, 2, 1 };

我会期望有这样一个函数：

我希望有一个如下所示的函数：

std::is_exclusive( v1.begin(), v1.end() ); // returning true
std::is_exclusive( v2.begin(), v2.end() ); // returning false

有这样一个简单的函数吗？我找不到任何（找到了 std::unique，但它会修改向量...）

注意：我不是在问“如何检查容器是否有重复项”，我知道如何做到这一点（基本上，我可以做 （ std::set<int>( v1.begin(), v1.end() ).size() == v1.size() ），还可能存在许多其他选项。 我想知道是否有 STL 算法函数可以更加智能地完成此操作，因为我很惊讶竟然找不到任何...

- jpo38

---

确定一个无序向量是否具有所有唯一元素。给定一个std::vector，如何确定它是否包含所有唯一的元素，即没有重复项？例如： {1, 2, 3, 4, 5} 是唯一的，但 {1, 2, 3, 2} 不是唯一的。 - Edgar Rokjān

@EdgarRokjān：我想这意味着答案是“不，没有”...;-) - jpo38

这样一个函数的复杂度应该是O(n^2)，所以可能并不存在。 - alain

@alain 你是指朴素实现吗？加上额外的哈希集合，它的平均运行时间为O(N)，空间复杂度为O(N)。 - bipll

@JesperJuhl 这是一种选择，虽然具有破坏性，但在空间上是最佳的选择，不过时间上并非最佳。 - bipll

Answer 1

实现STL风格的is_exclusive模板函数的一种方式是使用std::unordered_map，用于计算范围内元素的数量。当任何一个元素的计数大于1时，该函数模板可以立即返回false：

#include <unordered_map>

template<typename ForwardIt>
bool is_exclusive(ForwardIt first, ForwardIt last) {
    std::unordered_map<typename ForwardIt::value_type, unsigned> count;

    for (auto it = first; it != last; ++it)
        if (++count[*it] > 1)
            return false;

    return true;
}

针对您的例子：

int main() {
    std::vector<int> v1{ 1, 2, 3 };
    std::vector<int> v2{ 1, 2, 1 };


    assert(is_exclusive(v1.begin(), v1.end()));
    assert(!is_exclusive(v2.begin(), v2.end()));
}

- ローウ

Answer 2

我能想到的唯一方法是使用https://en.cppreference.com/w/cpp/algorithm/adjacent_find，但它要求元素已排序，因为它会检查相邻的元素。

编辑：

没有STL算法可以按照你的要求完成这个任务，另一个选择是使用std::any_of。

- Ch1v1

---

我并不是在问如何“检查容器是否有重复项”……有许多方法可以做到这一点（使用 adjacent_find 就是其中之一）。我正在寻找一个接受两个迭代器并返回 true/false 的函数。 - jpo38

那么我会说，有像你这样的人在寻找。 - Ch1v1

Answer 3

STL是关于效率和通用性的。似乎没有一种通用且高效的方法可以在不修改容器的情况下检查容器是否有重复项。因此，毫不奇怪STL中不存在这样的算法。

- Evg

---

错误，unordered_set 在大多数情况下都可以很好地工作，并且具有平均 O(n) 的复杂度（需要哈希和相等比较，以及可能的复制构造函数）。另一种可能性是对于前向迭代器范围，具有最坏情况 O(n log n) 的复杂度，是制作一个指向迭代器或指针的向量并对其进行排序（需要可比较小于类型）。然而，通用解决方案必须分配 O(N) 的额外内存，并对类型施加某些限制，这很可能是尚未出现此类算法的更有可能的原因。 - Arne Vogel

Answer 4

一种实现方法是使用std::set。

将您的向量复制到集合中，并比较元素数量是否相同。

如果相同，则没有重复项，否则您可以猜测重复项的数量。

#include <iostream>
#include <iterator>
#include <vector>
#include <set>
int has_duplicate(const std::vector<int> & v)
{
    std::set<int> s(v.begin(), v.end());
    return v.size() - s.size();
}

int
main()
{

    std::vector<int> v1{ 1, 2, 3 };
    std::vector<int> v2{ 1, 2, 1 };
    std::cout << has_duplicate(v1) << std::endl;
    std::cout << has_duplicate(v2) << std::endl;
}

对于v1，输出为0 -> 您没有重复项 对于v2，输出为1 -> 您有一个重复项

该算法的时间复杂度为O(N*log(N))

- PilouPili

---

你可以通过直接将迭代器传递到集合的构造函数中来简化代码。 - eerorika

这就是我在我的问题的“注释”中所说的。 - jpo38