std::ranges::includes

Определено в заголовке <algorithm>

Подпись вызова

Определено в заголовке `<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)	(с 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)	(с C++20)

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)

(с 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)

(с C++20)

1) Возвращает true, если проекции отсортированного диапазона [first2, last2) являются подпоследовательностью проекций отсортированного диапазона [first1, last1).

2) То же, что и (1), но использует r1 и r2 в качестве исходных диапазонов, как если бы они использовали ranges::begin(r1) и ranges::begin(r2) соответственно в качестве first1 и first2 соответственно, а ranges::end(r1) и ranges::end(r2) в качестве last1 и last2 соответственно.

Оба диапазона должны быть отсортированы с помощью заданной функции сравнения comp. Подпоследовательность необязательно должна быть непрерывной.

Функциональные сущности, описанные на этой странице, являются неблоидами, то есть:

Явные списки шаблонных аргументов не могут быть указаны при вызове ни одного из них.
Ни один из них не виден для поиска аргументов по зависимости (ADL).
Если любой из них найден стандартным поиском без квалификации в качестве имени слева от оператора вызова функции, поиск аргументов по зависимости (ADL) запрещён.

На практике они могут быть реализованы как объекты-функции или с помощью специальных расширений компилятора.

Параметры

first1, last1	-	отсортированный диапазон элементов для проверки
r1	-	отсортированный диапазон элементов для проверки
first2, last2	-	отсортированный диапазон элементов для поиска
r2	-	отсортированный диапазон элементов для поиска
comp	-	функция сравнения для применения к спроецированным элементам
proj1	-	проекция для применения к элементам в первом диапазоне
proj2	-	проекция для применения к элементам во втором диапазоне

Значение возврата

true если [first2, last2) является подпоследовательностью [first1, last1); в противном случае false.

Сложность

Не более \(\scriptsize 2 \cdot (N_1+N_2-1)\)2·(N₁+N₂-1) сравнений, где \(\scriptsize N_1\)N₁ — ranges::distance(r1) и \(\scriptsize N_2\)N₂ — ranges::distance(r2).

Возможная реализация

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 {};

Пример

#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);
}

Вывод:

{ 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

См. также

ranges::set_difference (C++20)	вычисляет разность двух множеств (неблоид)
ranges::search (C++20)	выполняет поиск диапазона элементов (неблоид)
ranges::containsranges::contains_subrange (C++23)(C++23)	проверяет, содержит ли диапазон заданный элемент или поддиапазон (неблоид)
includes	возвращает `true`, если одна последовательность является подпоследовательностью другой (шаблон функции)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/ranges/includes