This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Resolved status.

### 3115. Unclear description for algorithm `includes`

Section: 25.8.7.2 [includes] Status: Resolved Submitter: Casey Carter Opened: 2018-05-24 Last modified: 2020-09-06

Priority: 3

View all other issues in [includes].

View all issues with Resolved status.

Discussion:

25.8.7.2 [includes]/1 states:

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

but this program:

>     #include <algorithm>
>     #include <array>

>     int main() {
>       std::array<int, 1> a{1};
>       std::array<int, 3> b{1,1,1};
>       return std::includes(a.begin(), a.end(), b.begin(), b.end());
>     }

returns `0` on every implementation I can find, despite that every element in the range `b` is contained in the range `a`. The design intent of the algorithm is actually to determine if the sorted intersection of the elements from the two ranges — as would be computed by the `set_intersection` algorithm — is the same sequence as the range `[first2, last2)`. The specification should say so.

The complexity bound in 25.8.7.2 [includes]/2 is also unnecessarily high: straightforward implementations perform at most `2 * (last1 - first1)` comparisons.

Previous resolution [SUPERSEDED]:

> This wording is relative to N4750.

> 1. Modify 25.8.7.2 [includes] as indicated:

>    >     template<class InputIterator1, class InputIterator2>
>    >       constexpr bool includes(InputIterator1 first1, InputIterator1 last1,
>    >                               InputIterator2 first2, InputIterator2 last2);
>    >     […]

>    > > -1- Returns: `true` if and only 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 subsequence of `[first1, last1)`.

>    > > -2- Complexity: At most `2 * ((last1 - first1) + (last2 - first2)) - 1` comparisons.

[2018-06-27 after reflector discussion]

Priority set to 3. Improved wording as result of that discussion.

[2018-11-13; Casey Carter comments]

The acceptance of P0896R4 during the San Diego meeting resolves this issue: The wording in [includes] includes the PR for LWG 3115.

Proposed resolution:

This wording is relative to N4750.

1. Modify 25.8.7.2 [includes] as indicated:

   >     template<class InputIterator1, class InputIterator2>
   >       constexpr bool includes(InputIterator1 first1, InputIterator1 last1,
   >                               InputIterator2 first2, InputIterator2 last2);
   >     […]

   > > -1- Returns: `true` if and only 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 subsequence of `[first1, last1)`. [Note: A sequence `S` is a subsequence of another sequence `T` if `S` can be obtained from `T` by removing some, all, or none of `T`'s elements and keeping the remaining elements in the same order. — end note].

   > > -2- Complexity: At most `2 * ((last1 - first1) + (last2 - first2)) - 1` comparisons.