std::includes

来自cppreference.com
< cpp‎ | algorithm

 
 
算法库

|- class="t-nv-h1"

| colspan="5" |
功能
原文:
Functions
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里

|-

| |- |

修改序列操作
原文:
Non-modifying sequence operations
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里
all_of
any_of
none_of
(C++11)
(C++11)
(C++11)
for_each
count
count_if
mismatch
equal

|

|-

修改序列操作
原文:
Modifying sequence operations
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里

| |- |

|

|-

分区操作
原文:
Partitioning operations
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里

| |- |

is_partitioned(C++11)
partition
partition_copy(C++11)

|

|-

排序操作(排序的区间)
原文:
Sorting operations (on sorted ranges)
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里

| |- |

is_sorted(C++11)
is_sorted_until(C++11)
sort

|

|-

二进制搜索操作(排序的区间)
原文:
Binary search operations (on sorted ranges)
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里

| |- |

|

|-

设置操作(排序的区间)
原文:
Set operations (on sorted ranges)
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里

| |- |

merge
inplace_merge
includes

|

|-

堆的操作
原文:
Heap operations
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里

| |- |

|

|-

最小/最大操作
原文:
Minimum/maximum operations
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里

| |- |

|

|-

数字操作
原文:
Numeric operations
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里

| |- |

|

|-

C库
原文:
C library
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里

| |- |

|

|-

 
在头文件 <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 Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里
第一个版本预计都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 Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里

目录

[编辑] 参数

first1, last1 -
检查的元素排序的范围
原文:
the sorted range of elements to examine
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里
first2, last2 -
搜索排序范围内的元素
原文:
the sorted range of elements to search for
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里
comp - 比较函数,如果第一个参数小于第二个参数,返回true

该函数的签名形式如下:

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

虽然函数签名中const &不是必须的,但是函数必须保证不会修改传递给它的对象。
类型 Type1Type2 必须能使类型 InputIt 的对象能够被解引用并隐式转换为任意二者。 ​

类型要求
-
InputIt 必须满足 InputIterator 的要求。

[编辑] 返回值

true如果从[first2, last2)的每一个元素是一个成员的[first, last).
原文:
true if every element from [first2, last2) is a member of [first, last).
这段文字是通过 Google Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里

[编辑] 复杂度

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 Translate 自动翻译生成的。
您可以帮助我们检查、纠正翻译中的错误。详情请点击这里

[编辑] 可能的实现

版本一
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

[编辑] 另请参阅

计算两个集合的差集
(函数模板) [edit]
查找一个元素区间
(函数模板) [edit]