哪种求交集方法更快：std::sort+set_intersection还是哈希集查找？

先看两种方案的实现代码：

方案一：排序后调用std::set_intersection #

auto intersection = std::make_shared<MediaItems>();
std::sort(m_currentSearchResults->begin(), m_currentSearchResults->end());
std::sort(graphSearchResultMediaItems->begin(), graphSearchResultMediaItems->end());
std::set_intersection(
    m_currentSearchResults->begin(), m_currentSearchResults->end(),
    graphSearchResultMediaItems->begin(), graphSearchResultMediaItems->end(),
    std::back_inserter(*intersection));
std::swap(intersection, m_currentSearchResults);

方案二：基于unordered_set的哈希查找 #

auto projectKey = [](const auto& val) {return val.Key(); };
auto intersection = std::make_shared<MediaItems>();
std::unordered_set<mediaItemKey_t> currentRes;
std::unordered_set<mediaItemKey_t> graphRes;
std::ranges::for_each(std::views::transform(*m_currentSearchResults, projectKey), [&currentRes](const auto& val) { currentRes.emplace(val); });
std::ranges::for_each(std::views::transform(*graphSearchResultMediaItems, projectKey), [&graphRes](const auto& val) { graphRes.emplace(val); });
std::ranges::copy(
    currentRes
    | std::views::filter([graphRes](const auto& val) {return graphRes.find(val) != graphRes.end(); })
    | std::views::transform([strong_this](const auto& val) {return strong_this->m_mediaCollection->GetMediaItemByKey(val); }),
    std::back_inserter(*intersection));

性能对比核心逻辑 #

两种方案的快慢差异由时间复杂度和实际运行的常数开销共同决定：

• 方案一：核心开销在两次排序，时间复杂度为O(n log n + m log m)，后续的set_intersection是线性遍历O(n+m)。排序的常数开销较低，但针对大集合时，排序的时间占比会非常高。
• 方案二：依赖哈希表的平均O(1)插入和查找，总时间复杂度平均为O(n + m + k)（k是交集元素数量）。但哈希计算、哈希冲突处理，以及额外的反向查询（GetMediaItemByKey）会带来额外开销；如果哈希函数设计不佳、冲突频繁，最坏时间复杂度会退化成O(n*m)，反而比方案一慢。

不同场景下的选择 #

1. 小数据量场景：两种方案差异不大，甚至方案一可能更快——因为排序的常数开销比哈希表的内存分配、哈希计算开销更低。
2. 大数据量场景：如果mediaItemKey_t的哈希函数高效、冲突少，且GetMediaItemByKey是O(1)操作（比如内部用哈希表存储），方案二的平均性能会远超方案一；但如果哈希冲突严重，或者反向查询耗时高，方案一反而更稳定。
3. 额外因素：方案一会改变结果集合的元素顺序（变为排序后的顺序），方案二的结果顺序是哈希表的遍历顺序；另外方案二需要额外存储两个哈希表，内存占用更高，数据量极大时可能影响缓存命中率，拖慢性能。

总得来说，没有绝对“更快”的方案，要根据你的数据规模、元素类型、哈希质量和反向查询的开销实际测试后选择。

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