std::includes 实际上是做什么的？

Question

来自 the standard, std::includes:

Returns: true if [first2, last2) is empty or if every element in the range [first2, last2) is contained in the range [first1, last1). Returns false otherwise.

^{注意：因为这是在[alg.set.operations]下，所以范围必须排序}

从字面上看，如果我们让 R1=[first1, last1) 和 R2=[first2, last2)，这就是计算：

∀a∈R2 a∈R1

然而，这并不是实际评估的内容。对于 R1={1} 和 R2={1,1,1}，std::includes(R1, R2) returns false:

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> a({1});
    std::vector<int> b({1,1,1});

    // Outputs 'false'
    std::cout << std::boolalpha
        << std::includes(a.begin(), a.end(), b.begin(), b.end()) << '\n';
}

^{Live on Wandbox}

这令人惊讶。我用 libstdc++ 和 libc++ 验证了它，但在我看来这不太可能是标准库实现中的错误，考虑到它是算法库的一部分。如果这不是 std::includes 应该运行的算法，那是什么？

Answer 1

我相信您正在尝试检查 a 在您的示例中是否包含 b，a 不包含 b 但 b 包含包括 a。如果交换 b 和 a 它将 return 为真，因为 a 包含在 b.

中

我希望我没有漏掉一些明显的东西。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> a({1});
    std::vector<int> b({1,1,1});

    // Outputs 'true'
    std::cout << std::boolalpha
        << std::includes(b.begin(), b.end(), a.begin(), a.end()) << '\n';
}

我通过玩算法了解到的是，当您键入 includes(R2, R1) 时，它会检查 R2 是否拥有 R1 作为子组，如果是 return s true 如果不是 returns false。此外，如果未订购，则会引发错误：sequence not ordered.

Answer 2

我在 cpplang slack 中发布了这个，Casey Carter responded:

The description of the algorithm in the standard is defective. The intent is to determine [if] every element in the needle appears in order in the haystack.

[The algorithm it actually performs is:] "Returns true if the intersection of sorted sequences R1 and R2 is equal to R2"

或者，如果我们确定我们确定 subsequence 的含义：

Returns: true if and only if [first2, last2) is a subsequence of [first1, last1)

^{link to Casey Carter's message}

Answer 3

一如既往的看标准，一定要看未写的字。

关注意图而不仅仅是字母。（标准的措辞经常被发现含糊、不完整、自相矛盾或自相矛盾。）

阅读“28.7.6 Set operations on sorted structures [alg.set.operations]”部分的介绍：

This subclause defines all the basic set operations on sorted structures. They also work with multisets containing multiple copies of equivalent elements. The semantics of the set operations are generalized to multisets in a standard way by defining set_union() to contain the maximum number of occurrences of every element, set_intersection() to contain the minimum, and so on.

所以很明显 includes 的描述中的词：

Returns: true if [first2, last2) is empty or if every element in the range [first2, last2) is contained in the range [first1, last1). Returns false otherwise.

必须忽略。你需要知道 a priori 什么是多重集操作，"includes" 对两个多重集意味着什么，忽略描述并在你的脑海中重建什么是 显而易见的意图。

多集包含：

A 包含在 B 中当且仅当 A 并集 B = B.

这适用于集合或多重集合。

std::includes 实际上是做什么的？

What does std::includes actually do?

c++

language-lawyer

c++17

stl-algorithm