nth_element rearranges elements in[first, last) such that after the rearrangement:

• The element pointed at bynth is changed to whatever element would occur in that position if[first, last) were sorted.
• For every iteratori in[first, nth) and every iteratorj in[nth, last), the following condition is met:

If any of the following conditions is satisfied, the behavior is undefined:

• [first, nth) or[nth, last) is not avalid range.

[edit]Parameters

[edit]Complexity

Given\(\scriptsize N\)N aslast- first:

[edit]Exceptions

The overloads with a template parameter namedExecutionPolicy report errors as follows:

• If execution of a function invoked as part of the algorithm throws an exception andExecutionPolicy is one of thestandard policies,std::terminate is called. For any otherExecutionPolicy, the behavior is implementation-defined.
• If the algorithm fails to allocate memory,std::bad_alloc is thrown.

[edit]Possible implementation

See also the implementations inlibstdc++,libc++, andMSVC STL.

[edit]Notes

The algorithm used is typicallyIntroselect although otherSelection algorithm with suitable average-case complexity are allowed.

[edit]Example

#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);}

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};

[edit]Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

[edit]See also

• In other languages

• Deutsch
• Español
• Français
• Italiano
• 日本語
• Português
• Русский
• 中文