| 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) |
Reorders the elements in[first, last) such that:
[first, last) were sorted with respect tocomp andproj.nth element areless than or equal to the elements after the newnth element. That is, for every iteratori,j in the ranges[first, nth),[nth, last) respectively, the expressionstd::invoke(comp,std::invoke(proj,*j),std::invoke(proj,*i)) evaluates tofalse.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 reorder |
| r | - | the range of elements to reorder |
| nth | - | the iterator defining the partition point |
| comp | - | comparator used to compare the projected elements |
| proj | - | projection to apply to the elements |
Linear inranges::distance(first, last) on average.
The algorithm used is typicallyintroselect although otherselection algorithms with suitable average-case complexity are allowed.
See also the implementation inmsvc stl,libstdc++, and libc++:(1) /(2).
#include <algorithm>#include <array>#include <functional>#include <iostream>#include <ranges>#include <string_view> void print(std::string_view rem, std::ranges::input_rangeautoconst& a){for(std::cout<< rem;constauto e: a)std::cout<< e<<' ';std::cout<<'\n';} int main(){std::array v{5,6,4,3,2,6,7,9,3}; print("Before nth_element: ", v); std::ranges::nth_element(v, v.begin()+ v.size()/2); print("After nth_element: ", v);std::cout<<"The median is: "<< v[v.size()/2]<<'\n'; std::ranges::nth_element(v, v.begin()+1,std::greater<int>()); print("After nth_element: ", v);std::cout<<"The second largest element is: "<< v[1]<<'\n';std::cout<<"The largest element is: "<< v[0]<<"\n\n"; usingnamespace std::literals;std::array names{"Diva"sv,"Cornelius"sv,"Munro"sv,"Rhod"sv,"Zorg"sv,"Korben"sv,"Bender"sv,"Leeloo"sv,}; print("Before nth_element: ", names);auto fifth_element{std::ranges::next(names.begin(),4)}; std::ranges::nth_element(names, fifth_element); print("After nth_element: ", names);std::cout<<"The 5th element is: "<<*fifth_element<<'\n';}
Output:
Before nth_element: 5 6 4 3 2 6 7 9 3 After nth_element: 2 3 3 4 5 6 6 7 9 The median is: 5After nth_element: 9 7 6 6 5 4 3 3 2 The second largest element is: 7The largest element is: 9 Before nth_element: Diva Cornelius Munro Rhod Zorg Korben Bender Leeloo After nth_element: Diva Cornelius Bender Korben Leeloo Rhod Munro Zorg The 5th element is: Leeloo
(C++20) | returns the largest element in a range (algorithm function object)[edit] |
(C++20) | returns the smallest element in a range (algorithm function object)[edit] |
(C++20) | divides a range of elements into two groups (algorithm function object)[edit] |
(C++20) | sorts the first N elements of a range (algorithm function object)[edit] |
| partially sorts the given range making sure that it is partitioned by the given element (function template)[edit] |
