std::ranges::binary_search
| 定义于头文件 <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) 检查等价于
value 的元素是否在范围 [first, last) 内出现。2) 同 (1) ，但以
r 为源范围，如同以 ranges::begin(r) 为 first 并以 ranges::end(r) 为 last 。对于需要成功的 ranges::binary_search ，范围 [first, last) 必须至少以相对 value 部分有序，即他必须满足下列要求：
- 相对于 std::invoke(comp, std::invoke(proj, element), value) 已划分（即该表达式对其为 true 的所有元素在该表达式对其为 false 的所有元素之前）
- 相对于 !std::invoke(comp, value, std::invoke(proj, element)) 已划分
- 对于所有元素，若 std::invoke(comp, std::invoke(proj, element), value) 为 true 则 !std::invoke(comp, value, std::invoke(proj, element)) 为 true 。
完全排序的范围符合这些判别标准。
此页面上描述的仿函数实体是 niebloid ，即：
实际上，它们能以函数对象，或以某些特殊编译器扩展实现。
参数
| first, last | - | 要检验的元素范围 |
| r | - | 要检验的元素范围 |
| value | - | 与元素比较的值 |
| comp | - | 应用到投影后元素的比较函数 |
| proj | - | 应用到元素的投影 |
返回值
若找到等于 value 的元素则为 true ，否则为 false 。
复杂度
进行的比较与投影次数与 first 和 last 间的距离成对数（至多投影与比较 log
2(last - first) + O(1) 次）。然而，对于不实现 std::random_access_iterator 的迭代器，迭代器自增次数为线性。
可能的实现
struct binary_search_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 bool operator()(I first, S last, const T& value, Comp comp = {}, Proj proj = {}) const { first = std::lower_bound(first, last, value, comp); return (!(first == last) && !(comp(value, *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 bool 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 binary_search_fn binary_search; |
示例
运行此代码
#include <iostream> #include <algorithm> #include <vector> int main() { std::vector<int> haystack {1, 3, 4, 5, 9}; std::vector<int> needles {1, 2, 3}; for (auto needle : needles) { std::cout << "Searching for " << needle << '\n'; if (ranges::binary_search(haystack, needle)) { std::cout << "Found " << needle << '\n'; } else { std::cout << "no dice!\n"; } } }
输出：
Searching for 1 Found 1 Searching for 2 no dice! Searching for 3 Found 3
参阅
| (C++20) |
返回匹配特定值的元素范围 (niebloid) |
| 确定元素是否存在于某范围中 (函数模板) |