std::ranges::partial_sort
From cppreference.com
| ヘッダー <algorithm> で定義 |
||
| 呼び出しシグネチャ |
||
| template< std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > |
(1) | (C++20以降) |
| template< ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity > |
(2) | (C++20以降) |
1) 要素を並べ替えて、範囲
[first, middle) が、範囲 [first, last) 内の middle - first 個の最小要素をソートされた状態で含むようにします。 等しい要素の順序は保持されることが保証されません。範囲
[middle, last) 内の残りの要素の順序は未指定です。 要素は、与えられた二項比較関数 comp を使用して比較され、proj 関数オブジェクトを使用して射影されます。
2) <span class="t-v">(1)</span> と同じですが、<code>r</code> を範囲として使用します。これは <code>ranges::begin(r)</code> を <code>first</code> として、<code>ranges::end(r)</code> を <code>last</code> として使用するのと同等です。
このページで説明されている関数のようなエンティティは、アルゴリズム関数オブジェクト（非公式にはニーブロイドとして知られている）です。つまり、
- これらのいずれかを呼び出す際に、明示的なテンプレート引数リストを指定することはできません。
- これらのいずれも実引数依存の名前探索には見えません。
- これらのいずれかが関数呼び出し演算子の左側の名前として通常の非修飾名探索によって見つかった場合、実引数依存の名前探索は抑制されます。
目次 |
[edit] Parameters
| first, last | - | 並べ替える要素の範囲を定義するイテレータ-センチネルペア |
| r | - | 並べ替える要素の範囲 |
| middle | - | 範囲 [first, middle) がソートされます |
| comp | - | 投影された要素に適用されるコンパレータ |
| proj | - | 要素に適用する射影 |
[edit] Return value
last と等しいイテレータ。
[edit] Complexity
𝓞(N·log(M)) 比較と、その2倍の射影。ここで N は ranges::distance(first, last) であり、M は ranges::distance(first, middle) です。
[edit] Possible implementation
struct partial_sort_fn { 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 operator()(I first, I middle, S last, Comp comp = {}, Proj proj = {}) const { if (first == middle) return ranges::next(first, last); ranges::make_heap(first, middle, comp, proj); auto it {middle}; for (; it != last; ++it) { if (std::invoke(comp, std::invoke(proj, *it), std::invoke(proj, *first))) { ranges::pop_heap(first, middle, comp, proj); ranges::iter_swap(middle - 1, it); ranges::push_heap(first, middle, comp, proj); } } ranges::sort_heap(first, middle, comp, proj); return it; } template<ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity> requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr ranges::borrowed_iterator_t<R> operator()(R&& r, ranges::iterator_t<R> middle, Comp comp = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), std::move(middle), ranges::end(r), std::move(comp), std::move(proj)); } }; inline constexpr partial_sort_fn partial_sort {}; |
[edit] Example
このコードを実行
#include <algorithm> #include <functional> #include <iostream> #include <string> #include <vector> void print(const auto& v) { for (const char e : v) std::cout << e << ' '; std::cout << '\n'; } void underscore(int n) { while (n-- > 0) std::cout << "^ "; std::cout << '\n'; } int main() { static_assert('A' < 'a'); std::vector<char> v {'x', 'P', 'y', 'C', 'z', 'w', 'P', 'o'}; print(v); const int m {3}; std::ranges::partial_sort(v, v.begin() + m); print(v), underscore(m); static_assert('1' < 'a'); std::string s {"3a1b41c5"}; print(s); std::ranges::partial_sort(s.begin(), s.begin() + m, s.end(), std::greater {}); print(s), underscore(m); }
出力
x P y C z w P o C P P y z x w o ^ ^ ^ 3 a 1 b 4 1 c 5 c b a 1 3 1 4 5 ^ ^ ^
[edit] See also
| (C++20) |
要素の範囲をコピーして部分的にソートする (アルゴリズム関数オブジェクト) |
| (C++20) |
範囲を昇順にソートする (アルゴリズム関数オブジェクト) |
| (C++20) |
等しい要素間の順序を維持しながら要素の範囲をソートする (アルゴリズム関数オブジェクト) |
| (C++20) |
与えられた範囲を部分的にソートし、指定された要素によってパーティション化されるようにする (アルゴリズム関数オブジェクト) |
| (C++20) |
要素の範囲から最大ヒープを作成する (アルゴリズム関数オブジェクト) |
| (C++20) |
最大ヒープから最大の要素を削除する (アルゴリズム関数オブジェクト) |
| (C++20) |
最大ヒープに要素を追加する (アルゴリズム関数オブジェクト) |
| (C++20) |
最大ヒープを昇順にソートされた要素の範囲に変換する (アルゴリズム関数オブジェクト) |
| 範囲の最初のN個の要素をソートする (関数テンプレート) |
