Skip to main content

std::ranges::includes() algorithm

// (1)
constexpr bool
includes( I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} )

// (2)
constexpr bool
includes( R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} )

The type of arguments are generic and have the following constraints:

  • I1, I2 - std::input_iterator

  • S1, S2 - std::sentinel_for<I1>, std::sentinel_for<I2>

  • R1, R2 - std::ranges::input_range

  • O - std::weakly_incrementable

  • Comp:

    • (1) - indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>>
    • (2) - indirect_strict_weak_order<projected<ranges::iterator_t<R1> Proj1>, projected<ranges::iterator_t<R2> Proj2>>

    (The std:: namespace was ommited here for readability)

  • Proj1, Proj2 - (none)

The Proj and Comp template arguments have the following default types: std::identity, ranges::less for all overloads.

(The std:: namespace was ommited here for readability)

  • (1) Returns true if the projections of the sorted range [first2; last2) is a subsequence of the projections of the sorted range [first1; last1).

    The ranges must be sorted with the given comparison function comp.

    A subsequence need not be contiguous.

  • (2) Same as (1), but uses r1 as the first range and r2 as the second range, as if using ranges::begin(r1) as first1, ranges::end(r1) as last1, ranges::begin(r2) as first2, and ranges::end(r2) as last2.

The function-like entities described on this page are niebloids.

Parameters

first1
last1

The sorted range of elements to examine.

r
r1

The sorted range of elements to examine.

first2
last2

The sorted range of elements to search for.

r2

The sorted range of elements to search for.

comp

Comparison function to apply to projected elements.

proj1

Projection to apply to the elements in the first range.

proj2

Projection to apply to the elements in the second range.

Return value

true if [first2; last2) is a subsequence of [first1; last1).
Otherwise, false.

Complexity

Given N1 as ranges::distance(r1) and N2 as ranges::distance(r2):

At most 2 * (N1 + N2 − 1) comparisons

Exceptions

(none)

Possible implementation

includes(1) and includes(2)
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 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), ranges::end(r1),
ranges::begin(r2), ranges::end(r2),
std::ref(comp), std::ref(proj1), std::ref(proj2));
}
};

inline constexpr auto includes = includes_fn {};

Examples

Main.cpp

#include <algorithm>
#include <cctype>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <locale>
#include <string>

template<class T>
std::ostream& operator<<(std::ostream& os, std::initializer_list<T> const& list)
{
for (os << "{ "; auto const& 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
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.

std::ranges::includes() algorithm

// (1)
constexpr bool
includes( I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} )

// (2)
constexpr bool
includes( R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} )

The type of arguments are generic and have the following constraints:

  • I1, I2 - std::input_iterator

  • S1, S2 - std::sentinel_for<I1>, std::sentinel_for<I2>

  • R1, R2 - std::ranges::input_range

  • O - std::weakly_incrementable

  • Comp:

    • (1) - indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>>
    • (2) - indirect_strict_weak_order<projected<ranges::iterator_t<R1> Proj1>, projected<ranges::iterator_t<R2> Proj2>>

    (The std:: namespace was ommited here for readability)

  • Proj1, Proj2 - (none)

The Proj and Comp template arguments have the following default types: std::identity, ranges::less for all overloads.

(The std:: namespace was ommited here for readability)

  • (1) Returns true if the projections of the sorted range [first2; last2) is a subsequence of the projections of the sorted range [first1; last1).

    The ranges must be sorted with the given comparison function comp.

    A subsequence need not be contiguous.

  • (2) Same as (1), but uses r1 as the first range and r2 as the second range, as if using ranges::begin(r1) as first1, ranges::end(r1) as last1, ranges::begin(r2) as first2, and ranges::end(r2) as last2.

The function-like entities described on this page are niebloids.

Parameters

first1
last1

The sorted range of elements to examine.

r
r1

The sorted range of elements to examine.

first2
last2

The sorted range of elements to search for.

r2

The sorted range of elements to search for.

comp

Comparison function to apply to projected elements.

proj1

Projection to apply to the elements in the first range.

proj2

Projection to apply to the elements in the second range.

Return value

true if [first2; last2) is a subsequence of [first1; last1).
Otherwise, false.

Complexity

Given N1 as ranges::distance(r1) and N2 as ranges::distance(r2):

At most 2 * (N1 + N2 − 1) comparisons

Exceptions

(none)

Possible implementation

includes(1) and includes(2)
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 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), ranges::end(r1),
ranges::begin(r2), ranges::end(r2),
std::ref(comp), std::ref(proj1), std::ref(proj2));
}
};

inline constexpr auto includes = includes_fn {};

Examples

Main.cpp

#include <algorithm>
#include <cctype>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <locale>
#include <string>

template<class T>
std::ostream& operator<<(std::ostream& os, std::initializer_list<T> const& list)
{
for (os << "{ "; auto const& 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
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.