std::inplace merge

提供: C++入門
2014年9月28日 (日) 02:19時点におけるDaemon (トーク | 投稿記録)による版

(差分) ←前の版 | 最新版 (差分) | 次の版→ (差分)
移動: 案内検索
スポンサーリンク

std::inplace_merge とは、2つのソート済みの範囲をマージするのに使用します。

読み方

std::inplace_merge
えすてぃーでぃー いんぷれいす まーじ

概要

first, middle と middle , last の連続した2つの範囲をマージして、 first , last に格納します。

たとえば、以下の std::vector には、部分的にソートされたデータが格納されています。前半(前3つ)と後半(後ろ3つ)がそれぞれソートされています。

vector<int> v = { 1,4,6, 2,3,5 };

範囲を指定して、std::vectorstd::inplace_mergeでソートできます。

1 2 3 4 5 6

計算量

  • 余分なメモリを使用する場合、 (last - fisrt ) - 1 回比較します。
  • それ以外の場合は、 N log(N) (N = last - first) 回程度比較します。

ヘッダファイル

#include <algorithm>

inplace_merge1.cpp の例

ソースコード inplace_merge1.cpp

/*
 * inplace_merge1.cpp
 * Copyright (C) 2014 kaoru <kaoru@bsd>
 */
 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int
main(int argc, char const* argv[])
{
        vector<int> v = { 1,4,6, 2,3,5 };
 
        inplace_merge(v.begin(), v.begin() + 3, v.end() );
        for(auto i: v) {
                cout << i << " ";
        }
        cout << endl;
        return 0;
}

コンパイル

c++ -std=c++11  inplace_merge1.cpp -o inplace_merge1

実行例

% ./inplace_merge1
1 2 3 4 5 6

関連項目




スポンサーリンク