std::nth_element

 

C++

言語

ヘッダ

コンセプト

言語サポートライブラリ

診断ライブラリ

ユーティリティライブラリ

文字列ライブラリ

コンテナライブラリ

アルゴリズムライブラリ

イテレータライブラリ

数値演算ライブラリ

入出力ライブラリ

ローカライゼーションライブラリ

正規表現ライブラリ(C++11)

アトミック操作ライブラリ(C++11)

スレッドサポートライブラリ(C++11)

ファイルシステムライブラリ(C++17)

技術仕様書

 

アルゴリズムライブラリ

実行ポリシー (C++17)
is_execution_policy	execution::seqexecution::parexecution::par_unseq	execution::sequenced_policyexecution::parallel_policyexecution::parallel_unsequenced_policy
非変更シーケンス操作
all_ofany_ofnone_of (C++11)(C++11)(C++11) for_each for_each_n (C++17)	countcount_if mismatch equal adjacent_find	findfind_iffind_if_not (C++11) find_end find_first_of	search search_n lexicographical_compare lexicographical_compare_3way (C++20)
変更シーケンス操作
copycopy_if (C++11) copy_n (C++11) copy_backward move (C++11) move_backward (C++11) transform	fill fill_n generate generate_n swap iter_swap swap_ranges sample (C++17)	removeremove_if replacereplace_if reverse rotate unique random_shuffle (C++17以前)	remove_copyremove_copy_if replace_copyreplace_copy_if reverse_copy rotate_copy unique_copy shuffle (C++11)
未初期化記憶域の操作
uninitialized_copy uninitialized_move (C++17)	uninitialized_copy_n (C++11) uninitialized_move_n (C++17)	uninitialized_fill	uninitialized_fill_n
分割操作
is_partitioned (C++11) partition_point (C++11)	partition partition_copy (C++11)	stable_partition
ソート操作
is_sorted (C++11) is_sorted_until (C++11)	sort stable_sort	partial_sort partial_sort_copy	nth_element
バイナリサーチ操作
lower_bound	upper_bound	binary_search	equal_range
集合操作 (ソート済み範囲に対する)
merge inplace_merge	set_difference set_intersection	set_symmetric_difference set_union	includes
ヒープ操作
is_heap (C++11) is_heap_until (C++11)	make_heap sort_heap	push_heap pop_heap
最小/最大演算
max max_element	min min_element	minmax (C++11) minmax_element (C++11)	clamp (C++17) compare_3way (C++20)
順列
is_permutation (C++11)	next_permutation	prev_permutation
数値演算
iota (C++11) inner_product adjacent_difference	accumulate reduce (C++17) transform_reduce (C++17)	partial_sum inclusive_scan (C++17) exclusive_scan (C++17)	transform_inclusive_scan (C++17) transform_exclusive_scan (C++17)
C のライブラリ
qsort	bsearch

 

ヘッダ <algorithm> で定義
template<class RandomIt > void nth_element( RandomIt first, RandomIt nth, RandomIt last );	(1)
template<class RandomIt, class Compare > void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );	(2)

部分的にソートされるように昇順で範囲[first, last)範囲内のすべての要素[first, nth)アール範囲[nth, last)に比べて少ない。最初のバージョンは、要素を比較するoperator<使用して、2番目のバージョンは、指定された比較関数compを使用しています。 nth位置に配置要素は、正確に範囲が完全にソートされていた場合、この位置に現れることになる要素です.

Original:

Partially sorts the range [first, last) in ascending order so that all elements in the range [first, nth) are less than those in the range [nth, last). The first version uses operator< to compare the elements, the second version uses the given comparison function comp. The element placed in the nth position is exactly the element that would occur in this position if the range was fully sorted.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

パラメータ

first, last	-	範囲のソートを定義するランダムアクセス反復子 Original: random access iterators defining the range sort The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
nth	-	ソート·パーティション·ポイントを定義するランダムアクセス反復子を返します Original: random access iterator defining the sort partition point The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
comp	-	比較関数. 最初の値が二つ目の値より小さい 場合、 ​trueを返します. 比較関数のシグネチャは以下と同等でなければなりません.  bool cmp(const Type1 &a, const Type2 &b); シグネチャはconstを含まなくても構いませんが, 比較関数は渡されたオブジェクトを変更してはなりません. 型 Type1 および Type2 は、どちらも RandomIt 型のオブジェクトの逆参照から暗黙に変換可能なものでなければなりません。 ​
型の要件
- RandomIt は ValueSwappable および RandomAccessIterator の要件を満たさなければなりません。
- The type of dereferenced RandomIt must meet the requirements of MoveAssignable and MoveConstructible.

値を返します

(なし)

複雑性

平均でstd::distance(first, last)におけるリニア.

Original:

Linear in std::distance(first, last) on average.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

例

Run this code

#include <iostream>#include <vector>#include <algorithm>#include <functional>   int main(){std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};   std::nth_element(v.begin(), v.begin()+ v.size()/2, v.end());std::cout<<"The median is "<< v[v.size()/2]<<'\n';   std::nth_element(v.begin(), v.begin()+1, v.end(), std::greater<int>());std::cout<<"The second largest element is "<< v[1]<<'\n';}

出力:

The median is 5 The second largest element is 7

参照

partial_sort_copy	指定範囲の最初の N 個の要素がソートされたコピーを作成します (関数テンプレート)
stable_sort	等しい要素間の順序を維持しながら指定範囲の要素をソートします (関数テンプレート)
sort	指定範囲を昇順にソートします (関数テンプレート)