| 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::bidirectional_iterator I,std::sentinel_for<I> S, class Proj=std::identity, | (1) | (since C++20) (constexpr since C++26) |
template<ranges::bidirectional_range R,class Proj=std::identity, std::indirect_unary_predicate< | (2) | (since C++20) (constexpr since C++26) |
[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. The algorithms isstable, i.e. the relative order of elements ispreserved.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 |
pivot is an iterator to the first element of the second group.GivenN=ranges::distance(first, last), the complexity is at worst\(\scriptsize N\cdot\log{(N)}\)N·log(N) swaps, and only\(\scriptsize \mathcal{O}(N)\)𝓞(N) swaps in case an extra memory buffer is used. Exactly\(\scriptsize N\)N applications of the predicatepred and projectionproj.
This function attempts to allocate a temporary buffer. If the allocation fails, the less efficient algorithm is chosen.
| Feature-test macro | Value | Std | Feature |
|---|---|---|---|
__cpp_lib_constexpr_algorithms | 202306L | (C++26) | constexpr stable sorting |
This implementation does not use extra memory buffer and as such can be less efficient. See also the implementation inMSVC STL andlibstdc++.
struct stable_partition_fn{template<std::bidirectional_iterator I,std::sentinel_for<I> S,class Proj=std::identity,std::indirect_unary_predicate<std::projected<I, Proj>> Pred> requiresstd::permutable<I>constexprranges::subrange<I> operator()(I first, S last, Pred pred, Proj proj={})const{ first=ranges::find_if_not(first, last, pred, proj); I mid= first;while(mid!= last){ mid=ranges::find_if(mid, last, pred, proj);if(mid== last)break; I last2=ranges::find_if_not(mid, last, pred, proj);ranges::rotate(first, mid, last2); first=ranges::next(first,ranges::distance(mid, last2)); mid= last2;}return{std::move(first), std::move(mid)};} template<ranges::bidirectional_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::move(pred), std::move(proj));}}; inlineconstexpr stable_partition_fn stable_partition{}; |
#include <algorithm>#include <iostream>#include <iterator>#include <vector> namespace rng= std::ranges; template<std::permutable I,std::sentinel_for<I> S>constexprvoid stable_sort(I first, S last){if(first== last)return; auto pivot=*rng::next(first, rng::distance(first, last)/2, last);auto left=[pivot](constauto& em){return em< pivot;};auto tail1= rng::stable_partition(first, last, left);auto right=[pivot](constauto& em){return!(pivot< em);};auto tail2= rng::stable_partition(tail1, right); stable_sort(first, tail1.begin()); stable_sort(tail2.begin(), tail2.end());} void print(constauto rem,auto first,auto last,bool end=true){std::cout<< rem;for(; first!= last;++first)std::cout<<*first<<' ';std::cout<<(end?"\n":"");} int main(){constauto original={9,6,5,2,3,1,7,8}; std::vector<int> vi{};auto even=[](int x){return0==(x%2);}; print("Original vector:\t", original.begin(), original.end(),"\n"); vi= original;constauto ret1= rng::stable_partition(vi, even); print("Stable partitioned:\t", vi.begin(), ret1.begin(),0); print("│ ", ret1.begin(), ret1.end()); vi= original;constauto ret2= rng::partition(vi, even); print("Partitioned:\t\t", vi.begin(), ret2.begin(),0); print("│ ", ret2.begin(), ret2.end()); vi={16,30,44,30,15,24,10,18,12,35}; print("Unsorted vector: ", vi.begin(), vi.end()); stable_sort(rng::begin(vi), rng::end(vi)); print("Sorted vector: ", vi.begin(), vi.end());}
Possible output:
Original vector: 9 6 5 2 3 1 7 8Stable partitioned: 6 2 8 │ 9 5 3 1 7Partitioned: 8 6 2 │ 5 3 1 7 9Unsorted vector: 16 30 44 30 15 24 10 18 12 35Sorted vector: 10 12 15 16 18 24 30 30 35 44
(C++20) | divides a range of elements into two groups (algorithm function object)[edit] |
(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] |
| divides elements into two groups while preserving their relative order (function template)[edit] |
