std::includes() algorithm
- od C++20
- od C++17
- do C++17
// (1)
template< class InputIt1, class InputIt2 >
constexpr bool includes( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2 );
// (2)
template< class InputIt1, class InputIt2, class Compare >
constexpr bool includes( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, Compare comp );
// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
bool includes( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2 );
// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
class Compare >
bool includes( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2, Compare comp );
// (1)
template< class InputIt1, class InputIt2 >
bool includes( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2 );
// (2)
template< class InputIt1, class InputIt2, class Compare >
bool includes( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, Compare comp );
// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
bool includes( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2 );
// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
class Compare >
bool includes( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2, Compare comp );
// (1)
template< class InputIt1, class InputIt2 >
bool includes( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2 );
// (2)
template< class InputIt1, class InputIt2, class Compare >
bool includes( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, Compare comp );
Returns true
if the sorted range [first2
; last2
) is a subsequence of the sorted range [first1
; last1
) (a subsequence need not be contiguous).
-
(1) Both ranges must be sorted with
operator<
. -
(2) Both ranges must be sorted with
comp
. -
(3 - 4) Same as (1) and (2), but executed according to policy.
Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
istrue
. (do C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
istrue
. (od C++20)
This includes function is stable, which means that for equivalent elements in the original two ranges, the elements from the first range precede the elements from the second range, preserving their original order.
The behavior is undefined
if the destination range overlaps either of the input ranges (the input ranges may overlap each other).Parameters
first1 last2 | The sorted range of elements to examine. |
first2 last3 | The sorted range of elements to search for. |
policy | The execution policy to use. See execution policy for details. |
comp | Comparison function object (i.e. an object that satisfies the requirements of Compare). The signature of the comparison function should be equivalent to the following:
|
Type requirements
InputIt1 InputIt2 | LegacyInputIterator |
ForwardIt1 ForwardIt2 ForwardIt3 | LegacyForwardIterator |
Return value
true
if [first2
; last2
) is a subsequence of [first1
; last1
).
Otherwise, false
.
Complexity
Given N1
as std::distance(first1, last1)
and N2
as std::distance(first2, last2)
:
(1, 3) At most 2 * (N1 + N2 − 1) comparisons using operator<
.
(2, 4) At most 2 * (N1 + N2 − 1) applications of the comparison function comp
.
Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception and
ExecutionPolicy
is one of the standard policies,std::terminate
is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Possible implementation
includes(1)
template<class InputIt1, class InputIt2>
bool includes(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2)
{
for (; first2 != last2; ++first1)
{
if (first1 == last1 || *first2 < *first1)
return false;
if (!(*first1 < *first2))
++first2;
}
return true;
}
includes(2)
template<class InputIt1, class InputIt2, class Compare>
bool includes(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, Compare comp)
{
for (; first2 != last2; ++first1)
{
if (first1 == last1 || comp(*first2, *first1))
return false;
if (!comp(*first1, *first2))
++first2;
}
return true;
}
Examples
#include <algorithm>
#include <cctype>
#include <iostream>
template<class Os, class Co>
Os& operator<<(Os& os, const Co& v)
{
for (auto i : v)
os << i << ' ';
return os << '\t';
}
int main()
{
const auto
v1 = {'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'};
auto no_case = [](char a, char b) { return std::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";
}
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)
Hover to see the original license.