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

Created on 2018-05-24.00:00:00 last changed 65 months ago

Messages

Date: 2018-11-14.18:46:39

Proposed resolution:

This wording is relative to N4750.

  1. 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 [first2, last2) is contained in the range [first1, last1). Returns false otherwisea 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.

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: 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 [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 [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 otherwisea subsequence of [first1, last1).

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

History
Date User Action Args
2018-11-25 18:36:54adminsetstatus: new -> resolved
2018-11-14 18:46:39adminsetmessages: + msg10225
2018-06-27 18:44:50adminsetmessages: + msg9994
2018-05-27 13:55:56adminsetmessages: + msg9858
2018-05-24 00:00:00admincreate