- Title
- Unclear description for algorithm includes
- Status
- resolved
- Section
- [includes]
- Submitter
- Casey Carter

Created on **2018-05-24.00:00:00**,
last changed **2018-11-25.18:36:54**.

Date: 2018-11-14.18:46:39

**Proposed resolution:**

This wording is relative to N4750.

Modify [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~~a subsequence of`[first2, last2)`is contained in the range`[first1, last1)`. Returns`false`otherwise`[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 *`comparisons.~~(~~(last1 - first1)~~+ (last2 - first2)) - 1~~

Date: 2018-11-15.00:00:00

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

Date: 2018-06-27.00:00:00

*[ 2018-06-27 after reflector discussion ]*

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

Date: 2018-06-27.18:44:50

[includes]/1 states:

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

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 [includes]/2 is also unnecessarily high: straightforward implementations perform
at most `2 * (last1 - first1)` comparisons.

**Previous resolution [SUPERSEDED]:**

This wording is relative to N4750.

Modify [includes] as indicated:

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

Returns:trueif and only if[first2, last2)is~~empty or if every element in the range~~a subsequence of[first2, last2)is contained in the range[first1, last1). Returnsfalseotherwise[first1, last1).-2-

Complexity:At most2 *comparisons.~~(~~(last1 - first1)~~+ (last2 - first2)) - 1~~

History | |||
---|---|---|---|

Date | User | Action | Args |

2018-11-25 18:36:54 | admin | set | status: new -> resolved |

2018-11-14 18:46:39 | admin | set | messages: + msg10225 |

2018-06-27 18:44:50 | admin | set | messages: + msg9994 |

2018-05-27 13:55:56 | admin | set | messages: + msg9858 |

2018-05-24 00:00:00 | admin | create |