| 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::input_iterator I1,std::sentinel_for<I1> S1, std::random_access_iterator I2,std::sentinel_for<I2> S2, | (1) | (since C++20) |
template<ranges::input_range R1,ranges::random_access_range R2, class Comp=ranges::less,class Proj1=std::identity, | (2) | (since C++20) |
Helper types | ||
template<class I,class O> using partial_sort_copy_result=ranges::in_out_result<I, O>; | (3) | (since C++20) |
Copies the firstN elements from the source range[first, last), as if it was partially sorted with respect tocomp andproj1, into the destination range[result_first, result_first+ N), where\(\scriptsize N = \min{(L_1, L_2)}\)N = min(L₁, L₂),\(\scriptsize L_1\)L₁ is equal toranges::distance(first, last), and\(\scriptsize L_2\)L₂ is equal toranges::distance(result_first, result_last).
The order of equal elements isnot guaranteed to be 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 the sourcerange of elements to copy from |
| r | - | the source range to copy from |
| result_first, result_last | - | the iterator-sentinel pair defining the destinationrange of elements |
| result_r | - | the destination range |
| comp | - | comparison to apply to the projected elements |
| proj1 | - | projection to apply to the elements of source range |
| proj2 | - | projection to apply to the elements of destination range |
An object equal to{last, result_first+ N}.
At most\(\scriptsize L_1 \cdot \log{(N)}\)L₁•log(N) comparisons and\(\scriptsize 2 \cdot L_1 \cdot \log{(N)}\)2•L₁•log(N) projections.
struct partial_sort_copy_fn{template<std::input_iterator I1,std::sentinel_for<I1> S1,std::random_access_iterator I2,std::sentinel_for<I2> S2,class Comp=ranges::less,class Proj1=std::identity,class Proj2=std::identity> requiresstd::indirectly_copyable<I1, I2>&&std::sortable<I2, Comp, Proj2>&&std::indirect_strict_weak_order<Comp, std::projected<I1, Proj1>, std::projected<I2, Proj2>>constexpr ranges::partial_sort_copy_result<I1, I2> operator()(I1 first, S1 last, I2 result_first, S2 result_last, Comp comp={}, Proj1 proj1={}, Proj2 proj2={})const{if(result_first== result_last)return{std::move(ranges::next(std::move(first), std::move(last))), std::move(result_first)}; auto out_last{result_first};// copy first N elementsfor(;!(first== last or out_last== result_last);++out_last,++first)*out_last=*first; // convert N copied elements into a max-heapranges::make_heap(result_first, out_last, comp, proj2); // process the rest of the input range (if any), preserving the heap propertyfor(; first!= last;++first){if(std::invoke(comp,std::invoke(proj1,*first),std::invoke(proj2,*result_first))){// pop out the biggest item and push in a newly found smaller oneranges::pop_heap(result_first, out_last, comp, proj2);*(out_last-1)=*first;ranges::push_heap(result_first, out_last, comp, proj2);}} // first N elements in the output range is still// a heap - convert it into a sorted rangeranges::sort_heap(result_first, out_last, comp, proj2); return{std::move(first), std::move(out_last)};} template<ranges::input_range R1,ranges::random_access_range R2,class Comp=ranges::less,class Proj1=std::identity,class Proj2=std::identity> requiresstd::indirectly_copyable<ranges::iterator_t<R1>,ranges::iterator_t<R2>>&&std::sortable<ranges::iterator_t<R2>, Comp, Proj2>&&std::indirect_strict_weak_order<Comp, std::projected<ranges::iterator_t<R1>, Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>>constexpr ranges::partial_sort_copy_result<ranges::borrowed_iterator_t<R1>,ranges::borrowed_iterator_t<R2>> operator()(R1&& r, R2&& result_r, Comp comp={}, Proj1 proj1={}, Proj2 proj2={})const{return(*this)(ranges::begin(r),ranges::end(r),ranges::begin(result_r),ranges::end(result_r), std::move(comp), std::move(proj1), std::move(proj2));}}; inlineconstexpr partial_sort_copy_fn partial_sort_copy{}; |
#include <algorithm>#include <forward_list>#include <functional>#include <iostream>#include <ranges>#include <string_view>#include <vector> void print(std::string_view rem, std::ranges::input_rangeautoconst& v){for(std::cout<< rem;constauto& e: v)std::cout<< e<<' ';std::cout<<'\n';} int main(){conststd::forward_list source{4,2,5,1,3}; print("Write to the smaller vector in ascending order: ",""); std::vector dest1{10,11,12}; print("const source list: ", source); print("destination range: ", dest1); std::ranges::partial_sort_copy(source, dest1); print("partial_sort_copy: ", dest1); print("Write to the larger vector in descending order:",""); std::vector dest2{10,11,12,13,14,15,16}; print("const source list: ", source); print("destination range: ", dest2); std::ranges::partial_sort_copy(source, dest2,std::greater{}); print("partial_sort_copy: ", dest2);}
Output:
Write to the smaller vector in ascending order:const source list: 4 2 5 1 3destination range: 10 11 12partial_sort_copy: 1 2 3Write to the larger vector in descending order:const source list: 4 2 5 1 3destination range: 10 11 12 13 14 15 16partial_sort_copy: 5 4 3 2 1 15 16
(C++20) | sorts the first N elements of a range (algorithm function object)[edit] |
(C++20) | sorts a range into ascending order (algorithm function object)[edit] |
(C++20) | sorts a range of elements while preserving order between equal elements (algorithm function object)[edit] |
(C++20) | turns a max heap into a range of elements sorted in ascending order (algorithm function object)[edit] |
(C++20) | creates a max heap out of a range of elements (algorithm function object)[edit] |
(C++20) | adds an element to a max heap (algorithm function object)[edit] |
(C++20) | removes the largest element from a max heap (algorithm function object)[edit] |
| copies and partially sorts a range of elements (function template)[edit] |
