「std::inplace merge」の版間の差分

2014年9月28日 (日) 02:05時点における版

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

読み方

std::inplace_merge

えすてぃーでぃー まーじ

概要

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

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

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

範囲を指定して、std::vectorをstd::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

関連項目

• std::vector
• std::thread スレッドを使用したソートの並列化