From cppreference.com
Defined in header
template<classInputIt1,classInputIt2>boolincludes(InputIt1first1,InputIt1last1,InputIt2first2,InputIt2last2); (1)(constexpr since C++20)template<classInputIt1,classInputIt2,classCompare>boolincludes(InputIt1first1,InputIt1last1,InputIt2first2,InputIt2last2,Comparecomp); (2)(constexpr since C++20)template<classExecutionPolicy,classForwardIt1,classForwardIt2>boolincludes(ExecutionPolicy&&policy,ForwardIt1first1,ForwardIt1last1,ForwardIt2first2,ForwardIt2last2); (3) (since C++17)template<classExecutionPolicy,classForwardIt1,classForwardIt2,classCompare>boolincludes(ExecutionPolicy&&policy,ForwardIt1first1,ForwardIt1last1,ForwardIt2first2,ForwardIt2last2,Comparecomp); (4) (since C++17)Checks if the sorted target range [first2, last2) is a subsequence of the sorted source range [first1, last1).
A sequence S is a subsequence of another sequence T if S can be obtained from T by removing any number of T’s elements and keeping the remaining elements in the same order.
1) If any of these two ranges is not
with respect to operator<(until C++20)std::less{}(since C++20), the behavior is undefined.
2) If any of these two ranges is not sorted with respect to comp, the behavior is undefined.
3,4) Same as (1,2), but executed according to policy.
These overloads participate in overload resolution only if the value of the following expression is true:
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(until C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
(since C++20)Parameters
first1, last1 - the pair of iterators defining the source
first2, last2 - the pair of iterators defining the target
comp - comparison function object (i.e. an object that satisfies the requirements of
) which returns true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following:
boolcmp(constType1&a,constType2&b);
While the signature does not need to have const&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of
(thus, Type1& is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy(since C++11)).
The types Type1 and Type2 must be such that an object of type InputIt can be dereferenced and then implicitly converted to both of them.
policy - the
to use Type requirements -InputIt1, InputIt2 must meet the requirements of
. -ForwardIt1, ForwardIt2 must meet the requirements of
. -Compare must meet the requirements of
. Return value
true if the target range is a subsequence of the source range; otherwise false.
Complexity
Given
N1 as std::distance(first1,last1),
N2 as std::distance(first2,last2):
1) At most 2⋅(N1+N2)-1 comparisons using operator<(until C++20)std::less{}(since C++20).
2) At most 2⋅(N1+N2)-1 applications of the comparison function comp.
3)𝓞(N1+N2) comparisons using operator<(until C++20)std::less{}(since C++20).
4)𝓞(N1+N2) applications of the comparison function comp.
Exceptions
3,4) During the execution process:
If the temporary memory resources required for parallelization are not available,
is thrown.
If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for
,
is invoked).
Possible implementation
template<classInputIt1,classInputIt2>boolincludes(InputIt1first1,InputIt1last1,InputIt2first2,InputIt2last2){for(;first2!=last2;++first1){if(first1==last1||*first2<*first1)returnfalse;if(!(*first1<*first2))++first2;}returntrue;}
template<classInputIt1,classInputIt2,classCompare>boolincludes(InputIt1first1,InputIt1last1,InputIt2first2,InputIt2last2,Comparecomp){for(;first2!=last2;++first1){if(first1==last1||comp(*first2,*first1))returnfalse;if(!comp(*first1,*first2))++first2;}returntrue;}Example
Run this code
#include<algorithm>#include<cctype>#include<iostream>template<classOs,classCo>Os&operator<<(Os&os,constCo&v){for(constauto&i:v)os<<i<<' ';returnos<<'\t';}intmain(){constautov1={'a','b','c','f','h','x'},v2={'a','b','c'},v3={'a','c'},v4={'a','a','b'},v5={'g'},v6={'a','c','g'},v7={'A','B','C'};autono_case=[](chara,charb){returnstd::tolower(a)<std::tolower(b);};std::cout<<v1<<"\nincludes:\n"<<std::boolalpha<<v2<<": "<<std::includes(v1.begin(),v1.end(),v2.begin(),v2.end())<<'\n'<<v3<<": "<<std::includes(v1.begin(),v1.end(),v3.begin(),v3.end())<<'\n'<<v4<<": "<<std::includes(v1.begin(),v1.end(),v4.begin(),v4.end())<<'\n'<<v5<<": "<<std::includes(v1.begin(),v1.end(),v5.begin(),v5.end())<<'\n'<<v6<<": "<<std::includes(v1.begin(),v1.end(),v6.begin(),v6.end())<<'\n'<<v7<<": "<<std::includes(v1.begin(),v1.end(),v7.begin(),v7.end(),no_case)<<" (case-insensitive)\n";}Output:
a b c f h x includes: a b c : true a c : true a a b : false g : false a c g : false A B C : true (case-insensitive) Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
DR Applied to Behavior as published Correct behavior
C++98 the return value was unclear if the target range is empty returns true in this case See also