| 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::random_access_iterator I,std::sentinel_for<I> S, class Comp=ranges::less,class Proj=std::identity> | (1) | (since C++20) |
template<ranges::random_access_range R, class Comp=ranges::less,class Proj=std::identity> | (2) | (since C++20) |
Sorts the elements in the specified range with respect tocomp andproj, where the range originally represents aheap with respect tocomp andproj. The sorted range no longer maintains the heap property.
[first, last).If the specified range is not a heap with respect tocomp andproj, the behavior is undefined.
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 modify |
| r | - | therange of elements to modify |
| comp | - | comparator to apply to the projected elements |
| proj | - | projection to apply to the elements |
At most\(\scriptsize 2N \cdot \log(N)\)2N⋅log(N) applications ofcomp and\(\scriptsize 4N \cdot \log(N)\)4N⋅log(N) applications ofproj, where\(\scriptsize N \)N is:
struct sort_heap_fn{template<std::random_access_iterator I,std::sentinel_for<I> S,class Comp=ranges::less,class Proj=std::identity> requiresstd::sortable<I, Comp, Proj>constexpr I operator()(I first, S last, Comp comp={}, Proj proj={})const{auto ret{ranges::next(first, last)};for(auto last{ret}; first!= last;--last)ranges::pop_heap(first, last, comp, proj);return ret;} template<ranges::random_access_range R,class Comp=ranges::less,class Proj=std::identity> requiresstd::sortable<ranges::iterator_t<R>, Comp, Proj>constexprranges::borrowed_iterator_t<R> operator()(R&& r, Comp comp={}, Proj proj={})const{return(*this)(ranges::begin(r),ranges::end(r), std::move(comp), std::move(proj));}}; inlineconstexpr sort_heap_fn sort_heap{}; |
#include <algorithm>#include <array>#include <iostream> void print(autoconst& rem,constauto& v){std::cout<< rem;for(constauto i: v)std::cout<< i<<' ';std::cout<<'\n';} int main(){std::array v{3,1,4,1,5,9}; print("original array: ", v); std::ranges::make_heap(v); print("after make_heap: ", v); std::ranges::sort_heap(v); print("after sort_heap: ", v);}
Output:
original array: 3 1 4 1 5 9after make_heap: 9 5 4 1 1 3after sort_heap: 1 1 3 4 5 9
(C++20) | checks if the given range is a max heap (algorithm function object)[edit] |
(C++20) | finds the largest subrange that is a max heap (algorithm function object)[edit] |
(C++20) | creates a max heap out of a range of elements (algorithm function object)[edit] |
(C++20) | removes the largest element from a max heap (algorithm function object)[edit] |
(C++20) | adds an element to a max heap (algorithm function object)[edit] |
| turns a max heap into a range of elements sorted in ascending order (function template)[edit] |
