GeezerVison is showing cpprefjp.github.io — std::nth_element - cpprefjp C++日本語リファレンス
最終更新日時:
2026年08月26日 10時32分02秒 (JST)
Akira Takahashi
が更新
function template
<algorithm>
std:: nth_element
namespace std {
template < class RandomAccessIterator >
void nth_element ( RandomAccessIterator first ,
RandomAccessIterator nth ,
RandomAccessIterator last ); // (1) C++98
template < class RandomAccessIterator >
constexpr void nth_element ( RandomAccessIterator first ,
RandomAccessIterator nth ,
RandomAccessIterator last ); // (1) C++20
template < class RandomAccessIterator , class Compare >
void nth_element ( RandomAccessIterator first ,
RandomAccessIterator nth ,
RandomAccessIterator last ,
Compare comp ); // (2) C++98
template < class RandomAccessIterator , class Compare >
constexpr void nth_element ( RandomAccessIterator first ,
RandomAccessIterator nth ,
RandomAccessIterator last ,
Compare comp ); // (2) C++20
template < class ExecutionPolicy , class RandomAccessIterator >
void nth_element ( ExecutionPolicy && exec ,
RandomAccessIterator first ,
RandomAccessIterator nth ,
RandomAccessIterator last ); // (3) C++17
template < class ExecutionPolicy , class RandomAccessIterator , class Compare >
void nth_element ( ExecutionPolicy && exec ,
RandomAccessIterator first ,
RandomAccessIterator nth ,
RandomAccessIterator last ,
Compare comp ); // (4) C++17
}
概要
基準となる要素よりも小さい要素が前に来るよう並べ替える。
この関数はイテレータ範囲 [first,last) の並び替えを行うが、基準位置 nth のみが正しい要素、つまり仮に範囲 [first,last) 全体を並び替えた際にnthに位置すべき要素となる。前半のイテレータ範囲 [first,nth) は関数呼び出し後の位置 nth にある要素よりも小さいことは保証されるが、そのイテレータ範囲 [first,nth) 内での要素並び順はなんら保証されない。
あるイテレータ範囲に対して部分的な並び替えを行う場合は、partial_sort() sort()
テンプレートパラメータ制約
RandomAccessIterator は ValueSwappable の要件を満たしている必要がある。*first の型は MoveConstructible と MoveAssignable の要件を満たしている必要がある。
効果
nth_element() を呼び出した後、nth が指している位置の要素は、全ての範囲がソートされた場合の位置にある要素になる。ただしnth == lastである場合、この規定は適用されない。そして、[first,nth) にあるイテレータ i と、[nth,last) にあるイテレータ j について、!(*j < *i) または comp(*j, *i) == false になる。
戻り値
なし
計算量
(1), (2) : 平均で線形時間
(3), (4) : N = last - firstであるとして、O(N)回だけ比較または述語の適用と、O(NlogN)回だけswap操作を行う
例
#include <iostream>
#include <vector>
#include <algorithm>
int main ()
{
std::vector < int > v = { 5 , 10 , 4 , 7 , 1 , 9 , 8 , 6 , 2 };
// 4番目に小さい値より小さい値を前に集める
std::nth_element ( v.begin() , v.begin() + 3 , v.end() );
std::for_each ( v.begin() , v.end() , []( int x ) {
std::cout << x << std::endl ;
});
}
出力例
2
1
4
5
10
9
8
6
7
関連項目
参照