- A+

From 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.

^{Note: as this is under [alg.set.operations], the ranges must be sorted}

Taking this literally, if we let `R1=[first1, last1)`

and `R2=[first2, last2)`

, this is evaluating:

`∀a∈R2 a∈R1 `

However, this is not what is actually being evaluated. For `R1={1}`

and `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}

This is surprising. I verified it with both libstdc++ and libc++, but it seems unlikely to me that this would be a bug in the standard library implementation, considering it's part of the algorithms library. If this isn't the algorithm that `std::includes`

is supposed to run, what is?

I posted this in the cpplang slack, and 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"

Or, if we ensure we are certain of the meaning of subsequence:

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

^{link to Casey Carter's message}