std::includes
来自cppreference.com
<tbody>
</tbody>
| 在标头 <algorithm> 定义
|
||
template< class InputIt1, class InputIt2 > bool includes( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 ); |
(1) | (C++20 起为 constexpr) |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > bool includes( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 ); |
(2) | (C++17 起) |
template< class InputIt1, class InputIt2, class Compare > bool includes( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp ); |
(3) | (C++20 起为 constexpr) |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare > bool includes( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, Compare comp ); |
(4) | (C++17 起) |
在有序范围 [first2, last2) 是有序范围 [first1, last1) 的子序列的情况下返回 true（不必是连续的子序列）。
3) 如果
[first1, last1) 或 [first2, last2) 没有按 comp 排序，那么行为未定义。2,4) 同 (1,3)，但按照
policy 执行。 这些重载只有在满足以下所有条件时才会参与重载决议：
|
|
(C++20 前) |
|
|
(C++20 起) |
参数
| first1, last1 | - | 要检验的已排序元素范围的迭代器对 |
| first2, last2 | - | 要搜索的已排序元素范围的迭代器对 |
| policy | - | 所用的执行策略 |
| comp | - | 比较函数对象（即满足比较 (Compare) 概念的对象），在第一参数小于（即先 序于）第二参数时返回 true。比较函数的签名应等价于如下：
虽然签名不必有 |
| 类型要求 | ||
-InputIt1, InputIt2 必须满足老式输入迭代器 (LegacyInputIterator) 。
| ||
-ForwardIt1, ForwardIt2 必须满足老式向前迭代器 (LegacyForwardIterator) 。
| ||
-Compare 必须满足比较 (Compare) 。
| ||
返回值
在 [first2, last2) 是 [first1, last1) 的子序列时返回 true；否则返回 false。
因为空序列是所有序列的子序列，所以在 [first2, last2) 为空时会返回 true。
复杂度
给定 N1 为 std::distance(first1, last1)，N2 为 std::distance(first2, last2)：
1,2) 最多应用 2⋅(N1+N2)-1 次
operator<(C++20 前)std::less{}(C++20 起) 进行比较。3,4) 最多应用 2⋅(N1+N2)-1 次比较函数
comp。异常
拥有名为 ExecutionPolicy 的模板形参的重载按下列方式报告错误：
- 如果作为算法一部分调用的函数的执行抛出异常，且
ExecutionPolicy是标准策略之一，那么调用 std::terminate。对于任何其他ExecutionPolicy，行为由实现定义。 - 如果算法无法分配内存，那么抛出 std::bad_alloc。
可能的实现
| include (1) |
|---|
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;
}
|
| include (3) |
template<class InputIt1, class InputIt2, class Compare>
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 <algorithm>
#include <cctype>
#include <iostream>
template<class Os, class Co>
Os& operator<<(Os& os, const Co& v)
{
for (const auto& i : v)
os << i << ' ';
return os << '\t';
}
int main()
{
const auto
v1 = {'a', 'b', 'c', 'f', 'h', 'x'},
v2 = {'a', 'b', 'c'},
v3 = {'a', 'c'},
v4 = {'a', 'a', 'b'},
v5 = {'g'},
v6 = {'a', 'c', 'g'},
v7 = {'A', 'B', 'C'};
auto no_case = [](char a, char b) { return std::tolower(a) < std::tolower(b); };
std::cout
<< v1 << "\n包含：\n" << std::boolalpha
<< v2 << "：" << std::includes(v1.begin(), v1.end(), v2.begin(), v2.end()) << '\n'
<< v3 << "：" << std::includes(v1.begin(), v1.end(), v3.begin(), v3.end()) << '\n'
<< v4 << "：" << std::includes(v1.begin(), v1.end(), v4.begin(), v4.end()) << '\n'
<< v5 << "：" << std::includes(v1.begin(), v1.end(), v5.begin(), v5.end()) << '\n'
<< v6 << "：" << std::includes(v1.begin(), v1.end(), v6.begin(), v6.end()) << '\n'
<< v7 << "：" << std::includes(v1.begin(), v1.end(), v7.begin(), v7.end(), no_case)
<< "（大小写不敏感）\n";
}
输出：
a b c f h x
包含：
a b c ：true
a c ：true
a a b ：false
g ：false
a c g ：false
A B C ：true（大小写不敏感）
缺陷报告
下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。
| 缺陷报告 | 应用于 | 出版时的行为 | 正确行为 |
|---|---|---|---|
| LWG 1205 | C++98 | [first2, last2) 为空时返回值不明确
|
此时会返回 true
|
参阅
| 计算两个集合的差集 (函数模板) | |
| 搜索元素范围的首次出现 (函数模板) | |
(C++20) |
当一个序列是另一个的子序列时返回 true (算法函数对象) |