コンテナ（前編）

（このコンテンツはメールマガジンの STL & iostream 入門に手を加えたものです。「 STL と iostream が使えるかのチェック」等はメールマガジンの方のページをご覧ください）

　コンテナ ( #18 )

　STL アルゴリズムに渡すのは、配列かイテレーターでした。このうち、配列について目を向けてみましょう。
　もちろん実際には「配列」である必要はなく、リニアに十分なサイズが確保されたメモリ領域へのポインタであればいいわけで、そのための方法のひとつが「配列」です。もうひとつの方法は new などを使って動的にメモリを確保することです。

■ C++ : new と delete ( #19 )
　C 言語時代は、変数を動的に作成する場合には malloc() と free() が一般的に使われてきました。ですが、これは C++ では使用してはいけません。 malloc() は「変数を置く領域を確保する」だけで、コンストラクタを呼び出してくれないからです。
　代わりに new と delete というキーワードが用意されました。
　

class CForNew
{
public:
    CForNew()
    {
        printf( "CForNew\n" );
    }

    ~CForNew()
    {
        printf( "~CForNew\n" );
    }
};

void Use_CForNew()
{
    CForNew *pcForNew = new CForNew;
    delete pcForNew;
}
// CForNew
// ~CForNew

　
　このように、 new と delete を使用することで、コンストラクタとデストラクタ呼ばれます。クラス型変数を動的に作成するためには、 new と delete を使用しなければなりません。
　
　STL のコンテナクラスは、基本的にこの new と delete を使って各要素を確保します。ただし、「アロケーター」というシステムを使うと、確保する方法を変えることができます。アロケーターはちょっと難しいので、この「 STL & iostream 入門」では触れないことにします。
　
　new と delete を使ったときに、「デストラクタは仮想関数にする」ということの大事さが分かります。
　

class CNonVirtualDestBase
{
public:
    ~CNonVirtualDestBase()
    {
        printf( "CNonVirtualDestBase::~CNonVirtualDestBase()\n" );    
    }
};

class CNonVirtualDestSub
    : public CNonVirtualDestBase
{
public:
    ~CNonVirtualDestSub()
    {
        printf( "CNonVirtualDestSub::~CNonVirtualDestSub()\n" );    
    }
};

　
　と、基底クラスと派生クラスにデストラクタを作ります。そして、派生クラスで new し、基底クラスのポインタを delete します。
　

void Use_CNonVirtualDestSub()
{
    CNonVirtualDestBase *pcNonVirtualDestBase
        = new CNonVirtualDestSub;    // 派生クラスの方を作ります。
    delete pcNonVirtualDestBase;
}
// 結果
CNonVirtualDestBase::~CNonVirtualDestBase()

////////////////////////////

　
　と、このようにすると派生クラスのデストラクタが呼ばれません。呼ばれるようにするためには、基底クラスのデストラクタを仮想関数にする必要があります。
　

////////////////////////////////////////////////////////////////
//    CVirtualDestBase の使用例。
#include <stdio.h>

class CVirtualDestBase
{
public:
    virtual ~CVirtualDestBase()
    {
        printf( "CVirtualDestBase::~CVirtualDestBase()\n" );    
    }
};

class CVirtualDestSub
    : public CVirtualDestBase
{
public:
    virtual ~CVirtualDestSub()
    {
        printf( "CVirtualDestSub::~CVirtualDestSub()\n" );    
    }
};

void Use_CVirtualDestSub()
{
    CVirtualDestBase *pcVirtualDestBase
        = new CVirtualDestSub;    // 派生クラスの方を作ります。
    delete pcVirtualDestBase;
}

// 結果
CVirtualDestSub::~CVirtualDestSub()
CVirtualDestBase::~CVirtualDestBase()

/////////////////////////////

　
　デストラクタはほとんどのクラスに必要なメンバ関数なので、自分で基底クラスを作る場合には、必ずデストラクタを作って、仮想関数にしてください。

　このふたつにはそれぞれデメリットがあります。配列は管理は楽ですが動的にサイズを変更できません。動的メモリ割り当てはその逆です。そこで、 STL では「配列のように簡単に管理でき、動的にサイズを変えられる」ものを用意してくれています。 STL ではそれを「コンテナ」と呼んでいます。
　最も標準的なコンテナ std::vector を使ってみましょう。
　

////////////////////////////////////////////////////////////////
//    std::vector の使用例。
#include <stdio.h>
#include <vector>    // をインクルードしましょう。

void Use_vector()
{
    std::vector< int > cVector;

    cVector.push_back( 100 );
    cVector.push_back( 200 );
    cVector.push_back( 300 );

    for( int i = 0; i < 3; ++i )
        printf( "%d, ", cVector.at( i ) );
}

// 結果
100, 200, 300, 

/////////////////////////////

　 std::vector は配列に近い操作ができ、かつ要素数を自由に変えることができます。では順に見ていきましょう。
　まず std::vector 型の変数を作ります。このときテンプレート引数として指定するのは「要素の型」です。ここでは整数値を格納するので int 型を指定します。
　作ったばかりの std::vector 型変数（ここでは cVector ）は、要素数ゼロの何も入っていない状態です。そこで要素を追加します。 std::vector::push_back() は最後に要素を追加するメンバ関数です。このメンバ関数を３度呼んだことで、「要素数３の配列」が std::vector 型変数の中に作られたことになります。
　各要素へのアクセスには std::vector::at() を使います。これは配列で使う [ ] 演算子と同様の機能を持っています（ちなみに [ ] そのものも使えます）。
　もうひとつ例を見てみましょう。
　

////////////////////////////////////////////////////////////////
//    std::vector の使用例２。
#include <stdio.h>
#include <vector>

void Use_vector_2()
{
    std::vector< int > cVector( 3 );
    cVector.at( 0 ) = 100;
    cVector.at( 1 ) = 200;
    cVector.at( 2 ) = 300;
    printf( "%d, ", cVector.back() );    // 最後の要素。
    printf( "%d, ", cVector.size() );    // サイズ。

    cVector.assign( 2, 100 );
    printf( "%d, ", cVector.back() );
    printf( "%d, ", cVector.size() );
    cVector.clear();
    printf( "%d\n", cVector.size() );
}

// 結果
300, 3, 100, 2, 0

/////////////////////////////

　
　今度は最初に要素数を決めて領域を作成します。コンストラクタに渡した値の数だけ要素が作られます。ここでは 3 を渡しているので３つの要素が作られます。そして、その各要素に値を格納します。
　次にふたつのメンバ関数を使ってみます。 std::vector::back() は「一番最後の要素」を返します。 std::vector::size() は要素数を返します。
　そのあと std::vector::assign() を使ってみます。このメンバ関数は領域を一度削除して、第１引数の数だけ要素を作り、第２引数で埋めます。ここでは要素をふたつ作り 100 で埋めています。
　ふたたび std::vector::back() と std::vector::assign() を使ってみます。最後の要素が std::vector::assign() の第２引数に、要素数が第１引数になっていますね。
　最後に std::vector::clear() を試してみます。このメンバ関数は領域を削除します。なので要素数はゼロになります。
　このように std::vector はサイズを自由に変えることができます。

　コンテナとアルゴリズム ( #19 )

　 STL のコンテナクラスは、アルゴリズムの「配列」の代わりに使うことができるよう、イテレーターを取り出すことができます。今回はコンテナをアルゴリズムに使用してみましょう。
　

////////////////////////////////////////////////////////////////
//    std::vector と std::fill() の使用例。
#include <stdio.h>
#include <vector>
#include <algorithm>

void Use_vector_With_fill()
{
    std::vector< int > cVector( 3 );
    std::fill( cVector.begin(), cVector.end(), 100 );
    printf( "%d\n", cVector.at( 2 ) );    // 試しに３番目を出力。
}

// 結果
100

/////////////////////////////

　 std::fill() を使って特定の値で各要素を埋めてみましょう。
　すべての STL コンテナクラスには begin() と end() というメンバ関数が備わっています。 begin() は「先頭要素を指すイテレーター」を、end() は「最後＋１要素を指すイテレーター」を返します。つまりこのふたつの戻り値をアルゴリズムに渡せばいいのです。このふたつのメンバ関数は、コンテナをアルゴリズムに使うために用意されたものなのです。
　「配列を指すポインタ」に比べると、要素数などを考えなくていいので簡単に使えますね。
　
　もうひとつ、例を見てみましょう。今度は std::find() で検索します。
　

////////////////////////////////////////////////////////////////
//    std::vector と std::find() の使用例。
#include <stdio.h>
#include <vector>
#include <algorithm>

void Use_vector_With_find()
{
    std::vector< int > cVector;
    cVector.push_back( 100 );
    cVector.push_back( 200 );
    cVector.push_back( 300 );

    std::vector< int >::iterator cIter
        = std::find
            ( cVector.begin()
            , cVector.end()
            , 200 );
    if( cIter != cVector.end() )
        printf( "%d\n", *cIter );
}

// 結果
200

/////////////////////////////

　
　 std::find() は第３引数と一致する要素を探して、見つかったらその要素を指すイテレーターを返します。ということは、イテレーターを受け取るための変数を用意する必要があるということです。
　 std::vector のイテレータークラスの型は std::vector::iterator です。この型を使ってイテレーターを格納する変数を作ります。イテレーターなのでもちろん != を使ってのイテレーターどうしの比較や * を使って要素へのアクセスもできます。
　ちなみに、この例のようにコンテナのイテレーターを使う場合にはどうしても「名前」が長くなってしまうので、テンプレート引数を含めたコンテナクラス名を typedef してしまうほうがいい場合があります。
　

    typedef std::vector< int > vector_int;
    vector_int::iterator cIter

　
　のように。
　また、このような「検索」を行う場合には end() と比較して「見つかったかどうか」チェックする必要があります。必然的に end() を呼ぶ回数も多くなるので、イテレーター変数に格納したものを使い回した方が分かりやすいかもしれません。
　
　さて、 std::fill() の例は「意味なくない？」と思う方も多いでしょう。前回使用した std::vector::assign() が同じ機能を持っているからです。でもそれは違うのです。
　操作には std::vector::assign() などのメンバ関数は極力使用せず、アルゴリズムを使用するべきです。 std::fill() と std::find() を同時に使用することで、コードのスタイルを統一でき、可読性を高めます。また、 std::vector を使用しないことになった場合でも「アルゴリズムとイテレーター」の組み合わせさえしっかりできていれば他のベンダーのコンテナクラス（ CArray とか）への移行も簡単にできます。逆に、最初は配列でコードを書き、途中で std::vector へ乗り換えることも簡単にできるでしょう。
　もし std::vector のメンバ関数を使用してしまうと、これを配列や他のコンテナクラスに移行するのが非常に困難になります。この問題を避けるために、アルゴリズムを使用して、後々の改変しやすさを保つことで保守性を向上させているのです。
　 STL において最も重要なのはアルゴリズムであり、汎用性を高めてくれる関数オブジェクトやイテレーターとの連携です。コンテナはこの連携に最適化されたクラスグループです。「便利な脇役」として使いこなすことが、何より大事でしょう。

　vector と deque と list ( #20 )

　STL コンテナには７つのコンテナクラスが用意されています。それぞれ少しずつ性質が違います。まず３つ紹介しましょう。
　 std::vector はこれまで紹介してきましたね。 std::vector は配列に似た機能を提供します。ってゆーか配列そのものです。
　

////////////////////////////////////////////////////////////////
//    std::vector のイテレーター。
#include <stdio.h>
#include <vector>

void Use_vector_intp()
{
    std::vector< int > cVector;
    cVector.push_back( 100 );
    int *pi = cVector.begin();
    printf( "%d\n", *pi );
}

// 結果
100

/////////////////////////////

　
　と std::vector のイテレーターは要素型のポインタそのものなのです。なので std::vector は配列やポインタとまったく同じように使用できます。
　
　std::vector は new などで普通にメモリ領域を確保します。そのため「先頭に要素を挿入」という操作をすると「値をひとつずつずらす」という作業が必要になるため時間が掛かります。
　この「先頭に要素を挿入」が得意なコンテナが std::deque です。
　

////////////////////////////////////////////////////////////////
//    std::deque の使用例。
#include <stdio.h>
#include <deque>    // をインクルードしてください。

void Use_deque()
{
    std::deque< int > cDeque;
    cDeque.push_back( 100 );
    cDeque.push_front( 200 );    // 先頭に挿入。
    printf( "%d, %d\n", cDeque.at( 0 ), cDeque.at( 1 ) );
}

// 結果
200, 100

/////////////////////////////

　 std::deque は最初に余分に領域を確保し、確保した領域の中央に「先頭ポインタ」をセットします。こうすることで「先頭への挿入」は、ただ「先頭ポインタ」をひとつ前にずらすだけでできます。
　この仕組みのため std::deque のイテレーターはクラスになっていて、要素に対する特別な操作が実装されています。が、中身は std::vector に近く、ほぼ配列と同様の操作が行われます。
　
　 std::vector にも std::deque にも苦手なのが「非末端への挿入」です。先頭でも末尾でもない「中央」に値を挿入するためには、必ず各要素の値をずらす必要があります。
　この操作に向いているのが std::list です。
　

////////////////////////////////////////////////////////////////
//    std::list の使用例。
#include <stdio.h>
#include <list>    // をインクルードしてください。

void Use_list()
{
    std::list< int > cList;
    cList.push_back( 100 );
    cList.push_back( 200 );
    cList.insert( ++( cList.begin() ), 300 );    // 中央に挿入。
    for    ( std::list< int >::iterator cIter = cList.begin()
        ; cIter != cList.end()
        ; ++cIter )
            printf( "%d, ", *cIter );
}

// 結果
100, 300, 200, 

/////////////////////////////

　 std::list の各要素は、メモリ上に並んでいません。各要素はそれぞれ別に領域が確保され、「となりの要素」を指すポインタを持つことで仮想的に「並んでいる」のです。
　この各要素が「並んでいる」ように見せかけるため、イテレーターはクラスになっていて ++ 演算子などの操作で「となりの要素」へと移動するよう実装されています。
　 std::list の各要素は並んでいないので、途中への挿入が素早く行えます。ひとつの要素を作成したあと「となりの要素へのポインタ」を継なぎ直せばいいだけだからです。
　その代わり、特定の位置の要素へと素早くアクセスするのには向いていません。「特定の位置」を探すために、各要素をひとつずつ渡り歩く必要があるからです。そのため、 std::list には at() メンバ関数（そして [ ] 演算子）が備わっていません。 std::vector や std::deque のように「３番目の要素を直接取り出す」といった操作はできないのです。
　
　この３つのコンテナクラスだけでも、それぞれ特徴が違います。必要に応じて使い分けるのがいいでしょう。

　インサートイテレーター ( #21 )

　コンテナは基本的には「配列を模したもの」でしかありません。例えば、次の例のように「要素数ゼロ」の std::vector 型変数を使用するとエラーになります。
　

////////////////////////////////////////////////////////////////
//    std::vector と std::copy() の間違った使用例。
#include <stdio.h>
#include <vector>
#include <algorithm>

void Use_copy_fail()
{
    int iAry[] = { 100, 200, 300 }; 
    std::vector< int > cVector;    // 要素数ゼロ。
    std::copy( iAry, iAry + 3, cVector.begin() );
}

// 結果
ランタイムエラー。

/////////////////////////////

　
　コンテナクラスに十分な要素数がないときに書き込むと、確保していないメモリ領域に書き込んでしまい、アクセス違反を起こします。「要素数が足りないから自動的に拡張される」ということはないのです。
　でもできないのは「自動的に」という点だけです。つまり「拡張するようにする」ことができるのです。それには「インサートイテレーター」というイテレータークラスを使用します。
　

////////////////////////////////////////////////////////////////
//    std::back_inserter の使用例。
#include <stdio.h>
#include <vector>
#include <algorithm>

void Use_back_inserter()
{
    int iAry[] = { 100, 200, 300 }; 
    std::vector< int > cVector;    // 要素数ゼロ。
    std::copy
        ( iAry, iAry + 3
        , std::back_inserter( cVector ) ); // ここで使用。
    for( int *pi = cVector.begin(); pi != cVector.end(); ++pi )
        printf( "%d, ", *pi );
}

// 結果
100, 200, 300, 

/////////////////////////////

　
　 std::back_inserter() はイテレータークラス std::back_insert_iterator を生成する関数です。イテレータークラス std::back_insert_iterator は = 演算子で値が代入されるときに、渡されたコンテナクラスの push_back() メンバ関数を呼び出します。このメンバ関数は「最後に要素を追加する」ものなので、要素が確保されつつ代入することができる、ということです。
　
　初めから用意されているインサートイテレーターは３つあります。この std::back_insert_iterator の他に、 push_front() を呼び出して先頭に挿入する std::front_insert_iterator 、 insert() を呼び出してどこにでも挿入する std::insert_iterator です。それぞれ std::back_inserter() , std::front_inserter() , std::inserter() という「簡単にインサートイテレーターを作ってくれる関数」が用意されています。
　

呼ぶメンバ     イテレータークラス           生成用関数
push_back()   std::back_insert_iterator   std::back_inserter()
push_front()  std::front_insert_iterator  std::front_inserter()
insert()      std::insert_iterator        std::inserter()

　
　インサートイテレーターは、指定されたメンバ関数を呼び出すだけのクラステンプレートです。なので push_front() を持たない std::vector には std::front_insert_iterator を使用することができません。
　

    std::copy
        ( iAry, iAry + 3
        , std::front_inserter( cVector ) );    // コンパイルエラー。

　
　でも push_front() を持つ std::deque と std::list には使用できます。
　

////////////////////////////////////////////////////////////////
//    std::front_inserter の使用例。
#include <stdio.h>
#include <list>
#include <algorithm>

void Use_front_inserter()
{
    int iAry[] = { 100, 200, 300 }; 
    std::list< int > cList;
    std::copy
        ( iAry, iAry + 3
        , std::front_inserter( cList ) );
    for    ( std::list< int >::iterator cIter = cList.begin()
        ; cIter != cList.end()
        ; ++cIter )
            printf( "%d, ", *cIter );
}

// 結果
300, 200, 100, 

/////////////////////////////

　
　そのクラスに特定の演算子が備わっているか、特定の名前のメンバ関数が備わっているか、そういったことが STL では重要ということですね。

■ C++ : ないと呼べない ( #21 )
　例えばこんな関数テンプレート。
　

template< class type_With_Do >
void CallDo( const type_With_Do &p_rcWithDo )
{
    p_rcWithDo.Do();    // type_With_Do::Do() を呼ぶ。
}

　
　この関数テンプレートは、受け取った引数の Do() メンバ関数を呼び出します。
　この「 Do() メンバ関数を呼び出す」という点がポイントです。 Do() メンバ関数というのは、関数名が Do で、引数を受け取らないメンバ関数ならすべてあてはまります。ということは、そういうメンバ関数を持つクラスのみが CallDo() の引数として渡すことができるということです。
　当たり前ですが組込型は渡せません。
　渡せるのは次のようなクラスです。
　

class CWithDo
{
public:
    void Do() const
    {
        printf( "CWithDo()\n" );
    }
};

　
　Do() メンバ関数を持っていますね。これを渡すと、 CallDo() 関数テンプレートは次のようにインスタンス化されます。
　

void CallDo( const CWithDo &p_rcWithDo )
{
    p_rcWithDo.Do();    // CWithDo::Do() を呼ぶ。
}

　
　これならつじつまが合いますね。
　つまり、テンプレートがうまく働くかどうか（コンパイルエラーにならないか）の鍵は「型を実際に置き換えたときに矛盾がないか」という点に尽きます。
　この例は #21 で紹介する「インサートイテレーター」に当てはまる話です。また、メンバ関数の呼び出しを演算子に置き換えれば、これまでのアルゴリズムなどでの問題と一致するものです。
　
　C 言語時代は、こういったことをマクロが行っていました。ですがマクロは、名前空間に束縛されない、制限が緩すぎる、などの理由で使いづらいものでした。テンプレートは、そのマクロの代わりとして存在するものと考えるといいかもしれません。基本的には「ただの型の置き換え」なのです。