| 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 Proj=std::identity, | (1) | (since C++20) |
template<ranges::random_access_range R,class Proj=std::identity, std::indirect_strict_weak_order | (2) | (since C++20) |
Within the specified range, finds the longest range which starting from the beginning of the specified range and represents aheap with respect tocomp andproj.
[first, last).The function-like entities described on this page arealgorithm function objects (informally known asniebloids), that is:
Contents |
| first, last | - | the range of elements to examine |
| r | - | the range of elements to examine |
| pred | - | predicate to apply to the projected elements |
| proj | - | projection to apply to the elements |
The last iteratoriter in the specified range for which:
[first, iter) is a heap with respect tocomp andproj.\(\scriptsize O(N) \)O(N) applications ofcomp andproj, where\(\scriptsize N \)N is:
struct is_heap_until_fn{template<std::random_access_iterator I,std::sentinel_for<I> S,class Proj=std::identity,std::indirect_strict_weak_order<std::projected<I, Proj>> Comp=ranges::less>constexpr I operator()(I first, S last, Comp comp={}, Proj proj={})const{std::iter_difference_t<I> n{ranges::distance(first, last)}, dad{0}, son{1};for(; son!= n;++son){if(std::invoke(comp,std::invoke(proj,*(first+ dad)),std::invoke(proj,*(first+ son))))return first+ son;elseif((son%2)==0)++dad;}return first+ n;} template<ranges::random_access_range R,class Proj=std::identity,std::indirect_strict_weak_order<std::projected<ranges::iterator_t<R>, Proj>> Comp=ranges::less>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 is_heap_until_fn is_heap_until{}; |
The example renders a given vector as a (balanced)Binary tree.
#include <algorithm>#include <cmath>#include <iostream>#include <iterator>#include <vector> void out(constauto& what,int n=1){while(n-->0)std::cout<< what;} void draw_bin_tree(auto first,auto last){auto bails=[](int n,int w){auto b=[](int w){ out("┌"), out("─", w), out("┴"), out("─", w), out("┐");}; n/=2;if(!n)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);}; constauto size{std::ranges::distance(first, last)};constint m{static_cast<int>(std::ceil(std::log2(1+ size)))};for(int i{}; i!= m;++i) tier(i, m, first, last);} int main(){std::vector<int> v{3,1,4,1,5,9}; std::ranges::make_heap(v); // probably mess up the heap v.push_back(2); v.push_back(6); out("v after make_heap and push_back:\n"); draw_bin_tree(v.begin(), v.end()); out("the max-heap prefix of v:\n");constauto heap_end= std::ranges::is_heap_until(v); draw_bin_tree(v.begin(), heap_end);}
Output:
v after make_heap and push_back: 9 ┌───┴───┐ 5 4 ┌─┴─┐ ┌─┴─┐ 1 1 3 2 ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ 6 the max-heap prefix of v: 9 ┌─┴─┐ 5 4 ┌┴┐ ┌┴┐ 1 1 3 2
(C++20) | checks if the given range 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) | 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] |
(C++11) | finds the largest subrange that is a max heap (function template)[edit] |
