C++中使用std::set时std::find_if()的时间复杂度是多少？

核心结论 #

std::find_if()在std::set上的时间复杂度是O(n)，和它在std::vector上的复杂度一致。

原因解释 #

• std::find_if()是C++标准库的通用算法，它只依赖迭代器的遍历能力，完全不感知容器的底层结构。它会从容器的begin()迭代器开始，逐个检查元素是否满足谓词条件，直到找到匹配项或到达end()。不管容器是连续存储的vector，还是基于红黑树的有序set，只要迭代器是双向/随机访问类型，它都只会做线性遍历。
• 而std::set的成员函数find()能做到O(log n)，是因为它是容器专属方法，清楚自己底层红黑树的有序特性，可以利用排序规则进行二分查找。但std::find_if()的谓词是自定义的任意条件——比如你示例中的场景，set的排序规则是先比较pair中第二个set的大小，再比较第一个int的值；但find_if()的查找条件是第一个int等于某个值，这个条件和set的排序键完全不匹配，红黑树的结构无法为这种自定义条件提供快速定位的支持，只能逐个遍历元素。

结合你的示例代码分析 #

你的代码中，set的排序逻辑由自定义lambda决定：

auto cmp = [&](const pair<int, set<int>>& a , const pair<int, set<int>>& b) -> bool {
    if (a.second.size() == b.second.size()) {
        return a.first < b.first;
    }
    return a.second.size() < b.second.size();
};
set<pair<int, set<int>>, decltype(cmp)> tree(cmp);

但你用find_if()查找的是p.first == value的元素，这个条件和set的排序规则不对应，红黑树无法根据这个条件快速定位目标，只能从tree.begin()开始逐个检查每个元素，因此时间复杂度是O(n)。

优化建议 #

如果想要实现O(log n)的查找效率，你有两种选择：

• 调整set的排序规则，让查找条件和排序键匹配，这样可以使用set的成员函数find()；
• 换用更合适的数据结构，比如std::map<int, std::set<int>>，将需要快速查找的first作为map的键，这样调用map的find()方法就能以O(log n)的复杂度定位目标。

内容的提问来源于stack exchange，提问作者Олег Оратовский