std::ranges::nth_element
ja.cppreference.net より
| (C++23) <algorithm>
|
||
| ヘッダ |
||
template< std::random_access_iterator I, std::sentinel_for<I> S,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
constexpr I
nth_element( I first, I nth, S last, Comp comp = {}, Proj proj = {} );
|
で定義 | 呼び出しシグネチャ |
template< ranges::random_access_range R,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<iterator_t<R>, Comp, Proj>
constexpr ranges::borrowed_iterator_t<R>
nth_element( R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {} );
|
(1) | (C++20 以降) |
(2) [first, last)(C++20 以降)
nth内の要素を次のように並べ替えます:[first,last)compが指す要素は、projが- と
nthに関してソートされた場合にその位置に現れる要素に変更されます。この新しい 要素より前のすべての要素は、新しいnth要素より後の要素 以下です。つまり、範囲 と 内のすべてのイテレータ[first,nth)i[nth,last),std::invoke(comp, std::invoke(proj, *j), std::invoke(proj, *i))jfalseについて、式 - は
nth == lastと評価されます。
の場合、関数は何も行いません。
comp1)proj 要素は、指定された二項比較関数オブジェクト と射影オブジェクト を使用して比較されます。2) (1) と同じですが、
r を範囲として使用し、ranges::begin(r) を first として、ranges::end(r) を last として使用するかのように動作します。このページで説明されている関数のようなエンティティは アルゴリズム関数オブジェクト (非公式に niebloids として知られる) であり、次の特性を持ちます:
- それらのいずれかを呼び出す際に、明示的なテンプレート引数リストを指定することはできません。
- それらのいずれも 引数依存の名前探索 には見えません。
- それらのいずれかが 通常の非修飾名前探索 によって関数呼び出し演算子の左側の名前として見つかった場合、引数依存の名前探索 は抑制されます。
パラメータ
| first, last | - | 要素を並べ替える範囲を定義する 範囲 のイテレータ-センチネルペア |
| r | - | 並べ替える要素の範囲 |
| nth | - | 分割点を定義するイテレータ |
| comp | - | 投影された要素を比較するために使用される比較関数 |
| proj | - | 要素に適用する投影関数 |
戻り値
1)
last
に等しいイテレータ。
計算量
平均的に ranges:: distance ( first, last ) の計算量は線形です。
注記
使用されるアルゴリズムは通常 introselect ですが、適切な平均ケース計算量を持つ他の selection algorithms も使用可能です。
実装例
実装については msvc stl 、 libstdc++ および libc++ も参照してください: (1) / (2) 。
例
このコードを実行
#include <algorithm> #include <array> #include <functional> #include <iostream> #include <ranges> #include <string_view> void print(std::string_view rem, std::ranges::input_range auto const& a) { for (std::cout << rem; const auto e : a) std::cout << e << ' '; std::cout << '\n'; } int main() { std::array v{5, 6, 4, 3, 2, 6, 7, 9, 3}; print("Before nth_element: ", v); std::ranges::nth_element(v, v.begin() + v.size() / 2); print("After nth_element: ", v); std::cout << "The median is: " << v[v.size() / 2] << '\n'; std::ranges::nth_element(v, v.begin() + 1, std::greater<int>()); print("After nth_element: ", v); std::cout << "The second largest element is: " << v[1] << '\n'; std::cout << "The largest element is: " << v[0] << "\n\n"; using namespace std::literals; std::array names { "Diva"sv, "Cornelius"sv, "Munro"sv, "Rhod"sv, "Zorg"sv, "Korben"sv, "Bender"sv, "Leeloo"sv, }; print("Before nth_element: ", names); auto fifth_element{std::ranges::next(names.begin(), 4)}; std::ranges::nth_element(names, fifth_element); print("After nth_element: ", names); std::cout << "The 5th element is: " << *fifth_element << '\n'; }
出力:
Before nth_element: 5 6 4 3 2 6 7 9 3 After nth_element: 2 3 3 4 5 6 6 7 9 The median is: 5 After nth_element: 9 7 6 6 5 4 3 3 2 The second largest element is: 7 The largest element is: 9 Before nth_element: Diva Cornelius Munro Rhod Zorg Korben Bender Leeloo After nth_element: Diva Cornelius Bender Korben Leeloo Rhod Munro Zorg The 5th element is: Leeloo
関連項目
(C++20) |
範囲内の最大の要素を返す (アルゴリズム関数オブジェクト) |
(C++20) |
範囲内の最小の要素を返す (アルゴリズム関数オブジェクト) |
(C++20) |
範囲内の要素を2つのグループに分割する (アルゴリズム関数オブジェクト) |
(C++20) |
範囲の最初のN個の要素をソートする (アルゴリズム関数オブジェクト) |
| 範囲がソートされた場合のN番目の要素を見つける (関数テンプレート) |