[libc++][ranges] Implement ranges::binary_search and ranges::{lower, upper}_bound
Reviewed By: Mordante, var-const, ldionne, #libc
Spies: sstefan1, libcxx-commits, mgorny
Differential Revision: https://reviews.llvm.org/D121964
NOKEYCHECK=True
GitOrigin-RevId: 8171586176ee82bb54608c0d03622914c19dbee0
diff --git a/include/algorithm b/include/algorithm
index 864ff1c..c55c87f 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -345,6 +345,37 @@
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr borrowed_iterator_t<R>
ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+ indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+ constexpr I upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<forward_range R, class T, class Proj = identity,
+ indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+ ranges::less>
+ constexpr borrowed_iterator_t<R>
+ upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+ indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+ constexpr I lower_bound(I first, S last, const T& value, Comp comp = {},
+ Proj proj = {}); // since C++20
+ template<forward_range R, class T, class Proj = identity,
+ indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+ ranges::less>
+ constexpr borrowed_iterator_t<R>
+ lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
+
+ template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+ indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+ constexpr bool binary_search(I first, S last, const T& value, Comp comp = {},
+ Proj proj = {}); // since C++20
+ template<forward_range R, class T, class Proj = identity,
+ indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+ ranges::less>
+ constexpr bool binary_search(R&& r, const T& value, Comp comp = {},
+ Proj proj = {}); // since C++20
+
}
constexpr bool // constexpr in C++20
@@ -1063,6 +1094,7 @@
#include <__algorithm/push_heap.h>
#include <__algorithm/ranges_all_of.h>
#include <__algorithm/ranges_any_of.h>
+#include <__algorithm/ranges_binary_search.h>
#include <__algorithm/ranges_copy.h>
#include <__algorithm/ranges_copy_backward.h>
#include <__algorithm/ranges_copy_if.h>
@@ -1080,6 +1112,7 @@
#include <__algorithm/ranges_is_partitioned.h>
#include <__algorithm/ranges_is_sorted.h>
#include <__algorithm/ranges_is_sorted_until.h>
+#include <__algorithm/ranges_lower_bound.h>
#include <__algorithm/ranges_max.h>
#include <__algorithm/ranges_max_element.h>
#include <__algorithm/ranges_min.h>
@@ -1091,6 +1124,7 @@
#include <__algorithm/ranges_reverse.h>
#include <__algorithm/ranges_swap_ranges.h>
#include <__algorithm/ranges_transform.h>
+#include <__algorithm/ranges_upper_bound.h>
#include <__algorithm/remove.h>
#include <__algorithm/remove_copy.h>
#include <__algorithm/remove_copy_if.h>