|
|
|
|
调用签名
|
|
|
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) 若已排序范围
[first2, last2) 的投影是已排序范围
[first1, last1) 的投影的
子序列则返回
true 。
2) 同 (1) ，但以 r1 与
r2 为源范围，如同分别以 ranges::begin(r1) 与 ranges::begin(r2) 为 first1 与
first2 ，并分别以 ranges::end(r1) 与 ranges::end(r2) 为 last1 与
last2 。
两个范围都必须按照给定的比较函数 comp 排序。子序列不需要连续。
此页面上描述的仿函数实体是 niebloid，即：
实际上，它们能以函数对象，或者某些特殊编译器扩展实现。
参数
| first1, last1
|
-
|
待检验的已排序的元素范围
|
| r1
|
-
|
待检验的已排序的元素范围
|
| first2, last2
|
-
|
待搜索的已排序的元素范围
|
| r2
|
-
|
待搜索的已排序的元素范围
|
| comp
|
-
|
应用到投影后元素的谓词
|
| proj1
|
-
|
应用到第一范围中元素的投影
|
| proj2
|
-
|
应用到第二范围中元素的投影
|
返回值
若 [first2, last2) 是 [first1, last1) 的子序列则为 true ；否则为 false 。
复杂度
至多比较 \(\scriptsize 2 \cdot (N_1+N_2-1)\)2·(N1+N2-1) 次，其中
\(\scriptsize N_1\)N1 为 ranges::distance(r1) 而 \(\scriptsize N_2\)N2 为 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 <iostream>
#include <algorithm>
#include <cctype>
template <class Os, class R> Os& operator<<(Os& os, const R& r) {
for (const auto& e : r) os << e << ' ';
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); };
namespace ranges = std::ranges;
std::cout
<< v1 << "\nincludes:\n" << std::boolalpha
<< v2 << ": " << ranges::includes(v1.begin(), v1.end(), v2.begin(), v2.end()) << '\n'
<< v3 << ": " << ranges::includes(v1, v3) << '\n'
<< v4 << ": " << ranges::includes(v1, v4) << '\n'
<< v5 << ": " << ranges::includes(v1, v5) << '\n'
<< v6 << ": " << ranges::includes(v1, v6) << '\n'
<< v7 << ": " << ranges::includes(v1, v7, no_case)
<< " (case-insensitive)\n";
}
输出：
a b c f h x
includes:
a b c : true
a c : true
a a b : false
g : false
a c g : false
A B C : true (case-insensitive)
参阅
|
|
计算两个集合的差集
(niebloid) |
|
|
搜索一个元素范围
(niebloid) |
|
|
若一个序列是另一个的子列则返回 true
(函数模板) |