| Constrained algorithms and algorithms on ranges(C++20) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Constrained algorithms, e.g.ranges::copy,ranges::sort, ... | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Execution policies(C++17) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Numeric operations | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Operations on uninitialized memory | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
std::ranges| Non-modifying sequence operations | |||||||||||||||||||||||||||||||||
| Modifying sequence operations | |||||||||||||||||||||||||||||||||
| Partitioning operations | |||||||||||||||||||||||||||||||||
| Sorting operations | |||||||||||||||||||||||||||||||||
| Binary search operations (on sorted ranges) | |||||||||||||||||||||||||||||||||
| Set operations (on sorted ranges) | |||||||||||||||||||||||||||||||||
| Heap operations | |||||||||||||||||||||||||||||||||
| Minimum/maximum operations | |||||||||||||||||||||||||||||||||
| Permutation operations | |||||||||||||||||||||||||||||||||
| Fold operations | |||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||
| Operations on uninitialized storage | |||||||||||||||||||||||||||||||||
| Return types | |||||||||||||||||||||||||||||||||
Defined in header <algorithm> | ||
Call signature | ||
template<std::permutable I,std::sentinel_for<I> S,class Proj=std::identity, std::indirect_unary_predicate<std::projected<I, Proj>> Pred> | (1) | (since C++20) |
template<ranges::forward_range R,class Proj=std::identity, std::indirect_unary_predicate< | (2) | (since C++20) |
[first, last) in such a way that the projectionproj of all elements for which the predicatepred returnstrue precede the projectionproj of elements for which predicatepred returnsfalse. Relative order of elements is not preserved.The function-like entities described on this page arealgorithm function objects (informally known asniebloids), that is:
Contents |
| first, last | - | the iterator-sentinel pair defining therange of elements to reorder |
| r | - | the range of elements to reorder |
| pred | - | predicate to apply to the projected elements |
| proj | - | projection to apply to the elements |
A subrange starting with an iterator to the first element of the second group and finishing with an iterator equal tolast.(2) returnsstd::ranges::dangling ifr is an rvalue of non-borrowed_range type.
GivenN=ranges::distance(first, last), exactlyN applications of the predicate and projection. At mostN / 2 swaps ifI modelsranges::bidirectional_iterator, and at mostN swaps otherwise.
struct partition_fn{template<std::permutable I,std::sentinel_for<I> S,class Proj=std::identity,std::indirect_unary_predicate<std::projected<I, Proj>> Pred>constexprranges::subrange<I> operator()(I first, S last, Pred pred, Proj proj={})const{ first=ranges::find_if_not(first, last,std::ref(pred),std::ref(proj));if(first== last)return{first, first}; for(auto i=ranges::next(first); i!= last;++i){if(std::invoke(pred,std::invoke(proj,*i))){ranges::iter_swap(i, first);++first;}}return{std::move(first), std::move(last)};} template<ranges::forward_range R,class Proj=std::identity,std::indirect_unary_predicate< std::projected<ranges::iterator_t<R>, Proj>> Pred> requiresstd::permutable<ranges::iterator_t<R>>constexprranges::borrowed_subrange_t<R> operator()(R&& r, Pred pred, Proj proj={})const{return(*this)(ranges::begin(r),ranges::end(r),std::ref(pred),std::ref(proj));}}; inlineconstexpr partition_fn partition; |
#include <algorithm>#include <forward_list>#include <functional>#include <iostream>#include <iterator>#include <ranges>#include <vector> namespace ranges= std::ranges; template<class I,std::sentinel_for<I> S,class Cmp=ranges::less>requiresstd::sortable<I, Cmp>void quicksort(I first, S last, Cmp cmp= Cmp{}){using reference=std::iter_reference_t<I>; if(first== last)return; auto size=ranges::distance(first, last);auto pivot=ranges::next(first, size-1);ranges::iter_swap(pivot,ranges::next(first, size/2)); auto tail= ranges::partition(first, pivot,[=](reference em){returnstd::invoke(cmp, em,*pivot);// em < pivot}); ranges::iter_swap(pivot, tail.begin()); quicksort(first, tail.begin(),std::ref(cmp)); quicksort(ranges::next(tail.begin()), last,std::ref(cmp));} int main(){std::ostream_iterator<int> cout{std::cout," "}; std::vector<int> v{0,1,2,3,4,5,6,7,8,9};std::cout<<"Original vector:\t";ranges::copy(v, cout); auto tail= ranges::partition(v,[](int i){return i%2==0;}); std::cout<<"\nPartitioned vector:\t";ranges::copy(ranges::begin(v),ranges::begin(tail), cout);std::cout<<"│ ";ranges::copy(tail, cout); std::forward_list<int> fl{1,30,-4,3,5,-4,1,6,-8,2,-5,64,1,92};std::cout<<"\nUnsorted list:\t\t";ranges::copy(fl, cout); quicksort(ranges::begin(fl),ranges::end(fl),ranges::greater{});std::cout<<"\nQuick-sorted list:\t";ranges::copy(fl, cout); std::cout<<'\n';}
Possible output:
Original vector: 0 1 2 3 4 5 6 7 8 9Partitioned vector: 0 8 2 6 4 │ 5 3 7 1 9Unsorted list: 1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92Quick-sorted list: 92 64 30 6 5 3 2 1 1 1 -4 -4 -5 -8
(C++20) | copies a range dividing the elements into two groups (algorithm function object)[edit] |
(C++20) | determines if the range is partitioned by the given predicate (algorithm function object)[edit] |
(C++20) | divides elements into two groups while preserving their relative order (algorithm function object)[edit] |
| divides a range of elements into two groups (function template)[edit] |
