c++ - 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) 返回 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

我在 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}