如何更高效判断两个std::list是否包含相同的唯一元素？

需求描述 #

需要比较两个std::list<T>是否包含完全相同的唯一元素（忽略顺序和重复次数），原实现通过将list转换为std::set后比较，虽然简洁但存在额外的CPU和内存开销。

原实现代码 #

#include <list>
#include <set>
#include <string>
#include <cassert>

template<typename T>
auto areListsAsSetsEqual(const std::list<T> &a, const std::list<T> &b) -> bool {
    auto aSet = std::set<T>{a.begin(), a.end()};
    auto bSet = std::set<T>{b.begin(), b.end()};
    return aSet == bSet;
}

auto main() -> int {
    auto x = std::list<std::string>{"red", "blue", "yellow", "green", "green"};
    auto y = std::list<std::string>{"blue", "green", "yellow", "red", "red"};
    auto z = std::list<std::string>{"green", "red", "yellow"};

    auto xyEqual = areListsAsSetsEqual(x, y);
    assert(xyEqual == true);
    auto xzEqual = areListsAsSetsEqual(x, z);
    assert(xzEqual == false);
    return 0;
}

优化方案 #

1. 替换为std::unordered_set降低时间复杂度 #

std::set基于红黑树实现，插入和查找的时间复杂度为O(logn)；而std::unordered_set基于哈希表，平均时间复杂度为O(1)，元素数量较多时性能提升明显。

#include <list>
#include <unordered_set>
#include <string>
#include <cassert>

template<typename T>
bool areListsAsSetsEqual(const std::list<T>& a, const std::list<T>& b) {
    // 快速路径：空列表判断
    if (a.empty() != b.empty()) return false;

    std::unordered_set<T> aSet(a.begin(), a.end());
    std::unordered_set<T> bSet(b.begin(), b.end());

    return aSet == bSet;
}

// main函数同原代码

注意：使用std::unordered_set要求T类型支持哈希（标准库类型如std::string、基础类型已支持，自定义结构体需手动实现哈希函数）。

2. 单集合+提前终止检查 #

避免完全构建两个集合，遍历第二个列表时一旦发现不存在于第一个集合的元素，立刻返回false，减少不必要的计算。

#include <list>
#include <unordered_set>
#include <string>
#include <cassert>

template<typename T>
bool areListsAsSetsEqual(const std::list<T>& a, const std::list<T>& b) {
    if (a.empty() != b.empty()) return false;

    std::unordered_set<T> aSet;
    aSet.reserve(a.size()); // 预分配空间，减少哈希表扩容开销
    for (const auto& elem : a) {
        aSet.insert(elem);
    }

    std::unordered_set<T> bUnique;
    for (const auto& elem : b) {
        // 发现a中没有的元素，直接返回false
        if (!aSet.count(elem)) {
            return false;
        }
        bUnique.insert(elem);
    }

    // 确保a的所有唯一元素都在b中存在
    return aSet.size() == bUnique.size();
}

// main函数同原代码

3. 原地排序+去重比较 #

如果T类型支持<运算符（无需哈希），可以复制列表后排序、去重，再直接比较两个去重后的序列。这种方法内存开销与原实现相当，但排序的CPU开销可能在某些场景下优于哈希。

#include <list>
#include <algorithm>
#include <string>
#include <cassert>

template<typename T>
bool areListsAsSetsEqual(const std::list<T>& a, const std::list<T>& b) {
    if (a.empty() != b.empty()) return false;

    // 复制列表避免修改原数据
    auto aCopy = a;
    auto bCopy = b;

    // 排序后去重
    aCopy.sort();
    auto aLast = std::unique(aCopy.begin(), aCopy.end());
    aCopy.erase(aLast, aCopy.end());

    bCopy.sort();
    auto bLast = std::unique(bCopy.begin(), bCopy.end());
    bCopy.erase(bLast, bCopy.end());

    // 直接比较去重后的序列
    return aCopy == bCopy;
}

// main函数同原代码

4. 哈希表标记法（单容器实现） #

使用一个哈希表记录第一个列表的所有唯一元素，遍历第二个列表时标记元素是否存在，最后检查所有标记是否都被触发，确保双向元素覆盖。

#include <list>
#include <unordered_map>
#include <string>
#include <cassert>

template<typename T>
bool areListsAsSetsEqual(const std::list<T>& a, const std::list<T>& b) {
    if (a.empty() != b.empty()) return false;

    std::unordered_map<T, bool> elemTracker;
    // 初始化：记录a的所有唯一元素，标记为未在b中出现
    for (const auto& elem : a) {
        elemTracker[elem] = false;
    }

    for (const auto& elem : b) {
        auto it = elemTracker.find(elem);
        if (it == elemTracker.end()) {
            // b包含a没有的元素
            return false;
        }
        it->second = true; // 标记为已出现
    }

    // 检查a的所有元素都在b中出现过
    for (const auto& pair : elemTracker) {
        if (!pair.second) {
            return false;
        }
    }

    return true;
}

// main函数同原代码

方案选择建议 #

• 若T支持哈希，优先选择单集合+提前终止方案，兼顾性能和简洁性；
• 若T无法实现哈希但支持排序，选择排序去重方案；
• 对内存占用要求极高时，哈希表标记法仅使用一个容器，内存开销最小。

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