GeezerVison is showing cpprefjp.github.io — std::ranges::nth_element - cpprefjp C++日本語リファレンス
最終更新日時:
2026年09月11日 13時06分31秒 (JST)
Akira Takahashi
が更新
function template
<algorithm>
std::ranges:: nth_element (C++20)
namespace std :: ranges {
template < random_access_iterator I ,
sentinel_for < I > S ,
class Comp = ranges::less ,
class Proj = identity >
requires sortable < I , Comp , Proj >
constexpr I
nth_element ( I first ,
I nth ,
S last ,
Comp comp = {},
Proj proj = {}); // (1) C++20
template < random_access_range R ,
class Comp = ranges::less ,
class Proj = identity >
requires sortable < iterator_t < R > , Comp , Proj >
constexpr borrowed_iterator_t < R >
nth_element ( R && r ,
iterator_t < R > nth ,
Comp comp = {},
Proj proj = {}); // (2) C++20
template < execution-policy Ep ,
random_access_iterator I ,
sized_sentinel_for < I > S ,
class Comp = ranges::less ,
class Proj = identity >
requires sortable < I , Comp , Proj >
I nth_element ( Ep && exec ,
I first ,
I nth ,
S last ,
Comp comp = {},
Proj proj = {}); // (3) C++26
template < execution-policy Ep ,
sized-random-access-range R ,
class Comp = ranges::less ,
class Proj = identity >
requires sortable < iterator_t < R > , Comp , Proj >
borrowed_iterator_t < R >
nth_element ( Ep && exec ,
R && r ,
iterator_t < R > nth ,
Comp comp = {},
Proj proj = {}); // (4) C++26
}
概要
基準となる要素よりも小さい要素が前に来るよう並べ替える。
(1): イテレータ範囲を指定する
(2): Rangeを直接指定する
(3): (1)の並列アルゴリズム版。実行ポリシーを指定する
(4): (2)の並列アルゴリズム版。実行ポリシーを指定する
この関数は範囲 [first,last) の並び替えを行うが、基準位置 nth のみが正しい要素、つまり仮に範囲 [first,last) 全体を並び替えた際にnthに位置すべき要素となる。前半の範囲 [first,nth) は関数呼び出し後の位置 nth にある要素よりも小さいことは保証されるが、その範囲 [first,nth) 内での要素並び順はなんら保証されない。
ある範囲に対して部分的な並び替えを行う場合、partial_sort() sort()
効果
(1) : nth_element() を呼び出した後、nth が指している位置の要素は、全ての範囲がソートされた場合の位置にある要素になる。そして、[first,nth) にあるイテレータ i と、[nth,last) にあるイテレータ j について、!(*j < *i) または comp(*j, *i) == false になる。
(2) : 以下と等価：
(3) : (1)と同じ効果を、指定された実行ポリシーexecに従って実行する。
(4) : 以下と等価：
戻り値
last
計算量
平均で線形時間
例
基本的な使い方
出力例
2
1
4
5
7
6
8
9
10
並列アルゴリズムの例 (C++26)
#include <iostream>
#include <vector>
#include <algorithm>
#include <execution>
int main ()
{
std::vector < int > v = { 5 , 10 , 4 , 7 , 1 , 9 , 8 , 6 , 2 };
// 並列に4番目に小さい値より小さい値を前に集める
std::ranges::nth_element ( std::execution::par , v , v.begin() + 3 );
std::cout << "4th element: " << v [ 3 ] << std::endl ;
for ( int i : v ) {
std::cout << i << ' ' ;
}
std::cout << std::endl ;
}
出力例
4th element: 5
2 1 4 5 7 6 8 9 10
バージョン
言語
処理系
参照