C ++中算法std :: includes的复杂性

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)时达到最坏情况。

- MrPisarik

---

那个页面上有一个示例实现，它进行了多少次比较？ - Barmar

有可能标准这样规定是为了给实现留下一点余地。可能存在一种不太明显的算法，它可能潜在地更快，但需要进行额外的比较。 - Justin

@Justin，不错的假设，如果有人能找到这个实现，特别是在某个编译器中实现，那就太棒了。 - MrPisarik

Answer 1

我同意你的结论。来自Aki Suihkonen的答案中的交错集合示例是错误的，因为算法一旦2 < 3就会提前退出。

cppreference上的示例实现循环在每次迭代中递增first1，当first1 == last1时返回结果，每次迭代最多执行2次比较，并且不包含嵌套循环。我不认为这种方法会执行超过2xN1次比较。

- Matt Hellige

---

S1={5}和S2={5,5,5,5,5}怎么处理呢？我看不出来如何在两次比较内完成。 - Justin

啊，我以为它首先检查第二个而不是相反的顺序。我的错。 - Slava

@Justin，在这种情况下，算法将在第一次比较后停止，因为在第二次迭代中，S1的指针将被增加，并且由于first1 == last1，算法将返回false。实际上，在每种情况下，当N1 < N2时，它将在N1次迭代后返回false。 - MrPisarik

@Justin，不，就我所看到的，样例算法在那种情况下只会返回false。为了使std::includes返回true，第一个范围需要包含与第二个范围相同数量的副本。 - Matt Hellige

@MattHellige，然后在标准中函数被错误地指定了。它说我们正在评估∀a∈S2，a∈S1，即使|S2| > |S1|也可以成立，因为S1和S2不是集合，而是具有潜在重复元素的范围。 - Justin

Answer 2

我在github上创建了一个C++标准草案的问题。与ISO C++标准委员会的Richard Smith有一些关于它的对话。

起初，他拒绝了这个问题，对std::includes的意图感到困惑。但最终同意，在澄清规范后应重新审视函数的复杂性：

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

- MrPisarik

Answer 3

对于交错集合，例如1、3、5、7……2、4、6、8……，必须比较每个集合的第一个项目是否相等，当失败时，必须消耗排序队列中较小的项。另一种方法是首先比较a<b，然后比较b<a，假设只有小于运算符可用。无论哪种方式都会导致2（N1+N2+c）的复杂度。

引入三路比较符号<= >可以改变此复杂度分析为（N1 + N2-1）。

编辑：是的，你是正确的。该算法在每次迭代中推进每个指针，并在第一个指针/迭代器到达末尾时停止。因此，最多会有N次迭代。这与推进iterator2所需的步骤无关。失败在于示例算法，它没有处理set1 = {1,2,3}，set2 = {3,3,3,X}的重复情况。

- Aki Suihkonen

---

算法必须在比较3和2时停止，因为cppreference上建议的for循环具有循环不变式“first1 <= first2”，对吗？ - MrPisarik

它处理这种情况，因为multiset1不包含multiset2，因为第一个只有一个3，而第二个有三个3。而且这个操作在标准中被视为对集合的操作。 - MrPisarik