namespace std {
template <class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last); // (1) C++03
template <class BidirectionalIterator>
constexpr
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last); // (1) C++26
template <class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last,
Compare comp); // (2) C++03
template <class BidirectionalIterator, class Compare>
constexpr
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last,
Compare comp); // (2) C++26
template <class ExecutionPolicy, class BidirectionalIterator>
void inplace_merge(ExecutionPolicy&& exec,
BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last); // (3) C++17
template <class ExecutionPolicy, class BidirectionalIterator, class Compare>
void inplace_merge(ExecutionPolicy&& exec,
BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last,
Compare comp); // (4) C++17
}
概要
2つの連続したソート済みイテレータ範囲[first, middle)と[middle, last)をマージする。
この関数は、ソート済みイテレータ範囲[first, middle)と、ソート済み範囲[middle, last)のように大きいイテレータ範囲[first, last)内に2つのソート済みイテレータ範囲が含まれている場合に、それらをマージしてソートする。
テンプレートパラメータ制約
BidirectionalIteratorはValueSwappableの要件を満たしていること。*firstの型はMoveConstructibleとMoveAssignableの要件を満たしていること。
事前条件
効果
[first,middle), [middle,last) という、連続した２つの範囲をマージし、結果を [first,last) へ格納する。
結果のイテレータ範囲 [first,last) は昇順になる。つまり、first を除く [first,last) 内の全てのイテレータ i について、*i < *(i - 1) または comp(*i, *(i - 1)) が false になる。
戻り値
なし
計算量
N = last - firstであるとして説明する。
- (1), (2) : 余分なメモリを使用する場合は、
N - 1回比較する。そうでない場合は、O(N log(N))回比較する - (3), (4) : O(N log N)回比較する
例
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> v = {1,4,5, 2,3,6};
// ソートされた2つのイテレータ範囲をマージ
std::inplace_merge(v.begin(), v.begin() + 3, v.end());
std::for_each(v.begin(), v.end(), [](int x) {
std::cout << x << std::endl;
});
}
16
#include <iostream>#include <vector>#include <algorithm>int main(){ std::vector<int> v = {1,4,5, 2,3,6}; // ソートされた2つのイテレータ範囲をマージ std::inplace_merge(v.begin(), v.begin() + 3, v.end()); std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << std::endl; });}出力
1
2
3
4
5
6
実装例
参照
- P2562R1
constexprStable Sorting- C++26から
constexprに対応した
- C++26から