std::ranges::includes
定义于头文件 <algorithm>
|
||
调用签名 |
||
template< std::input_iterator I1, std::sentinel_for<I1> S1, std::input_iterator I2, std::sentinel_for<I2> S2, |
(1) | (C++20 起) |
template< ranges::input_range R1, ranges::input_range R2, class Proj1 = std::identity, class Proj2 = std::identity, |
(2) | (C++20 起) |
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 。
复杂度
至多比较 2·(N1+N2-1) 次,其中 N1 = ranges::distance(r1) 而 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)
参阅
(C++20) |
计算两个集合的差集 (niebloid) |
(C++20) |
搜索一个元素范围 (niebloid) |
若一个序列是另一个的子列则返回 true (函数模板) |