C++如何判断容器内元素是否全部唯一？现有实现对比及最优方案问询

问题描述 #

您好，我想寻找可以判断容器内元素是否全部唯一的算法。
以下是我已经尝试实现的方案：

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

int main(){
    std::vector<int> vi{5, 7, 3, 8, 2, 7, 5};
    std::deque<int> di{1, 5, 7, 2, 3, 8, 6};
    std::cout << hasAllDistinctElems( vi.cbegin(), vi.cend() ) << '\n'; // 0
    std::cout << hasAllDistinctElems( di.cbegin(), di.cend() ) << '\n'; // 1
}

该实现运行正常，但我还找到了另一种实现思路：

• 将原容器的所有元素复制到可保证元素唯一性的STL关联容器中，例如std::set、std::map等。
• 对比原容器和新容器的大小：如果二者大小相等，说明原容器所有元素都成功存入了关联容器，即全部唯一；如果大小不等，说明原容器存在重复元素，重复元素被关联容器自动去重：

#include <unordered_set>
#include <deque>
#include <vector>
#include <iostream>

int main(){
    std::vector<int> vi{5, 7, 3, 8, 2, 7, 5};
    std::deque<int> di{1, 5, 7, 2, 3, 8, 6};

    std::unordered_set<int> usi(vi.cbegin(), vi.cend());
    std::unordered_set<int> usi2(di.cbegin(), di.cend());

    std::cout << std::boolalpha;
    std::cout << "vi's all distinct? " << (vi.size() == usi.size()) << '\n'; // false
    std::cout << "di's all distinct? " << (di.size() == usi2.size()) << '\n'; // true
}

以上两种方案均能正常运行，请问实际开发中应该优先选择哪一种？是否有官方内置算法可以直接实现该功能？是否还有其他更优的实现思路？谢谢！

回答 #

1. 两种现有方案的选择建议 #

你写的两种方案适配的场景完全不同，没有绝对的优劣：

• 双重循环方案：时间复杂度为O(n²)，无额外空间开销。只有当容器元素数量极少（通常n<20）的时候才适合用，此时没有额外的内存分配、哈希计算开销，性能反而更高。一旦元素数量超过50，性能会出现断崖式下跌，完全不适用。
• unordered_set方案：平均时间复杂度为O(n)，最坏情况O(n²)，额外空间开销为O(n)。适合绝大多数通用场景，尤其是元素数量大、允许额外内存开销的情况，性能远优于双重循环。注意如果用std::set的话时间复杂度是O(nlogn)，比哈希版略慢，但没有哈希冲突的最坏情况问题。

2. 标准库内置实现 #

目前C++标准库没有直接提供has_all_distinct之类的命名算法，但可以通过现有标准算法组合实现，不需要自己手写双重循环：

方案A：排序+相邻重复检测（允许修改原容器时最优）

#include <algorithm>

template <typename It>
bool hasAllDistinctElems(It first, It last) {
    std::sort(first, last);
    return std::adjacent_find(first, last) == last;
}

这个方案时间复杂度O(nlogn)，如果允许修改原容器则无额外空间开销，不需要内存分配，性能稳定，没有哈希冲突问题，适合对内存占用敏感、不能接受哈希开销的场景。如果不能修改原容器，需要先复制一份元素再排序，空间复杂度变为O(n)。

方案B：哈希检测（通用场景最优）

可以直接基于标准库的unordered_set封装成通用函数，适配所有迭代器类型，相比全量插入再比大小的实现，还可以提前终止，遇到第一个重复元素就直接返回，不需要遍历完所有元素，实际性能更好：

#include <unordered_set>
#include <iterator>

template <typename It>
bool hasAllDistinctElems(It first, It last) {
    using ValueType = typename std::iterator_traits<It>::value_type;
    std::unordered_set<ValueType> seen;
    for (auto it = first; it != last; ++it) {
        if (seen.count(*it)) return false;
        seen.insert(*it);
    }
    return true;
}

3. 其他更优实现思路 #

如果你的场景有特殊约束，可以选针对性的优化方案：

• 如果元素取值范围很小（比如都是0~255的uint8_t，或者是有限的枚举值），可以用数组/位图计数，时间复杂度O(n)，空间复杂度O(1)，没有哈希开销，性能是所有方案里最高的。
• 如果容器本身已经是有序的，不需要排序，直接用std::adjacent_find即可，时间复杂度O(n)，无额外空间开销。
• 如果是C++20及以上版本，可以用范围库简化写法，代码更简洁可读性更高。

内容的提问来源于stack exchange，提问作者Itachi Uchiwa