算法std ::的复杂性包含在c ++中

Question

该算法std::includes采用两个有序范围并检查set2是否在set1中(即set2的每个元素是否包含在set1中)？

我想知道为什么eel.is/c++draft说这个算法的复杂性至多是2·(N1+N2-1)比较的？

:同样在陈述
1. cppreference
2. CPLUSPLUS

在我看来,它应该只是最多的2·N1比较,最糟糕的情况是max(set2) >= max(set1).

Answer 1

我在 github 上创建了一个C++ 标准草案的问题。与 ISO C++ 标准委员会的 Richard Smith 就此进行了一些对话。

从一开始他就否认了意图混淆的问题std::includes。但最终同意在澄清规范后应重新审视功能的复杂性：

复杂性要求与当前的描述一致，并且如果/当描述被修复以实际描述算法“应该”做什么时，应该被修复。看起来 LWG 已经在处理这个问题了。我会回复那个库线程请求在规范修复后重新审视复杂性。