同志们，晚上好！ 您如此冷淡地
从我们这里拆分了本书的第一版“
C ++ 17 STL。Standard Template Library ”，并且您继续分析第二本书，以至于我们最终决定在这里提出另一种观点。 今天的文章的作者是IvanČukić，他还拥有《
C ++函数式编程 》一书，该书正准备在曼宁出版社出版。 我们提供评估他的怀疑思想，代码和计算方法
前言我想将此帖子命名为“关于STL算法的恶性”，以测试我自己在激发点击方面的技能。 但是后来他认为最好是为目标受众写一篇文章，而不是写这样的帖子，让那些想争论我的出色论文的人聚在一起。
因此，我可以假设您对算法，算法的复杂性感兴趣，并且想编写最完美的代码。
演算法在现代的专业C ++社区中，通常建议人们：使您的程序更安全，更快，更富有表现力，等等。 -使用标准库中的算法。 我还会尝试在有合适受众的地方，在我的书，演讲，研讨会中推广此建议。
当然，如果我们被迫编写一个
for循环来解决摆在我们面前的问题，那是绝对正确的，我们首先需要考虑标准库（或boost）的现有算法是否适合于此，而不是盲目行动。
我们仍然需要知道这些算法是如何实现的，与它们相关的要求和保证，它们的时空复杂性是什么。
通常，如果我们面临的任务完全符合STL算法的要求，并且可以直接应用，那么该算法将是最有效的解决方案。
如果我们需要在应用算法之前以某种方式准备数据，则可能会出现问题。
套路口假设我们正在为C ++开发人员编写一个工具，该工具将提供有关替换lambda表达式中的默认捕获选项（谈论
[=]和
[&] ）的提示，并显式显示捕获变量的列表。
std::partition(begin(elements), end(elements), [=] (auto element) { ^~~ - - , [threshold] return element > threshold; });
解析文件时，我们需要一个集合，用于存储当前作用域和相邻作用域的变量。 一旦遇到带有默认捕获的lambda表达式，我们将需要查看那里使用了哪些变量。
结果，我们有两组：一组在周围可见性区域中的变量，另一组在lambda表达式主体中使用的变量。
我们将要提供的捕获选项列表应该是这两个集合的交集（lambda表达式可以使用不需要捕获的全局变量，并且lambda表达式中不会使用周围范围的所有变量）。
而且，如果需要交集，则可以使用
std::set_intersection 。
该算法简单易用。 它接受两个排序的集合，并从头到尾同时运行它们：
- 如果第一个集合中的当前项目与第二个集合中的当前项目相同，则将其添加到结果中，该算法将简单地移至两个集合中的下一个项目；
- 如果第一个集合中的实际项目小于第二个集合中的实际项目，则该算法将仅跳过第一个集合中的当前项目；
- 如果第一个集合中的实际项目大于第二个集合中的实际项目，则该算法将跳过第二个集合中的当前项目；否则，该算法将跳过第二个集合中的当前项目。
在每次迭代中，至少一个元素（来自第一个或第二个输入集合）被跳过-因此，算法的复杂度将是线性的
O(m + n) ，其中
m是第一个集合中的元素数量，
n是第二个集合中的元素数量。
简单有效。 只要对输入集合进行排序。
排序问题是：如果集合没有预先排序怎么办？
在前面的示例中，明智的做法是将周围可见性区域中的变量存储在类似堆栈的结构中，在该结构中，解析器可以简单地添加进入新作用域的新元素，并在其离开时立即删除当前作用域的变量。
因此，变量将不会按名称排序，并且我们将无法直接使用
std::set_intersection进行操作。 同样，如果您在lambda表达式的主体中跟踪变量，那么我们很可能将无法以排序形式保存它们。
由于
std::set_intersection仅适用于已排序的集合，因此在许多项目中会发生此原理：首先对集合进行排序，然后调用
std::set_intersection 。
如果我们忘记了在示例中对一堆变量进行排序会完全贬低我们定义的堆栈的全部使用价值，那么未排序集合的交集算法将如下所示：
template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_1(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { std::sort(first1, last1); std::sort(first2, last2); return std::set_intersection(first1, last1, first2, last2, dest); }
整个算法的复杂度是多少？ 排序需要准线性时间，因此此方法的总体复杂度为
O(n log n + m log m + n + m) 。
排序较小是否可以不进行分类？
如果两个集合都没有排序，那么对于第一个元素中的每个元素，我们将不得不遍历第二个集合-以确定是否将其包括在结果集中。 尽管这种方法在实际项目中非常普遍，但比以前的方法还要糟糕-其复杂度为
O(n * m) 。
请记住Zen并选择“第三条路径”，而不是将所有内容连续排列或不进行任何排序，我们只对一个集合进行排序。
如果仅对一个集合进行排序，则可以逐一迭代未排序的所有值，并针对每个值检查它是否在排序的集合中。 为此，请应用二进制搜索。
在这种情况下，用于对第一个集合进行排序的时间复杂度将为
O(n log n)对于进行排序和检查的时间复杂度将为
O (m log n) 。 总复杂度将为
O((n + m) log n) 。
如果我们决定对第二个集合而不是第一个集合进行排序，那么复杂度将为
O((n + m) log m) 。
为了获得最大效率，我们总是对元素较少的集合进行排序，以使算法的最终复杂度为
((m + n) log (min(m, n)) 。
该实现将如下所示：
template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_2(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_2(first2, last2, first1, last1, dest); return; } std::sort(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return std::binary_search(first1, last1, FWD(value)); }); }
在我们的具有lambda表达式中的捕获列表的示例中，通常对lambda表达式中存在的变量的集合进行排序，因为它可能小于来自所有周围范围的所有变量的集合。
散列最后一个选择是从较小的集合中构建
std::unordered_set （基于哈希的无序集实现），而不是对其进行排序。 在这种情况下，搜索操作的复杂度将平均为
O(1) ，但是构建
std::unordered_set会花费一些时间。 建筑物的复杂度范围从
O(n)到
O(n*n) ，这是一个潜在的问题。
template <typename InputIt1, typename InputIt2, typename OutputIt> void unordered_intersection_3(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_3(first2, last2, first1, last1, dest); return; } std::unordered_set<int> test_set(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return test_set.count(FWD(value)); }); }
当您需要计算具有单个预定义的小集合的多个集合的交集时，散列方法将完全胜出。 也就是说，我们有集合
A ，集合
B₁ ，
B₂…并且我们要计算
A ∩ B₁, A ∩ B₂…在这种情况下，您可以忽略
std::unordered_set构造的复杂度，并且计算每个交集的复杂度将是线性的
O(m) ，其中
m是第二个集合中元素的数量。
控制权当然，检查算法的复杂性总是有用的，但是在这种情况下，使用检查点检查各种方法也是明智的。 特别是从最后两个选项中进行选择时，我们将比较二进制搜索和基于哈希的集合。
我最简单的测试表明，必须对两个集合进行排序的第一个选项始终是最慢的。
对较小的集合进行排序的性能要优于
std::unordered_set ，但并非特别如此。
当两个集合具有相同数量的元素时，第二种和第三种方法都比第一种略快，而当一个集合中的元素数量比第二种多大约1000倍时，第二种和第三种方法都快得多（最多六倍）。