39template<
typename ForwardRange,
typename Compare = std::less<>,
typename Proj = std::
identity>
40[[nodiscard]]
bool is_sorted(ForwardRange&&
range, Compare comp = {}, Proj proj = {})
42 return std::is_sorted(std::begin(range), std::end(range),
43 [&](
const auto& x,
const auto& y) {
44 return comp(std::invoke(proj, x), std::invoke(proj, y));
48template<
typename RandomAccessRange>
54template<
typename RandomAccessRange,
typename Compare>
55constexpr void sort(RandomAccessRange&&
range, Compare comp)
57 std::sort(std::begin(
range), std::end(
range), comp);
60template<
typename RAIter,
typename Compare = std::less<>,
typename Proj>
61constexpr void sort(RAIter first, RAIter last, Compare comp, Proj proj)
63 std::sort(first, last,
64 [&](
const auto& x,
const auto& y) {
65 return comp(std::invoke(proj, x), std::invoke(proj, y));
69template<
typename RandomAccessRange,
typename Compare = std::less<>,
typename Proj>
70constexpr void sort(RandomAccessRange&&
range, Compare comp, Proj proj)
75template<
typename RandomAccessRange>
78 std::stable_sort(std::begin(
range), std::end(
range));
81template<
typename RandomAccessRange,
typename Compare>
84 std::stable_sort(std::begin(
range), std::end(
range), comp);
87template<
typename RAIter,
typename Compare = std::less<>,
typename Proj>
88void stable_sort(RAIter first, RAIter last, Compare comp, Proj proj)
90 std::stable_sort(first, last,
91 [&](
const auto& x,
const auto& y) {
92 return comp(std::invoke(proj, x), std::invoke(proj, y));
96template<
typename RandomAccessRange,
typename Compare = std::less<>,
typename Proj>
102template<
typename ForwardRange,
typename T>
105 return std::binary_search(std::begin(
range), std::end(
range), value);
108template<
typename ForwardRange,
typename T,
typename Compare>
111 return std::binary_search(std::begin(
range), std::end(
range), value, comp);
114template<
typename ForwardRange,
typename T,
typename Compare = std::less<>,
typename Proj = std::
identity>
115[[nodiscard]]
auto lower_bound(ForwardRange&&
range,
const T& value, Compare comp = {}, Proj proj = {})
117 auto comp2 = [&](
const auto& x,
const auto& y) {
118 return comp(std::invoke(proj, x), y);
120 return std::lower_bound(std::begin(range), std::end(range), value, comp2);
123template<
typename ForwardRange,
typename T,
typename Compare = std::less<>,
typename Proj = std::
identity>
124[[nodiscard]]
auto upper_bound(ForwardRange&&
range,
const T& value, Compare comp = {}, Proj proj = {})
126 auto comp2 = [&](
const auto& x,
const auto& y) {
127 return comp(x, std::invoke(proj, y));
129 return std::upper_bound(std::begin(range), std::end(range), value, comp2);
132template<
typename ForwardRange,
typename T,
typename Compare = std::less<>>
135 return std::equal_range(std::begin(range), std::end(range), value, comp);
137template<
typename ForwardRange,
typename T,
typename Compare = std::less<>,
typename Proj = std::
identity>
138[[nodiscard]]
auto equal_range(ForwardRange&&
range,
const T& value, Compare comp, Proj proj)
140 using Iter =
decltype(std::begin(
range));
141 using R =
typename std::iterator_traits<Iter>::value_type;
146 bool operator()(
const R& x,
const R& y)
const {
147 return comp(std::invoke(proj, x), std::invoke(proj, y));
149 bool operator()(
const R& x,
const T& y)
const {
150 return comp(std::invoke(proj, x), y);
152 bool operator()(
const T& x,
const R& y)
const {
153 return comp(x, std::invoke(proj, y));
156 return std::equal_range(std::begin(
range), std::end(
range), value, Comp2{comp, proj});
159template<
typename InputRange,
typename T>
160[[nodiscard]]
auto find(InputRange&&
range,
const T& value)
162 return std::find(std::begin(
range), std::end(
range), value);
165template<
typename InputRange,
typename T,
typename Proj>
166[[nodiscard]]
auto find(InputRange&&
range,
const T& value, Proj proj)
169 [&](
const auto& e) {
return std::invoke(proj, e) == value; });
172template<
typename InputRange,
typename UnaryPredicate>
175 auto it = std::begin(
range);
176 auto et = std::end(
range);
177 for (; it != et; ++it) {
178 if (std::invoke(pred, *it)) {
185template<
typename InputRange,
typename UnaryPredicate>
189 auto it = std::begin(
range);
190 auto et = std::end(
range);
191 for (; it != et; ++it) {
192 if (!std::invoke(pred, *it))
return false;
197template<
typename InputRange,
typename UnaryPredicate>
201 auto it = std::begin(
range);
202 auto et = std::end(
range);
203 for (; it != et; ++it) {
204 if (std::invoke(pred, *it))
return true;
209template<
typename InputRange,
typename UnaryPredicate>
213 auto it = std::begin(
range);
214 auto et = std::end(
range);
215 for (; it != et; ++it) {
216 if (std::invoke(pred, *it))
return false;
221template<
typename ForwardRange>
224 return std::unique(std::begin(
range), std::end(
range));
227template<
typename ForwardRange,
typename BinaryPredicate>
228[[nodiscard]]
auto unique(ForwardRange&&
range, BinaryPredicate pred)
230 return std::unique(std::begin(
range), std::end(
range), pred);
233template<
typename RAIter,
typename Compare = std::equal_to<>,
typename Proj>
234[[nodiscard]]
auto unique(RAIter first, RAIter last, Compare comp, Proj proj)
236 return std::unique(first, last,
237 [&](
const auto& x,
const auto& y) {
238 return comp(std::invoke(proj, x), std::invoke(proj, y));
242template<
typename RandomAccessRange,
typename Compare = std::equal_to<>,
typename Proj>
243[[nodiscard]]
auto unique(RandomAccessRange&&
range, Compare comp, Proj proj)
248template<
typename InputRange,
typename OutputIter>
249 requires(!range<OutputIter>)
252 return std::copy(std::begin(
range), std::end(
range), out);
255template<sized_range Input, sized_range Output>
256auto copy(Input&& in, Output&& out)
258 assert(std::size(in) <= std::size(out));
259 return std::copy(std::begin(in), std::end(in), std::begin(out));
262template<
typename InputRange,
typename OutputIter,
typename UnaryPredicate>
265 return std::copy_if(std::begin(
range), std::end(
range), out, pred);
268template<
typename InputRange,
typename OutputIter,
typename UnaryOperation>
271 return std::transform(std::begin(
range), std::end(
range), out, op);
274template<
typename ForwardRange,
typename Generator>
277 std::generate(std::begin(
range), std::end(
range), std::forward<Generator>(
g));
280template<
typename ForwardRange,
typename T>
283 return std::remove(std::begin(
range), std::end(
range), value);
286template<
typename ForwardRange,
typename UnaryPredicate>
289 return std::remove_if(std::begin(
range), std::end(
range), pred);
292template<
typename ForwardRange,
typename T>
293constexpr void replace(ForwardRange&&
range,
const T& old_value,
const T& new_value)
295 std::replace(std::begin(
range), std::end(
range), old_value, new_value);
298template<
typename ForwardRange,
typename UnaryPredicate,
typename T>
301 std::replace_if(std::begin(
range), std::end(
range), pred, new_value);
304template<
typename ForwardRange,
typename T>
305constexpr void fill(ForwardRange&&
range,
const T& value)
307 std::fill(std::begin(
range), std::end(
range), value);
311template<
typename ForwardIt,
typename T>
312constexpr void iota(ForwardIt first, ForwardIt last, T value)
314 while (first != last) {
320template<
typename ForwardRange,
typename T>
326template<
typename InputRange,
typename T>
329 return std::accumulate(std::begin(
range), std::end(
range), init);
332template<
typename InputRange,
typename T,
typename BinaryOperation>
335 return std::accumulate(std::begin(
range), std::end(
range), init, op);
338template<
typename InputRange,
typename T>
341 return std::count(std::begin(
range), std::end(
range), value);
344template<
typename InputRange,
typename UnaryPredicate>
347 auto first = std::begin(
range);
348 auto last = std::end(
range);
349 typename std::iter_difference_t<
decltype(first)>
count = 0;
350 while (first != last) {
351 if (std::invoke(pred, *first++)) ++
count;
357template<
typename InputRange1,
typename InputRange2,
typename OutputIter>
360 return std::set_difference(std::begin(range1), std::end(range1),
361 std::begin(range2), std::end(range2),
365template<range InputRange1, range InputRange2,
366 typename Pred = std::equal_to<void>,
367 typename Proj1 = std::identity,
typename Proj2 = std::identity>
368bool equal(InputRange1&& range1, InputRange2&& range2, Pred pred = {},
369 Proj1 proj1 = {}, Proj2 proj2 = {})
371 auto it1 = std::begin(range1);
372 auto it2 = std::begin(range2);
373 auto et1 = std::end(range1);
374 auto et2 = std::end(range2);
375 for (; (it1 != et1) && (it2 != et2); ++it1, ++it2) {
376 if (!std::invoke(pred, std::invoke(proj1, *it1), std::invoke(proj2, *it2))) {
380 return (it1 == et1) && (it2 == et2);
383template<sized_range SizedRange1, sized_range SizedRange2,
384 typename Pred = std::equal_to<void>,
385 typename Proj1 = std::identity,
typename Proj2 = std::identity>
386bool equal(SizedRange1&& range1, SizedRange2&& range2, Pred pred = {},
387 Proj1 proj1 = {}, Proj2 proj2 = {})
389 if (std::size(range1) != std::size(range2))
return false;
391 auto it1 = std::begin(range1);
392 auto it2 = std::begin(range2);
393 auto et1 = std::end(range1);
394 for (; it1 != et1; ++it1, ++it2) {
395 if (!std::invoke(pred, std::invoke(proj1, *it1), std::invoke(proj2, *it2))) {
404template<
typename InputRange,
typename Proj = std::
identity>
407 auto it = std::begin(range);
408 auto et = std::end(range);
409 if (it == et)
return true;
411 auto val = std::invoke(proj, *it);
412 for (++it; it != et; ++it) {
413 if (std::invoke(proj, *it) != val) {
437template<
typename ForwardRange,
typename T,
typename Compare = std::less<>,
typename Proj = std::
identity>
438[[nodiscard]]
auto*
binary_find(ForwardRange&& range,
const T& value, Compare comp = {}, Proj proj = {})
441 return ((it != std::end(range)) && (!std::invoke(comp, value, std::invoke(proj, *it))))
451template<
typename Range>
454#ifndef _LIBCPP_VERSION
457 return std::span(range);
466 return std::span(&*std::begin(range), std::size(range));
470template<
typename Range>
471constexpr auto subspan(Range&& range,
size_t offset,
size_t count = std::dynamic_extent)
473 return make_span(std::forward<Range>(range)).subspan(offset, count);
476template<
size_t Count,
typename Range>
477constexpr auto subspan(Range&& range,
size_t offset = 0)
479 return make_span(std::forward<Range>(range)).subspan(offset).template first<Count>();
bool comp(const uint8_t *p, const uint8_t *q)
bool is_sorted(ForwardRange &&range, Compare comp={}, Proj proj={})
bool binary_search(ForwardRange &&range, const T &value)
bool any_of(InputRange &&range, UnaryPredicate pred)
auto unique(ForwardRange &&range)
bool all_of(InputRange &&range, UnaryPredicate pred)
constexpr void fill(ForwardRange &&range, const T &value)
auto remove(ForwardRange &&range, const T &value)
void replace_if(ForwardRange &&range, UnaryPredicate pred, const T &new_value)
bool all_equal(InputRange &&range, Proj proj={})
auto find_if(InputRange &&range, UnaryPredicate pred)
bool none_of(InputRange &&range, UnaryPredicate pred)
auto copy(InputRange &&range, OutputIter out)
auto count(InputRange &&range, const T &value)
auto remove_if(ForwardRange &&range, UnaryPredicate pred)
constexpr void iota(ForwardIt first, ForwardIt last, T value)
T accumulate(InputRange &&range, T init)
void stable_sort(RandomAccessRange &&range)
auto find(InputRange &&range, const T &value)
bool equal(InputRange1 &&range1, InputRange2 &&range2, Pred pred={}, Proj1 proj1={}, Proj2 proj2={})
auto upper_bound(ForwardRange &&range, const T &value, Compare comp={}, Proj proj={})
auto equal_range(ForwardRange &&range, const T &value, Compare comp={})
auto set_difference(InputRange1 &&range1, InputRange2 &&range2, OutputIter out)
void generate(ForwardRange &&range, Generator &&g)
auto transform(InputRange &&range, OutputIter out, UnaryOperation op)
auto copy_if(InputRange &&range, OutputIter out, UnaryPredicate pred)
constexpr void replace(ForwardRange &&range, const T &old_value, const T &new_value)
constexpr void sort(RandomAccessRange &&range)
auto lower_bound(ForwardRange &&range, const T &value, Compare comp={}, Proj proj={})
auto count_if(InputRange &&range, UnaryPredicate pred)
constexpr auto make_span(Range &&range)
constexpr auto subspan(Range &&range, size_t offset, size_t count=std::dynamic_extent)
auto * binary_find(ForwardRange &&range, const T &value, Compare comp={}, Proj proj={})