GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing cpprefjp.github.io — std::inplace_merge - cpprefjp C++日本語リファレンス

最終更新日時: 2026年08月25日 12時11分17秒 (JST)
Akira Takahashi が更新

function template

std::inplace_merge

namespace std {
  template <class BidirectionalIterator>
  void inplace_merge(BidirectionalIterator first,
                     BidirectionalIterator middle,
                     BidirectionalIterator last);  // (1) C++98
  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++98
  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;
  });
}

出力

実装例

inplace_merge を読んでみた

参照

P2562R1 constexpr Stable Sorting
- C++26からconstexprに対応した
LWG Issue 4196. Complexity of inplace_merge() is incorrect
- C++26で、余分なメモリを使用する場合の比較回数が「ちょうどN - 1回」から「最大でN - 1回」に修正された

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

GeezerVison

std::inplace_merge

概要

テンプレートパラメータ制約

事前条件

効果

戻り値

計算量

例

出力

実装例

関連項目

参照