Namespaces
Variants
Views
Actions

std::ranges::includes

From cppreference.com
< cpp‎ | algorithm‎ | ranges
 
 
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms: std::ranges::copy, std::ranges::sort, ...
Execution policies (C++17)
Non-modifying sequence operations
(C++11)(C++11)(C++11)
(C++17)
Modifying sequence operations
Operations on uninitialized storage
Partitioning operations
Sorting operations
(C++11)
Binary search operations
Set operations (on sorted ranges)
Heap operations
(C++11)
Minimum/maximum operations
(C++11)
(C++17)

Permutations
Numeric operations
C library
 
Constrained algorithms
Non-modifying sequence operations
Modifying sequence operations
Operations on uninitialized storage
Partitioning operations
Sorting operations
Binary search operations
Set operations (on sorted ranges)
ranges::includes

Heap operations
Minimum/maximum operations
Permutations
 
Defined in header <algorithm>
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)

Returns true if the projections of the sorted range [first2, last2) is a subsequence of the projections of the sorted range [first1, last1). (A subsequence need not be contiguous.)

1) Both ranges must be sorted with the given comparison function comp.
2) Same as (1), but uses r1 and r2 as the source ranges, as if by using ranges::begin(r1) and ranges::begin(r2) as first1 and first2 (respectively), and ranges::end(r1) and ranges::end(r2) as last1 and last2 (respectively).

The function-like entities described on this page are niebloids, that is:

In practice, they may be implemented as function objects, or with special compiler extensions.

Contents

[edit] Parameters

first1, last1 - the sorted range of elements to examine
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 the projected elements
proj1 - projection to apply to the elements in the first range
proj2 - projection to apply to the elements in the second range

[edit] Return value

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

[edit] Complexity

At most 2·(N1+N2-1) comparisons, where N1 = ranges::distance(r1) and N2 = ranges::distance(r2).

[edit] 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 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{};

[edit] Example

#include <iostream>
#include <algorithm>
#include <iterator>
#include <cctype>
#include <vector>
 
namespace ranges = std::ranges;
 
int main()
{
  auto const v1 = std::vector<char>{'a', 'b', 'c', 'f', 'h', 'x'};
  auto const v2 = std::vector<char>{'a', 'b', 'c'};
  auto const v3 = std::vector<char>{'a', 'c'};
  auto const v4 = std::vector<char>{'g'};
  auto const v5 = std::vector<char>{'a', 'c', 'g'};
 
  ranges::copy(v1, std::ostream_iterator<char>(std::cout, " "));
  std::cout << "\nincludes:\n" << std::boolalpha;
 
  ranges::copy(v2, std::ostream_iterator<char>(std::cout, " "));
  std::cout << ": " << ranges::includes(v1.begin(), v1.end(), v2.begin(), v2.end()) << '\n';
 
  ranges::copy(v3, std::ostream_iterator<char>(std::cout, " "));
  std::cout << ": " << ranges::includes(v1, v3) << '\n';
 
  ranges::copy(v4, std::ostream_iterator<char>(std::cout, " "));
  std::cout << ": " << ranges::includes(v1, v4) << '\n';
 
  ranges::copy(v5, std::ostream_iterator<char>(std::cout, " "));
  std::cout << ": " << ranges::includes(v1, v5) << '\n';
 
  auto cmp_nocase = [](char a, char b) {
    return std::tolower(a) < std::tolower(b);
  };
 
  auto const v6 = std::vector<char>{'A', 'B', 'C'};
  ranges::copy(v6, std::ostream_iterator<char>(std::cout, " "));
  std::cout << ": (case-insensitive) "
            << ranges::includes(v1, v6, cmp_nocase)
            << '\n';
}

Output:

a b c f h x 
includes:
a b c : true
a c : true
g : false
a c g : false
A B C : (case-insensitive) true

[edit] See also

computes the difference between two sets
(niebloid) [edit]
searches for a range of elements
(niebloid) [edit]
returns true if one sequence is a subsequence of another
(function template) [edit]