| 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) |
Swaps the first element and the last element of the specifiedheap with respect tocomp andproj and makes the subrange excluding the first position into a heap with respect tocomp andproj. This has the effect of removing the first element from the specified heap.
[first, last).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 2\log{(N)}\)2log(N) applications ofcomp and\(\scriptsize 4\log{(N)}\)4log(N) applications ofproj, where\(\scriptsize N \)N is:
#include <algorithm>#include <array>#include <iostream>#include <iterator>#include <string_view> template<class I=int*>void print(std::string_view rem, I first={}, I last={},std::string_view term="\n"){for(std::cout<< rem; first!= last;++first)std::cout<<*first<<' ';std::cout<< term;} int main(){std::array v{3,1,4,1,5,9,2,6,5,3}; print("initially, v: ", v.cbegin(), v.cend()); std::ranges::make_heap(v); print("make_heap, v: ", v.cbegin(), v.cend()); print("convert heap into sorted array:");for(auto n{std::ssize(v)}; n>=0;--n){ std::ranges::pop_heap(v.begin(), v.begin()+ n); print("[ ", v.cbegin(), v.cbegin()+ n,"] "); print("[ ", v.cbegin()+ n, v.cend(),"]\n");}}
Output:
initially, v: 3 1 4 1 5 9 2 6 5 3make_heap, v: 9 6 4 5 5 3 2 1 1 3convert heap into sorted array:[ 6 5 4 3 5 3 2 1 1 9 ] [ ][ 5 5 4 3 1 3 2 1 6 ] [ 9 ][ 5 3 4 1 1 3 2 5 ] [ 6 9 ][ 4 3 3 1 1 2 5 ] [ 5 6 9 ][ 3 2 3 1 1 4 ] [ 5 5 6 9 ][ 3 2 1 1 3 ] [ 4 5 5 6 9 ][ 2 1 1 3 ] [ 3 4 5 5 6 9 ][ 1 1 2 ] [ 3 3 4 5 5 6 9 ][ 1 1 ] [ 2 3 3 4 5 5 6 9 ][ 1 ] [ 1 2 3 3 4 5 5 6 9 ][ ] [ 1 1 2 3 3 4 5 5 6 9 ]
(C++20) | adds an element to a max heap (algorithm function object)[edit] |
(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) | turns a max heap into a range of elements sorted in ascending order (algorithm function object)[edit] |
| removes the largest element from a max heap (function template)[edit] |
