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

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

listクラスでリスト同士の連結 - (void*)Pないと

ですが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;
}

20
30
60
40
50
80

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関数で一つずつ突っ込む方法でした。どう考えても効率悪いですよね。

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

bitsetクラスを自作する

昨日勉強したbitsetクラスですが、題材としてとても面白そうだと思ったので自作してみることにしました。

テンプレートクラスとビット演算に慣れるという意味でもちょうど良いと思います。

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

template<unsigned long SIZE>
class mybitset {
public:
    mybitset () { m_bit = 0; }
    mybitset (unsigned long bit) { m_bit = bit; }
    
    mybitset<SIZE>& set () {
        m_bit = (1 << SIZE) - 1;
        return *this;
    }
    
    mybitset<SIZE>& set (size_t pos,int val=1) {
        if ( SIZE <= pos ) {
            err();
        }
        if ( val ) {
            m_bit |= (1 << pos);
        }
        else {
            m_bit &= ~(1 << pos);
        }
        return *this;
    }
    
    mybitset<SIZE>& reset () {
        m_bit = 0;
        return *this;
    }
    
    mybitset<SIZE>& reset(size_t pos) {
        if ( SIZE <= pos ) {
            err();
        }
        return set(pos,0);
    }
    
    mybitset<SIZE>& flip() {
        m_bit = ~m_bit;
        m_bit &= (1 << SIZE) - 1;
        return *this;
    }
    
    mybitset<SIZE>& flip(size_t pos) {
        if ( SIZE <= pos ) {
            err();
        }
        set(pos,((*this)[pos] ? 0 : 1));
        return *this;
    }
    
    bool test(size_t pos) const {
        if ( SIZE <= pos ) {
            err();
        }
        return (m_bit & (1 << pos)) ? true : false;
    }
    
    bool operator[](size_t pos) const {
        return test(pos);
    }
    
    bool operator==(const mybitset<SIZE>& bs) const {
        return m_bit == bs.m_bit;
    }
    
    bool operator!=(const mybitset<SIZE>& bs) const {
        return m_bit != bs.m_bit;
    }
    
    mybitset<SIZE>& operator<<=(size_t shift) {
        m_bit <<= shift;
        m_bit &= (1 << SIZE) - 1;
        return *this;
    }
    
    mybitset<SIZE>& operator>>=(size_t shift) {
        m_bit >>= shift;
        m_bit &= (1 << SIZE) - 1;
        return *this;
    }
    
    mybitset<SIZE> operator<<(size_t shift) const {
        mybitset<SIZE> bs(m_bit);
        return bs <<= shift;
    }
    
    mybitset<SIZE> operator>>(size_t shift) const {
        mybitset<SIZE> bs(m_bit);
        return bs >>= shift;
    }
    
    mybitset<SIZE> operator~() const {
        mybitset<SIZE> bs(m_bit);
        return bs.flip();
    }
    
    size_t count () const {
        size_t cnt = 0;
        for(int i=0;i<SIZE;++i ) {
            if ( m_bit & (1 << i) ) {
                ++cnt;
            }
        }
        return cnt;
    }
    
    string to_string() const {
        string str;
        str.reserve(SIZE+1);
        for(int i=1;i<=SIZE;++i ) {
            str.append( (m_bit & (1 << (SIZE-i))) ? "1" : "0" );
        }
        return str;
    }
    
    unsigned long to_ulong () const {
        return m_bit;
    }
    
    bool any () const { return m_bit != 0; }
    bool none () const { return m_bit == 0; }
    unsigned long size () const { return SIZE; }
    
private:
    unsigned long m_bit;
    void err () const {
        // 取り合えず例外吐いておく
        throw("error");
    }
};

int main () {
    mybitset<8> bs;
    
    cout << bs.size() << endl;
    
    bs.set( 1 );
    bs.set( 2 );
    
    // どれか一つでもビットが立っていたら
    if ( bs.any() ) {
        // 立っているビットを確認する
        if ( bs[0] ) { cout << "bs[0] = ON" << endl; }
        if ( bs[1] ) { cout << "bs[1] = ON" << endl; }
        if ( bs[2] ) { cout << "bs[2] = ON" << endl; }
        if ( bs[3] ) { cout << "bs[3] = ON" << endl; }
        // test関数と[]演算子のオーバーロードは同じ
        if ( bs.test(0) ) { cout << "bs[0] = ON" << endl; }
        if ( bs.test(1) ) { cout << "bs[1] = ON" << endl; }
        if ( bs.test(2) ) { cout << "bs[2] = ON" << endl; }
        if ( bs.test(3) ) { cout << "bs[3] = ON" << endl; }
    }
    
    // ビットを文字列に変換する
    cout << "to_string = " << bs.to_string() << endl;
    
    // ビットが立っている数を数える
    cout << "count = " << bs.count() << endl;
    
    // ビットを反転する
    bs.flip();
    cout << "to_string = " << bs.to_string() << endl;
    
    // ビットを数値に変換する
    cout << "to_ulong = " << bs.to_ulong() << endl;
    
    // 1番目だけビットを反転する
    bs.flip(1);
    cout << "to_string = " << bs.to_string() << endl;
    
    // 4番目のビットだけを落とす
    bs.reset( 4 );
    cout << "to_string = " << bs.to_string() << endl;
    
    // 2ビット左へずらす
    bs = bs << 2;
    cout << "to_string = " << bs.to_string() << endl;
    
    // 2ビット右へずらす
    bs >>= 2;
    cout << "to_string = " << bs.to_string() << endl;
    
    // 引数なしsetは全ビットを立てる
    bs.set();
    cout << "to_string = " << bs.to_string() << endl;
    
    // 引数なしresetは全ビットを落とす
    bs.reset();
    cout << "to_string = " << bs.to_string() << endl;
    
    // ビットが一つも立っていなかったら
    if ( bs.none() ) {
        cout << "all bit OFF" << endl;
    }
    
    return 0;
}

$ main
8
bs[1] = ON
bs[2] = ON
bs[1] = ON
bs[2] = ON
to_string = 00000110
count = 2
to_string = 11111001
to_ulong = 249
to_string = 11111011
to_string = 11101011
to_string = 10101100
to_string = 00101011
to_string = 11111111
to_string = 00000000
all bit OFF

できました。

いくつかの演算子に関しては実装していません。

基本的なものに関しては大体実装できたと思います。

エラーの処理やテスト等はまだまだ適当なのでバグもあるかとは思いますが、とりあえずは満足ということで。

setクラス

http://www.geocities.jp/ky_webid/cpp/library/009.html

setクラスとは、自動的に要素のソートを行ってくれるコンテナです。

さっそく実装してみます。

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

int main () {
    
    set<int> data;
    
    data.insert(5);
    data.insert(3);
    data.insert(4);
    data.insert(2);
    data.insert(1);
    
    set<int>::iterator it = data.begin();
    
    while( it != data.end() ) {
        cout << *it << endl;
        ++it;
    }
    
    return 0;
}

$ main
1
2
3
4
5

ソートされていますね。

今までのコンテナと違って要素の追加にはinsert関数を使います。この辺の違いがややこしいので覚えておきましょう。

デフォルトでは昇順にソートされます。

降順にしたければ宣言時に

set<int, greater<int>> data;

とすれば可能です。

要素の削除はerase関数で可能ですが、これも今までのコンテナと違って使い方が少し変わります。

setクラスのeraseは戻り値を返さないので

data.erase( it++ );

といったようにイテレータが指す場所を削除して一つ進むという感じにしなければなりません。

もちろん一時変数を用意しても問題ありません。

set<int>::iterator del_it = it;
++it;
data.erase(del_it);

次に要素へのアクセスですが、setクラスはツリー構造なので[]演算子による直接アクセスはできないのでイテレータ経由でアクセスします。

また、値の検索はfind関数を使えばできます。

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

int main () {
    
    set<int> data;
    
    data.insert(5);
    data.insert(3);
    data.insert(4);
    data.insert(2);
    data.insert(1);
    
    set<int>::iterator it = data.find( 3 );
    
    if ( it == data.end() ) {
        cout << "見つかりません" << endl;
    }
    else {
        cout << *it << "が見つかりました" << endl;
    }
    
    return 0;
}

$ main
3が見つかりました

find関数の戻り値はイテレータとなります。

もし値が見つからなかった場合はend関数の値が返されるのでそれと比較すれば値が存在していたかどうかを判定できます。

setクラスの利点はこういった値の探索が効率的に行えるところにあるようです。ツリー構造が故でしょうね。

multisetクラス

http://www.geocities.jp/ky_webid/cpp/library/009.html

前回のsetクラスと殆ど同じです。

setクラスは、同じ値を格納できませんでしたが、multisetクラスの場合は同じ値であっても格納できるようになります。

まずはsetクラスで同値の格納を行った場合どうなるか試してみます。

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

int main () {
    
    set<int> data;
    
    data.insert(5);
    data.insert(3);
    data.insert(4);
    data.insert(1);
    data.insert(2);
    data.insert(2); // 同じ値を格納
    
    set<int>::iterator it = data.begin();
    
    while( it != data.end() ) {
        cout << *it << endl;
        ++it;
    }
    
    return 0;
}

$ main
1
2
3
4
5

2がひとつ消えていますね。同値は同じ場所に格納されているようなので別の物として扱うことができません。

今度はmultisetクラスで試してみます。

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

int main () {
    
    multiset<int> data;
    
    data.insert(5);
    data.insert(3);
    data.insert(4);
    data.insert(1);
    data.insert(2);
    data.insert(2); // 同じ値を格納
    
    multiset<int>::iterator it = data.begin();
    
    while( it != data.end() ) {
        cout << *it << endl;
        ++it;
    }
    
    return 0;
}

$ main
1
2
2
3
4
5

ちゃんと2が二つ表示されていますね。別物として扱われているようです。

逆順のイテレータ

さて今までvector、list、set等色々なコンテナの勉強をしてきたわけですが、全ての値にアクセスする手段としてイテレータを使ってきました。

このイテレータなんですが、実は逆順でループさせることも可能なのです。

さっそくやってみます。例としてvectorクラスで試します。

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

int main () {
    vector<int> data;
    
    data.push_back(100);
    data.push_back(200);
    data.push_back(300);
    
    vector<int>::reverse_iterator it = data.rbegin();
    
    while( it != data.rend() ) {
        cout << *it << endl;
        it++;
    }
}

$ main
300
200
100

逆順で表示されてますね。

普通のイテレータを3つ違いがあります。

まず開始位置を取得する関数がbegin関数からrbegin関数に変わっています。同様にend関数もrend関数に変わります。

そしてイテレータの型がiteratorからreverse_iteratorに変わっています。

これだけですね。

後は普通のiteratorと同じようにループでrendと判定しながらitをインクリメントしていくだけでOKです。

mapクラス

http://www.geocities.jp/ky_webid/cpp/library/010.html

mapクラスとはキーと値の組み合わせでデータを管理するためのクラスで、ちょうどハッシュテーブルの仕組みに似ているかもしれないものです。

ただし内部のデータ構造としてはツリー構造らしいので、挙動が似てるだけで実装はハッシュテーブルとは違うようです。

とりあえず実装してみます。

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main () {
    // キーと値の型を指定
    map<string, int> data;
    
    data.insert( map<string, int>::value_type("ddd",40) );
    data.insert( map<string, int>::value_type("aaa",10) );
    data.insert( map<string, int>::value_type("ccc",30) );
    data.insert( map<string, int>::value_type("bbb",20) );
    data.insert( map<string, int>::value_type("eee",50) );
    
    map<string, int>::iterator it = data.begin();
    
    while( it != data.end() ) {
        cout << "key=" << it->first << " value=" << it->second << endl;
        ++it;
    }
    
    return 0;
}

$ main
key=aaa value=10
key=bbb value=20
key=ccc value=30
key=ddd value=40
key=eee value=50

できました。

宣言時にキーの型と、値の型を指定します。

要素の追加にはinsert関数を使います。

イテレータの表示では今までと違うので注意が必要です。

firstとsecondというメンバ変数へアクセスしていますが、これはキーと値が別々に格納されているのでこうなっています。

さて出力結果を見るとソートされていますね。setクラスと同様に自動的にソートされるようになっています。

しかしここまでテンプレート引数が多くなってくるといちいち何度も同じことを書くのが面倒になってきましたね。

こういう場合はtypedefを使えば良いんでしょうか？やってみました。

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main () {
    typedef map<string, int> map_type;
    
    map_type data;
    
    data.insert( map_type::value_type("ddd",40) );
    data.insert( map_type::value_type("aaa",10) );
    data.insert( map_type::value_type("ccc",30) );
    data.insert( map_type::value_type("bbb",20) );
    data.insert( map_type::value_type("eee",50) );
    
    map_type::iterator it = data.begin();
    
    while( it != data.end() ) {
        cout << "key=" << it->first << " value=" << it->second << endl;
        ++it;
    }
    
    return 0;
}

とてもスッキリしましたね。こういう使い方アリなのかちょっと分かりませんが動くということはたぶんアリなんでしょう。

mapクラスでキー名でアクセス

http://www.geocities.jp/ky_webid/cpp/library/010.html

mapクラスの続きです。

mapクラスはツリー構造なので直接アクセスすることは通常出来ないのですが、キー名でアクセスすることはできるのでそれが[]演算子に割り当てられいます。

ということで使ってみます。

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main () {
    typedef map<string, int> map_type;
    
    map_type data;
    
    data.insert( map_type::value_type("ddd",40) );
    data.insert( map_type::value_type("aaa",10) );
    data.insert( map_type::value_type("ccc",30) );
    data.insert( map_type::value_type("bbb",20) );
    data.insert( map_type::value_type("eee",50) );
    
    cout << data["aaa"] << endl;
    
    return 0;
}

$ main
10

ちゃんとキー名でアクセスできてますね。

また、存在しないキー名にアクセスした場合はエラーにならずにそのキー名が登録されます。

つまりinsert関数を使わなくても値の設定ができるということになります。

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main () {
    typedef map<string, int> map_type;
    
    map_type data;
    
    // 存在しないキーに値を設定する
    data["foo"] = 999;
    
    cout << data["foo"] << endl;
    
    return 0;
}

$ main
999

便利ですね。

pairクラス

http://www.geocities.jp/ky_webid/cpp/library/011.html

pairは、２つの値をペアにして１つとして扱うためのクラスです。 前章のmapでは、キーと値をペアで扱う必要がありました。正にこのような用途で使うものです。前章のmapで、insertするとき、value_typeを使っていましたが、value_typeの正体は通常pairです。

な、なるほど。そういうことでしたか。

前回のmapクラスの時に使っていたvalue_typeとはとどのつまりpairクラスだったわけなんですね。

なのでmapのinsertにはvalue_typeじゃなくてpairを直接渡すことも可能です。試してみましょう。

#include <iostream>
#include <map>
#include <string>

// pairを使うのに必要
#include <utility>

using namespace std;

int main () {
    map<string, int> data;
    
    // pairを使う
    data.insert( pair<string, int>("ddd",40) );
    data.insert( pair<string, int>("aaa",10) );
    data.insert( pair<string, int>("ccc",30) );
    data.insert( pair<string, int>("bbb",20) );
    data.insert( pair<string, int>("eee",50) );
    
    map<string, int>::iterator it = data.begin();
    
    while( it != data.end() ) {
        cout << "key=" << it->first << " value=" << it->second << endl;
        ++it;
    }
    
    return 0;
}

$ main
key=aaa value=10
key=bbb value=20
key=ccc value=30
key=ddd value=40
key=eee value=50

ちゃんと動きました。

そして次にpairのテンプレート引数を省略できるmake_pairというものもあります。

こちらも試してみます。

#include <iostream>
#include <map>
#include <string>
#include <utility>
using namespace std;

int main () {
    map<string, int> data;
    
    // make_pairを使う
    data.insert( make_pair("ddd",40) );
    data.insert( make_pair("aaa",10) );
    data.insert( make_pair("ccc",30) );
    data.insert( make_pair("bbb",20) );
    data.insert( make_pair("eee",50) );
    
    map<string, int>::iterator it = data.begin();
    
    while( it != data.end() ) {
        cout << "key=" << it->first << " value=" << it->second << endl;
        ++it;
    }
    
    return 0;
}

ばっちりです。make_pairはその引数から自動で型を検出して動いてくれるのでテンプレート引数を指定しなくても良いというわけなんですね。

イテレータに関するあれこれ

http://www.geocities.jp/ky_webid/cpp/library/012.html

listやsetやmap等で使ってきたイテレータのことを双方向イテレータと言います。++演算子や--演算子で双方向に移動ができるからです。

さらにこれに加えて[]演算子での直接アクセスできるvectorやdeque等で使ってきたイテレータのことをランダムアクセス(直接アクセス)イテレータと言います。

まぁでも名称を意識することはあまりないんじゃないかなぁとは思いますが。

イテレータで複数分先に進める(or戻る)方法

通常イテレータでは++演算子を用いて一つ進めたりすることができます。

vector<int>::iterator it = data.begin();
// ひとつ進める
++it;

では二つ以上進めたい場合どうするか？

// 二つ進める
++it;
++it;

とすればできますよね、当たり前の話です。でもこれが5つ進めたいとしたら？あるいは100進めたいとしたら？++演算子だけではちょっと面倒です。

そこで+=演算子が使えるのではないかと試してみました。

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

int main () {
    vector<int> data;
    
    for(int i=0;i<100;++i) {
        data.push_back(i);
    }
    
    vector<int>::iterator it = data.begin();
    
    // 5つ進める
    it+=5;
    
    cout << *it << endl;
    
    return 0;
}

$ main
5

ビンゴですね。

またiteratorヘッダに用意されているadvance関数を使ってイテレータを進めることもできます。

// 5つ進める
advance(it,5);

たぶんですが、+=演算子のオーバーロードした後の処理はadvance関数に任せてるんじゃないかなぁと想像してます。