listクラスでソートせずにリスト同士の連結

前にlistクラスのmerge関数でリスト同士の連結をする方法を勉強しました。

ですがmerge関数だと元のデータがソートされていた場合、連結後のデータも勝手にソートしてしまいます。

ソートをせずに連結する方法を、コメント欄で教えてもらったので動作確認してみます。

まずはinsert関数を使う方法です。

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

int main () {
    list<int> xs;
    list<int> ys;

    xs.push_back(20);
    xs.push_back(30);
    xs.push_back(60);

    ys.push_back(40);
    ys.push_back(50);
    ys.push_back(80);

    xs.insert(xs.end(), ys.begin(), ys.end());
    
    list<int>::iterator it = xs.begin();
    
    while( it != xs.end() ) {
        cout << *it << endl;
        ++it;
    }
    
    return 0;
}

xs変数のinsert関数を呼び、xsの最後の要素を指す場所から、ysのイテレータが指す最初の要素から最後の要素までを追加します。

こうすればxsの後ろにysが連結される感じになります。

お次はsplice関数を使う方法です。

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

int main () {
    list<int> xs;
    list<int> ys;

    xs.push_back(20);
    xs.push_back(30);
    xs.push_back(60);

    ys.push_back(40);
    ys.push_back(50);
    ys.push_back(80);

    xs.splice(xs.end(), ys);
    
    list<int>::iterator it = xs.begin();
    
    while( it != xs.end() ) {
        cout << *it << endl;
        ++it;
    }
    
    return 0;
}

こちらもinsert関数を似ていますが、第二引数にysそのものを渡すことができます。

spliceを使って連結させる方がinsertよりも効率が良いらしいです。

ちなみに僕が初めに考えた方法はysのイテレータでループし、xsのpush_back関数で一つずつ突っ込む方法でした。どう考えても効率悪いですよね。

用途によって使い分けが必要ですね。