| 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) |
Constructs aheap with respect tocomp andproj from the elements in the specified range.
[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 3\cdot N\)3·N applications ofcomp and\(\scriptsize 6\cdot N\)6·N applications ofproj, where\(\scriptsize N \)N is:
#include <algorithm>#include <cmath>#include <functional>#include <iostream>#include <vector> void out(constauto& what,int n=1){while(n-->0)std::cout<< what;} void print(auto rem,constauto& v){ out(rem);for(auto e: v) out(e), out(' '); out('\n');} void draw_heap(constauto& v){auto bails=[](int n,int w){auto b=[](int w){ out("┌"), out("─", w), out("┴"), out("─", w), out("┐");};if(!(n/=2))return;for(out(' ', w); n-->0;) b(w), out(' ', w+ w+1); out('\n');}; auto data=[](int n,int w,auto& first,auto last){for(out(' ', w); n-->0&& first!= last;++first) out(*first), out(' ', w+ w+1); out('\n');}; auto tier=[&](int t,int m,auto& first,auto last){constint n{1<< t};constint w{(1<<(m- t-1))-1}; bails(n, w), data(n, w, first, last);}; constint m{static_cast<int>(std::ceil(std::log2(1+ v.size())))};auto first{v.cbegin()};for(int i{}; i!= m;++i) tier(i, m, first, v.cend());} int main(){std::vector h{1,6,1,8,0,3,3,9,8,8,7,4,9,8,9}; print("source: ", h); std::ranges::make_heap(h); print("\n""max-heap: ", h); draw_heap(h); std::ranges::make_heap(h,std::greater{}); print("\n""min-heap: ", h); draw_heap(h);}
Output:
source: 1 6 1 8 0 3 3 9 8 8 7 4 9 8 9 max-heap: 9 8 9 8 8 4 9 6 1 0 7 1 3 8 3 9 ┌───┴───┐ 8 9 ┌─┴─┐ ┌─┴─┐ 8 8 4 9┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐6 1 0 7 1 3 8 3 min-heap: 0 1 1 8 6 3 3 9 8 8 7 4 9 8 9 0 ┌───┴───┐ 1 1 ┌─┴─┐ ┌─┴─┐ 8 6 3 3┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐9 8 8 7 4 9 8 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) | 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] |
(C++20) | turns a max heap into a range of elements sorted in ascending order (algorithm function object)[edit] |
| creates a max heap out of a range of elements (function template)[edit] |
