STL list

リストはsort()関数でソートすることができる。そしてソートされたリスト同士をmerge()関数でマージすることもできる。

#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> l1,l2;

    // ランダムな値でリストを作成
    for(int i=0; i<5; i++) {
        l1.push_back(rand());
        l2.push_back(rand());
    }

    // リストをソート
    l1.sort();
    l2.sort();

    list<int>::iterator p;

    p = l1.begin();
    while( p != l1.end() ) {
        cout << *p << " ";
        ++p;
    }
    cout << endl;
    
    p = l2.begin();
    while( p != l2.end() ) {
        cout << *p << " ";
        ++p;
    }
    cout << endl;

    // l2の内容をl1にマージ
    l1.merge(l2);

    p = l1.begin();
    while( p != l1.end() ) {
        cout << *p << " ";
        ++p;
    }
}

実行結果
41 6334 11478 19169 26962
15724 18467 24464 26500 29358
41 6334 11478 15724 18467 19169 24464 26500 26962 29358

merge()関数の引数となったリストの内容は空となる。
ソートしていないリストで試したが、どういう順番でマージされているのかはよく分からなかった。たぶん、要素1個ずつ比較しながら追加していっていると思うんだけど。