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.
includes
Section: 27.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:
27.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)
. Returnsfalse
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 27.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.
Modify 27.8.7.2 [includes] as indicated:
template<class InputIterator1, class InputIterator2> constexpr bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); […]-1- Returns:
-2- Complexity: At mosttrue
if and only if[first2, last2)
isempty or if every element in the rangea subsequence of[first2, last2)
is contained in the range[first1, last1)
. Returnsfalse
otherwise[first1, last1)
.2 *
comparisons.((last1 - first1)+ (last2 - first2)) - 1
[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.
Modify 27.8.7.2 [includes] as indicated:
template<class InputIterator1, class InputIterator2> constexpr bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); […]-1- Returns:
-2- Complexity: At mosttrue
if and only if[first2, last2)
isempty or if every element in the rangea subsequence of[first2, last2)
is contained in the range[first1, last1)
. Returnsfalse
otherwise[first1, last1)
. [Note: A sequenceS
is a subsequence of another sequenceT
ifS
can be obtained fromT
by removing some, all, or none ofT
's elements and keeping the remaining elements in the same order. — end note].2 *
comparisons.((last1 - first1)+ (last2 - first2)) - 1