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

Question

是否有任何 STL 算法可以判断容器是否具有重复元素(使用 operator== 或给定谓词)？

让我们考虑这两个 vector :

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 ，但这会修改​​ vector ...)

注意:我不是在问如何“检查容器是否有重复项”，我知道我该怎么做(基本上，我可以做 ( std::set<int>( v1.begin(), v1.end() ).size() == v1.size() ) 并且可能存在许多其他选项。我在问是否有一个 STL 算法函数可以以更智能的方式完成它，因为我很惊讶我找不到任何...

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