最終更新日時: 2026年04月13日 15時17分49秒 (JST)
teruyamato0731 が更新

履歴 編集

function template
<algorithm>

# std::inplace_merge

    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)` はそれぞれ `operator<` か `comp` でソートされていること。

## 効果

`[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;
      });
    }

### 出力

    1
    2
    3
    4
    5
    6

## 実装例

- `inplace_merge` を読んでみた

## 関連項目

- `ranges::inplace_merge`

## 参照

- P2562R1 `constexpr` Stable Sorting
  - C++26から`constexpr`に対応した