std::ranges::includes
From cppreference.com
| Defined in header <algorithm>
|
||
| Call signature |
||
template< std::input_iterator I1, std::sentinel_for<I1> S1,
std::input_iterator I2, std::sentinel_for<I2> S2,
class Proj1 = std::identity, class Proj2 = std::identity,
std::indirect_strict_weak_order
<std::projected<I1, Proj1>,
std::projected<I2, Proj2>> Comp = ranges::less >
constexpr bool includes( I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} )
|
(1) | (since C++20) |
template< ranges::input_range R1, ranges::input_range R2,
class Proj1 = std::identity, class Proj2 = std::identity,
std::indirect_strict_weak_order
<std::projected<ranges::iterator_t<R1>, Proj1>,
std::projected<ranges::iterator_t<R2>, Proj2>> Comp
= ranges::less >
constexpr bool includes( R1&& r1, R2&& r2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} )
|
(2) | (since C++20) |
template< /*execution-policy*/ Ep,
std::random_access_iterator I1, std::sized_sentinel_for<I1> S1,
std::random_access_iterator I2, std::sized_sentinel_for<I2> S2,
class Proj1 = std::identity, class Proj2 = std::identity,
std::indirect_strict_weak_order
<std::projected<I1, Proj1>,
std::projected<I2, Proj2>> Comp = ranges::less >
bool includes( Ep&& policy, I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(3) | (since C++26) |
template< /*execution-policy*/ Ep,
/*sized-random-access-range*/ R1, /*sized-random-access-range*/ R2,
class Proj1 = std::identity, class Proj2 = std::identity,
std::indirect_strict_weak_order
<std::projected<ranges::iterator_t<R1>, Proj1>,
std::projected<ranges::iterator_t<R2>, Proj2>> Comp
= ranges::less >
bool includes( Ep&& policy, R1&& r1, R2&& r2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(4) | (since C++26) |
For the definition of /*execution-policy*/, see this page; for the definition of /*sized-random-access-range*/, see this page.
1,2) Checks if the sorted target range
[first2, last2) or r2 is a subsequence of the sorted source range [first1, last1) or r1. 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.3,4) Same as (1,2), but executed according to
policy.If any of the following conditions is satisfied, the behavior is undefined:
- The source range is not sorted with respect to the comparator
compand projectionproj1. - The target range is not sorted with respect to the comparator
compand projectionproj2.
The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:
- Explicit template argument lists cannot be specified when calling any of them.
- None of them are visible to argument-dependent lookup.
- When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.
Parameters
| first1, last1 | - | the pair of iterators defining the source range |
| r1 | - | the source range |
| first2, last2 | - | the pair of iterators defining the target range |
| r2 | - | the target range |
| comp | - | the comparator to be applied to the (projected) elements |
| proj1 | - | the projection to be applied to the elements in the source range |
| proj2 | - | the projection to be applied to the elements in the target range |
| policy | - | the execution policy to use |
Return value
true if the target range is a subsequence of the source range; otherwise false.
Complexity
Given
- N1 as
ranges::distance(first1, last1)orranges::distance(r1), - N2 as
ranges::distance(first2, last2)orranges::distance(r2):
1,2) At most 2⋅(N1+N2)-1 applications of
comp, proj1 and proj2.3,4) 𝓞(N1+N2) applications of
comp, proj1 and proj2.Exceptions
3,4) During the execution process:
- If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
- If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).
Possible implementation
struct includes_fn
{
template<std::input_iterator I1, std::sentinel_for<I1> S1,
std::input_iterator I2, std::sentinel_for<I2> S2,
class Proj1 = std::identity, class Proj2 = std::identity,
std::indirect_strict_weak_order
<std::projected<I1, Proj1>,
std::projected<I2, Proj2>> Comp = ranges::less>
constexpr bool operator()(I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
{
for (; first2 != last2; ++first1)
{
if (first1 == last1 || comp(*first2, *first1))
return false;
if (!comp(*first1, *first2))
++first2;
}
return true;
}
template<ranges::input_range R>
auto get_end(R&& r)
{
return ranges::end(r);
}
template<ranges::forward_range R>
auto get_end(R&& r)
{
return ranges::next(ranges::begin(r), ranges::end(r));
}
template<ranges::input_range R1, ranges::input_range R2,
class Proj1 = std::identity, class Proj2 = std::identity,
std::indirect_strict_weak_order
<std::projected<ranges::iterator_t<R1>, Proj1>,
std::projected<ranges::iterator_t<R2>, Proj2>> Comp = ranges::less>
constexpr bool operator()(R1&& r1, R2&& r2, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {}) const
{
return (*this)(ranges::begin(r1), get_end(r1),
ranges::begin(r2), get_end(r2),
std::ref(comp), std::ref(proj1), std::ref(proj2));
}
};
inline constexpr auto includes = includes_fn{};
|
Example
Run this code
#include <algorithm>
#include <cctype>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <locale>
#include <string>
template<class T>
std::ostream& operator<<(std::ostream& os, const std::initializer_list<T>& list)
{
for (os << "{ "; const auto& elem : list)
os << elem << ' ';
return os << "} ";
}
struct true_false : std::numpunct<char>
{
std::string do_truename() const { return "? Yes\n"; }
std::string do_falsename() const { return "? No\n"; }
};
int main()
{
std::cout.imbue(std::locale(std::cout.getloc(), new true_false));
auto ignore_case = [](char a, char b) { return std::tolower(a) < std::tolower(b); };
const auto
a = {'a', 'b', 'c'},
b = {'a', 'c'},
c = {'a', 'a', 'b'},
d = {'g'},
e = {'a', 'c', 'g'},
f = {'A', 'B', 'C'},
z = {'a', 'b', 'c', 'f', 'h', 'x'};
std::cout
<< z << "includes\n" << std::boolalpha
<< a << std::ranges::includes(z.begin(), z.end(), a.begin(), a.end())
<< b << std::ranges::includes(z, b)
<< c << std::ranges::includes(z, c)
<< d << std::ranges::includes(z, d)
<< e << std::ranges::includes(z, e)
<< f << std::ranges::includes(z, f, ignore_case);
}
Output:
{ a b c f h x } includes
{ a b c } ? Yes
{ a c } ? Yes
{ a a b } ? No
{ g } ? No
{ a c g } ? No
{ A B C } ? Yes
See also
| determines if one sequence is a subsequence of another (function template) | |
(C++20) |
computes the difference between two sets (algorithm function object) |
(C++20) |
searches for the first occurrence of a range of elements (algorithm function object) |
(C++23)(C++23) |
checks if the range contains the given element or subrange (algorithm function object) |