std::ranges::lower_bound
来自cppreference.com
| 定义于头文件 <algorithm>
|
||
| 调用签名 |
||
| template< std::forward_iterator I, std::sentinel_for<I> S, class T, class Proj = std::identity, |
(1) | (C++20 起) |
| template< ranges::forward_range R, class T, class Proj = std::identity, std::indirect_strict_weak_order< |
(2) | (C++20 起) |
1) 返回指向范围
[first, last) 中首个不小于（即大于或等于） value 的元素的迭代器，或若找不到这种元素返回 last 。
范围 [first, last) 必须已按照表达式 comp(element, value) 划分，即所有该表达式对其为 true 的元素必须前趋所有该表达式对其为 false 的元素。完全排序的范围符合此判别标准。2) 同 (1) ，但以
r 为源范围，如同以 ranges::begin(r) 为 first 并以 ranges::end(r) 为 last 。此页面上描述的仿函数实体是 niebloid ，即：
实际上，它们能以函数对象，或以某些特殊编译器扩展实现。
参数
| first, last | - | 定义要检验的部分有序范围的迭代器-哨位对 |
| r | - | 要检验的部分有序范围 |
| value | - | 要与元素比较的值 |
| pred | - | 应用到投影后元素的谓词 |
| proj | - | 应用到元素的投影 |
返回值
指向首个不小于 value 的元素的迭代器，或若找不到这种元素则为 last 。
复杂度
比较和应用投影的次数与 first 和 last 之间的距离成对数（至多比较和应用投影 log
2(last - first) + O(1) 次）。然而，对于不实现 random_access_iterator 的迭代器，迭代器自增次数为线性。
可能的实现
struct lower_bound_fn { template<std::forward_iterator I, std::sentinel_for<I> S, class T, class Proj = std::identity, std::indirect_strict_weak_order< const T*, std::projected<I, Proj>> Comp = ranges::less> constexpr I operator()( I first, S last, const T& value, Comp comp = {}, Proj proj = {} ) const { I it; std::iter_difference_t<I> count, step; count = std::ranges::distance(first, last); while (count > 0) { it = first; step = count / 2; ranges::advance(it, step, last); if (comp(*it, value)) { first = ++it; count -= step + 1; } else { count = step; } } return first; } template<ranges::forward_range R, class T, class Proj = std::identity, std::indirect_strict_weak_order< const T*, std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less> constexpr ranges::borrowed_iterator_t<R> operator()( R&& r, const T& value, Comp comp = {}, Proj proj = {} ) const { return (*this)(ranges::begin(r), ranges::end(r), value, std::ref(comp), std::ref(proj)); } }; inline constexpr lower_bound_fn lower_bound; |
示例
运行此代码
#include <algorithm> #include <iostream> #include <iterator> #include <vector> namespace ranges = std::ranges; template<std::forward_iterator I, std::sentinel_for<I> S, class T, class Proj = std::identity, std::indirect_strict_weak_order< const T*, std::projected<I, Proj>> Comp = ranges::less> I binary_find(I first, S last, const T& value, Comp comp = {}, Proj proj = {}) { first = ranges::lower_bound(first, last, value, comp, proj); return first != last && !comp(value, *first) ? first : last; } int main() { std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 }; auto lower = ranges::lower_bound(data, 4); auto upper = ranges::upper_bound(data, 4); ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; // 经典二分搜索，仅若存在才返回值 data = { 1, 2, 4, 6, 9, 10 }; auto it = binary_find(data.cbegin(), data.cend(), 4); //< 选择 '5' 将返回 end() if(it != data.cend()) std::cout << *it << " found at index "<< ranges::distance(data.cbegin(), it); return 0; }
输出：
4 4 4 4 found at index 2
参阅
| (C++20) |
返回匹配特定值的元素范围 (niebloid) |
| (C++20) |
将范围中的元素分为二组 (niebloid) |
| (C++20) |
定位已划分范围的划分点 (niebloid) |
| (C++20) |
返回指向首个大于某值的元素的迭代器 (niebloid) |
| 返回指向第一个不小于给定值的元素的迭代器 (函数模板) |