C++,STL,我应该用哪一个算法来检查容器是否有副本?

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

一种实现STL-like的方法 is_exclusive std::unordered_map 它保持了范围内元素的计数。函数模板可以返回 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()));
}

我唯一能做的就是 https://en.cppreference.com/w/cpp/algorithm/adjacent_find ,但它要求对元素进行排序,因为它将签入相邻的元素。

编辑:

没有一种stl算法可以按您的要求那样做,另一种方法是使用std::any_of。

一种方法是使用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))