◐ Shell
clean mode source ↗

std::includes — cppreference.com

Материал из cppreference.com

<metanoindex/>

<tbody> </tbody>

Определено в заголовочном файле <algorithm>

template< class InputIt1, class InputIt2 > bool includes( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );

 (1)

template< class InputIt1, class InputIt2 > bool includes( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp );

 (2)

Возврат true, если каждый элемент из отсортированного диапазона [first2, last2) находится в диапазоне отсортированы [first, last). Также возвращает true если [first2, last2) пусто.

Оригинал:

Returns true if every element from the sorted range [first2, last2) is found within the sorted range [first, last). Also returns true if [first2, last2) is empty.

Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

Первая версия ожидает, что оба диапазона должны быть отсортированы с operator<, вторая версия ожидает, что они должны быть отсортированы с заданной функцией сравнения comp.

Оригинал:

The first version expects both ranges to be sorted with operator<, the second version expects them to be sorted with the given comparison function comp.

Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

Параметры

first1, last1 —

отсортированный набор элементов для изучения

Оригинал:

the sorted range of elements to examine

Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

first2, last2 —

отсортированный набор элементов для поиска

Оригинал:

the sorted range of elements to search for

Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

comp — объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает true, если первый аргумент "меньше", чем второй.

Определение сравнения должно быть эквивалентно:

bool cmp(const Type1 &a, const Type2 &b);

Использование noexcept (начиная с C++11) желательно но не обязательно. Параметры не обязаны передаваться по const&, но не должны модифицироваться. Они должны быть способны принимать все значения типа (даже const) Type1 и Type2 независимо от категории значений (таким образом, Type1& не допускается, равно как и Type1, если только для Type1 перемещение не эквивалентно копированию (начиная с C++11)). Типы Type1 и Type2 должны быть таковы, что объект типа InputIt может быть разыменован и затем неявно преобразован в оба из них.

Требования к типам
-InputIt должен соответствовать требованиям InputIterator.

Возвращаемое значение

true, если каждый элемент из [first2, last2) является членом [first, last).

Оригинал:

true if every element from [first2, last2) is a member of [first, last).

Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

Сложность

В большинстве сравнений 2·(N1+N2-1), где N1 = std::distance(first1, last1) и N2 = std::distance(first2, last2).

Оригинал:

At most 2·(N1+N2-1) comparisons, where N1 = std::distance(first1, last1) and N2 = std::distance(first2, last2).

Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

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

Первый вариант 
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;
}
Второй вариант 
template<class InputIt1, class InputIt2>
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;
}

Пример

#include <iostream>
#include <algorithm>
#include <cctype>

int main()
{
  std::vector<char> v1 {'a', 'b', 'c', 'f', 'h', 'x'};
  std::vector<char> v2 {'a', 'b', 'c'};
  std::vector<char> v3 {'a', 'c'};
  std::vector<char> v4 {'g'};
  std::vector<char> v5 {'a', 'c', 'g'};
  std::vector<char> v6;

  for (auto i : v1) std::cout << i << ' ';
  std::cout << "includes:\n";

  for (auto i : v2) std::cout << i << ' ';
  std::cout << ": " << std::includes(v1.begin(), v1.end(), v2.begin(), v2.end()) << '\n';
  for (auto i : v3) std::cout << i << ' ';
  std::cout << ": " << std::includes(v1.begin(), v1.end(), v3.begin(), v3.end()) << '\n';
  for (auto i : v4) std::cout << i << ' ';
  std::cout << ": " << std::includes(v1.begin(), v1.end(), v4.begin(), v4.end()) << '\n';
  for (auto i : v5) std::cout << i << ' ';
  std::cout << ": " << std::includes(v1.begin(), v1.end(), v5.begin(), v5.end()) << '\n';
  for (auto i : v6) std::cout << i << ' ';
  std::cout << ": " << std::includes(v1.begin(), v1.end(), v6.begin(), v6.end()) << '\n';

  auto cmp_nocase = [](char a, char b) {
    return std::tolower(a) < std::tolower(b);
  }
  std::vector<char> v7 {'A', 'B', 'C'};
  for (auto i : v7) std::cout << i << ' ';
  std::cout << ": "
            << std::includes(v1.begin(), v1.end(), v7.begin(), v7.end(), cmp_nocase)
            << '\n';
}

Вывод: 

a b c f h x includes:
a b c : 1
a c : 1
g : 0
a c g : 0
A B C : 1

См. также