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 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Defined in header <algorithm> | ||
template<class RandomIt> void nth_element( RandomIt first, RandomIt nth, RandomIt last); | (1) | (constexpr since C++20) |
template<class ExecutionPolicy,class RandomIt> void nth_element( ExecutionPolicy&& policy, | (2) | (since C++17) |
template<class RandomIt,class Compare> void nth_element( RandomIt first, RandomIt nth, RandomIt last, | (3) | (constexpr since C++20) |
template<class ExecutionPolicy,class RandomIt,class Compare> void nth_element( ExecutionPolicy&& policy, | (4) | (since C++17) |
nth_element
rearranges elements in[
first,
last)
such that after the rearrangement:
[
first,
last)
were sorted.[
first,
nth)
and every iteratorj in[
nth,
last)
, the following condition is met:std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> istrue. | (until C++20) |
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> istrue. | (since C++20) |
If any of the following conditions is satisfied, the behavior is undefined:
[
first,
nth)
or[
nth,
last)
is not avalid range.
| (until C++11) |
| (since C++11) |
Contents |
first, last | - | the pair of iterators defining therange of elements for partial sorting |
nth | - | random access iterator defining the sort partition point |
policy | - | theexecution policy to use |
comp | - | comparison function object (i.e. an object that satisfies the requirements ofCompare) which returns true if the first argument isless than (i.e. is orderedbefore) the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1& a,const Type2& b); While the signature does not need to haveconst&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) |
Type requirements | ||
-RandomIt must meet the requirements ofLegacyRandomAccessIterator. | ||
-Compare must meet the requirements ofCompare. |
Given\(\scriptsize N\)N aslast- first:
The overloads with a template parameter namedExecutionPolicy
report errors as follows:
ExecutionPolicy
is one of thestandard policies,std::terminate is called. For any otherExecutionPolicy
, the behavior is implementation-defined.See also the implementations inlibstdc++,libc++, andMSVC STL.
The algorithm used is typicallyIntroselect although otherSelection algorithm with suitable average-case complexity are allowed.
#include <algorithm>#include <cassert>#include <functional>#include <iostream>#include <numeric>#include <vector> void printVec(conststd::vector<int>& vec){std::cout<<"v = {";for(char sep[]{0,' ',0};constint i: vec)std::cout<< sep<< i, sep[0]=',';std::cout<<"};\n";} int main(){std::vector<int> v{5,10,6,4,3,2,6,7,9,3}; printVec(v); auto m= v.begin()+ v.size()/2; std::nth_element(v.begin(), m, v.end());std::cout<<"\nThe median is "<< v[v.size()/2]<<'\n';// The consequence of the inequality of elements before/after the Nth one:assert(std::accumulate(v.begin(), m,0)<std::accumulate(m, v.end(),0)); printVec(v); // Note: comp function changed std::nth_element(v.begin(), v.begin()+1, v.end(),std::greater{});std::cout<<"\nThe second largest element is "<< v[1]<<'\n';std::cout<<"The largest element is "<< v[0]<<'\n'; printVec(v);}
Possible output:
v = {5, 10, 6, 4, 3, 2, 6, 7, 9, 3}; The median is 6v = {3, 2, 3, 4, 5, 6, 10, 7, 9, 6}; The second largest element is 9The largest element is 10v = {10, 9, 6, 7, 6, 3, 5, 4, 3, 2};
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
DR | Applied to | Behavior as published | Correct behavior |
---|---|---|---|
LWG 2150 | C++98 | after the rearrangement, only one element beforenth was required to be not greater than one element afternth | corrected the requirement |
LWG 2163 | C++98 | overload(1) usedoperator> to compare the elements | changed tooperator< |
P0896R4 | C++98 | [ first, nth) and[ nth, last) were not required to be valid ranges | the behavior is undefined if any of them is invalid |
returns the largest element in a range (function template)[edit] | |
returns the smallest element in a range (function template)[edit] | |
copies and partially sorts a range of elements (function template)[edit] | |
sorts a range of elements while preserving order between equal elements (function template)[edit] | |
sorts a range into ascending order (function template)[edit] | |
(C++20) | partially sorts the given range making sure that it is partitioned by the given element (algorithm function object)[edit] |