C++マニアック

STL の使い方,how to use STL,標準テンプレートライブラリ,standard template library,コンテナ,container,イテレータ,iterator,アルゴリズム,algorithm

ページの末尾へ   トップページ > STL

TOPIC  1  2  3  4  5  6  7【地球は若い】  8  9  10  11  12  13  14 
節電しましょう。電力の使用状況グラフ(東電)

STL の使い方

  1. STL とは
  2. STL 関連本
  3. 不要な警告の処理について
  4. コンテナとは
    1. vector(一次元配列)
      1. vector の使い方
      2. vector に入れる要素の作り方(その 1)
      3. vector に入れる要素の作り方(その 2)
      4. vector の落とし穴
    2. map(マップ=連想配列)
    3. deque(デック=双方向キュー=FIFO/LIFO、実力派?)
    4. set(セット≒集合)
    5. list(リスト=リンクポインタでリンクされたリスト)
    6. stack(スタック=LIFO)
    7. queue(キュー=FIFO)
    8. multiset(マルチセット=複数の同じ要素を受け入れる集合)
    9. multimap(マルチマップ=複数の同じ要素を受け入れる連想配列)
  5. イテレータとは
    1. ランダムアクセス・イテレータ
    2. 双方向・イテレータ
    3. 前方・イテレータ
    4. 入力・イテレータ
    5. 出力・イテレータ
    6. イテレータが、ポインタとは異なる振る舞いをする場合とは?
    7. 自作クラスにイテレータを実装してみる
  6. アルゴリズムとは
    1. for_each
    2. transform、toupper、tolower、文字列変換
    3. sort
  7. functional とは
    1. mem_fun、mem_fun_ref
  8. その他
    1. string の使い方
    2. pair の使い方

STL とは ページの先頭へ

STL とは Standard Template Library の略で、日本語では標準テンプレートライブラリと呼びます。STL は、クラスとテンプレートを利用したまさに 20 世紀の大発明というべき、高機能で汎用的なテンプレートクラスライブラリです。これほどのライブラリが処理系に標準添付というのはまさに驚愕で、C++マニアック的には、これを使わない手はありません。

STL は次のほぼ三つの部分で構成されています。

  1. データ構造を表すコンテナ
  2. その中をスキャンするためのイテレータ
  3. コンテナに適用可能な各種アルゴリズム

これらを組み合わせて使用することで、いろいろ面倒なことが簡単にできてしまいます。

不要な警告の処理について ページの先頭へ

VC++6 で STL を使ったコードをコンパイルすると、warning C4786: という文字列を含む非常に長い警告が出て、面食らうということがよく起こります。この警告は、STL で使う(自動生成される)変数名が長すぎて、コンパイラのシステムによって長さが切り詰められたということの警告で、実害はありません。これを避けるには、次の行を *.cpp の冒頭に入れましょう。

#pragma warning(disable:4786)

もし、プリコンパイルドヘッダ StdAfx.h を使用しているのであれば、このファイルの冒頭(と言ってもワンタイムインクルードの内側が良いでしょう)に上記の行を入れるのが最も効果があります。

この警告でびっくりして、STL って使えない、などと思うのは大いなる損失です。さらりと通り抜けてください。

もうひとこと言っておけば、一般的に STL 関連のコンパイルエラーのメッセージは、テンプレートクラスの名前を含む非常に長い変数名、関数名を含むものになります。これらは、読み解くのが大変で、初心者はくじけそうになるかもしれません。しかし、これらも落ち着いてよく読むと、何を言っているのか分かるようになってきます。これは、C++ プログラミングにおける一つの大きな壁かもしれません。

上記のような事態が発生したときの対処方法は、次のようなものが経験上有効です。

  1. エラーが起きる一つ前のコードに戻って、比較する。当然、コードのスナップショットを、こまめに取っておく必要があります。
  2. より単純なコードで試してみる。別の簡単なテストプログラムを作成してみるということです。
  3. エラーメッセージを気合を入れて読み解く。大変ですが、これは、かなり、勉強になります。

一般の学問と同様、STL についても王道なしですが、STL を使うことのメリットに比べれば、これらは些細なことです。警告やエラーでくじけないでください。

コンテナとは ページの先頭へ

コンテナ(Container)とは、一般的には入れ物という意味ですが、STL で言うコンテナはもちろん C++ のオブジェクト(変数)の入れ物という意味になります。その種類には、次のようなものがあります。独断と偏見で、よく使う順に並べてあります。

  1. vector(一次元配列)
  2. map(連想配列)
  3. deque(双方向キュー)
  4. set(集合)
  5. list(リンクポインタでリンクされたリスト)
  6. multiset(複数の同じ要素を受け入れる集合)
  7. multimap(複数の同じ要素を受け入れる連想配列)

この中で vector は、使い方が比較的単純で、それゆえに良く使うものなので、まず vector を取り上げて、その使い方を詳細に解説します。後のクラスについては、その後に解説することにします。

vector コンテナへ ページの先頭へ

vector の使い方 ページの先頭へ

まず、一番良く使うと思われる vector について、どんなものなのか、見てみましょう。vector は、簡単に言えば伸縮自在な一次元配列です。vector を使わない場合、例えば C++ では、次のような一次元配列を使うことが出来ます。

    float afTable[2];   // float 型の長さ 2 の配列

しかし、この afTable は、長さが 2 に固定されていて、2 個までの数値を入れることは出来ますが、3 個目を入れようとしたとたんに破綻します。そこで、伸縮自在な一次元配列があったらな、ということになるのですが、これを実現するのが vector です。では、早速 vector 型のオブジェクトを定義して、データを 2 個追加してみましょう。STL はテンプレートクラスライブラリなので、配列要素の変数型を <> で囲んで vector の後ろにつけ vector<float> のように型を指定します。

    vector<float> vecfTable;  // float 型を要素とする長さ 0 の の配列ができるvecfTable.push_back(1.0);   // 1.0 を末尾に追加する。配列の長さは 1 になる。
    vecfTable.push_back(2.0);   // 2.0 を末尾に追加する。配列の長さは 2 になる。

上記のように push_back() を使って値を末尾に追加でき、追加後は、次のように [] 演算子を使って、中身を読むことができます。

    float fValue0 = vecfTable[0];
    float fValue1 = vecfTable[1];
    printf("fValue0 = %f, fValue1 = %f\n", fValue0, fValue1);   // 答えは、1.0 と 2.0 になります。

vector のサンプル vector1.cpp

配列の長さを少し長く一気に 100 にしたい場合には、次のようにします。

    vecfTable.resize(100); // 配列の長さが 100 になる。

長さが伸びたので、先頭から 50 番目の要素に値を書き込むこともできます。

    vecfTable[49] = 3.2;    // 先頭から 50 番目の添え字は 49 である。

等々、他に vector で使える関数などは例えば MSDN などで調べることができます。また、VC++ では、ソースコード上で vector という文字列上にカーソルを置いて、F1 キーを押せば調べることができます。

vector に入れる要素の作り方(その 1) ページの先頭へ

vector の使い方は、上記のように簡単ですが、自作のクラスオブジェクトを vector に入れる場合には、その定義の仕方が少し問題になります。上記例では、vector に入れた要素は foat 型でした。float は C++ に初めから組み込まれている変数型で、問題なく vector に入れることができます。これに対し、自作のクラスオブジェクトを入れようとするときには、必ず、デフォルトコンストラクタコピーコンストラクタデストラクタの三つを使えるようにしておく必要があります。これらをこの項の中では、三点セットと呼ぶことにします

クラスを、明示的なコンストラクタ、デストラクタ、なしで作成すると、この条件は自動的に満たされます。例えば次の単なる構造体のようなクラスは、vector に問題なく入れることができます。

class CManiac {
public:
    int m_iValue;
};

上記の CManiac クラスでは、デフォルトコンストラクタは何もしないコンストラクタが、コピーコンストラクタは要素同士のコピーとして、デストラクタは何もしないデストラクタが、コンパイラによって自動的に付加されたように動作します。つまり次のように定義したのと同じことになります。

class CManiac {
public:
    int m_iValue;
public:
    ~CManiac() {}   // 何もしないデストラクタ
    CManiac() {}    // 何もしないデフォルトコンストラクタ
    CManiac(const CManiac& rmaniac) {   // 要素同士のコピーを行うコピーコンストラクタ
        m_iValue = rmaniac.m_iValue;
    }
};

では、どのような場合に、自前の三点セットが必要になるのかというと、それは、クラスがコンストラクタでメモリを確保する場合です。次のダメな例を見てください。この定義では、vector に上手く入りません。

class CManiac {
private:
    char* m_pc;
public:
    virtual ~CManiac() { delete[] m_pc; }    // デストラクタ
    CManiac() : m_pc(new char[1]) {}         // デフォルトコンストラクタ
};

上記の例では、デフォルトコンストラクタで 1 バイトのメモリを new で確保し、デストラクタで開放しています。これで問題ないように見えますが、このままだと、オブジェクトのコピーを行ったときに、m_pc がそのままコピーされるために、同じメモリ領域を二つのオブジェクトが指すことになるので、コピー元とコピー先のオブジェクトのデストラクタが合わせて 2 回呼び出されたときに、2 回目の呼び出しで既に開放されているメモリを更に開放しようとして、エラーになってしまいます。そこで、正しくは、コピーコンストラクタを定義して、次のようにします。

class CManiac {
private:
    char* m_pc;
public:
    virtual ~CManiac() { delete[] m_pc; }    // デストラクタ
    CManiac() : m_pc(new char[1]) {}         // デフォルトコンストラクタ
    CManiac(const CManiac& rmaniac) : m_pc(new char[1]) {   // コピーコンストラクタ
        strncpy(m_pc, rmaniac.m_pc, 1);
    }
};

これで、vector に入れても問題なくなりました。下記のようなコードが正しく動作します。

int main() {
    vector<CManiac> vecmaniac;  // CManiac オブジェクトの vector を定義する。
    vecmaniac.resize(3);       // 長さを 3 に伸ばす。
    return 0;
}                               // ここで、全てが、正しく消滅する(重要!)。

vector のサンプル vector2.cpp

上記で、長さを 3 に伸ばすときに、伸びた部分には CManiac オブジェクトを入れる必要があるので、このとき CManiac のデフォルトコンストラクタが呼ばれて、CManiac オブジェクトが一つ作られます。あとは、そのオブジェクトをコピーコンストラクタでコピーしては vector の末尾に追加していきます。このような動作のためにデフォルトコンストラクタとコピーコンストラクタが必要なわけです。デストラクタは、コンストラクタで確保したメモリの後始末をするために当然必要ですね。このように、クラスでメモリを確保するのなら、三点セットが必要と覚えておきましょう。

vector に入れる要素の作り方(その 2) ページの先頭へ

vector に入れるという意味では、上記でよいのですが、クラスの定義としては、まだ考慮すべき点があります。次のように、オブジェクトをコピーするときには、上記の定義のままでは要素同士のコピーが行われてしまい、同じメモリ領域を二つのオブジェクトが指すという問題が、また、生じます。

int main() {
    CManiac maniac0;
    CManiac maniac1;
    maniac1 = maniac0;
    return 0;
}

そこで、三点セットに加えて、コピー演算子 = を定義する必要があります。CManiac のメンバ関数に次のように追加を行います。実装的には、まず Copy という名前の関数を定義して、これを使ってコピー演算子を定義するのがよいでしょう。全体は、少し長くなりますが、強調文字の部分が追加した部分です。

class CManiac {
private:
    char* m_pc;
public:
    virtual ~CManiac() { delete[] m_pc; }                   // デストラクタ
    CManiac() : m_pc(new char[1]) {}                        // デフォルトコンストラクタ
    CManiac(const CManiac& rmaniac) : m_pc(new char[1]) {   // コピーコンストラクタ
        strncpy(m_pc, rmaniac.m_pc, 1);
    }
    CManiac& Copy(const CManiac& rmaniac) {          // コピー関数
        if (this == &rmaniac) { return *this; }
        delete m_pc;
        m_pc = new char[1];
        strncpy(m_pc, rmaniac.m_pc, 1);
        return *this;
    }
    CManiac& operator =(const CManiac& rmaniac) {    // コピー演算子
        return Copy(rmaniac);
    }
};

vector のサンプル vector3.cpp

ほぼ何もしないクラスを定義するだけでも、この程度の考慮が必要ということになります。STL と協働するクラスオブジェクトを定義するには、このあたりをさらりとこなす必要があります。しかし、ここを読まれた方は、もう迷うことはないですね。

vector の落とし穴 ページの先頭へ

vector を使う上での落とし穴、というか、注意点が二つあります。

一つ目は、簡単ですが、vector の要素をインデクス(添え字)で参照するときに、限界チェックが自動的には行われないということです。これは、普通の配列でも同様なので、vector だから特に問題ということはないのですが、逆に vector だから、自動でチェックされるのではないかという幻想は、見事に打ち砕かれます。C++ は STL を使っても、やはりアセンブリ言語であると認識しましょう。

vector<int> veciTable(10);     // 長さ 10 の配列を用意する。
veciTable[12];                 // インデクス 12 は、配列要素のある範囲を超えている。

vector のサンプル vector4.cpp

上記のコードは、コンパイルは通りますが、実行時にエラーになる可能性があります。実際にやってみると、たまたま、上記は問題なく終了しますが、メモリ上の vector が管理していない領域を読み取っていることは明らかです。逆に言えば、一見正常に動作しているように見えるので、非常にデバグしにくい、どこかおかしいけれど何が原因か分からない、という問題になり安いといえます。vector を初めから限界チェックを自動的に行うようなクラスとして設計することも出来たわけですが、実行速度的な効率を考えて、汎用の vector としては、チェック無しになっていると認識しましょう。もし限界チェックを自動で行いたいのであれば、自前で vector から派生した(実行速度の遅い)クラスを作成することは可能です。

二つ目は、vector のメモリの再配置にかかわる問題です。vector は、可変長配列であるがゆえに、配列を伸ばす操作を行うと、あらかじめ用意してあったメモリ領域をはみ出してしまう場合があります。そのようなときには、十分な長さの新しいメモリ領域をとって、現在の内容をそこにコピーし、元のメモリ領域を開放するという動作を行います。この場合、元のメモリ領域を指していたポインタや参照は、使えなくなります。次のコードを見てください。

vector<int> veciTable(1);       // 長さ 1 の配列を用意する。
veciTable[0] = 123;             // 最初の要素に 123 を入れる。
int& riElement = veciTable[0];  // 最初の要素の参照
printf("%d\n", riElement);      // ここでは 123 である。
veciTalbe.push_back(2);        // この時点で上記参照は無効になる可能性がある。
printf("%d\n", riElement);      // もはや、123 ではない。

vector は、配列の長さを増加させた場合、要素の参照や、要素を指すポインタは、無効になる、と覚えておきましょう。

イテレータとは ページの先頭へ

  1. ランダムアクセス・イテレータ
  2. 双方向・イテレータ
  3. 前方・イテレータ
  4. 入力・イテレータ
  5. 出力・イテレータ

イテレータ(iterator)とは、日本語で言えば、「繰り返すもの」というような意味ですが、STL で言うイテレータとはコンテナの要素をスキャンする(渡り歩く=巡回する)ためのポインタのようなものです。初めは、本当に、ポインタであると思っておいても、あまり、間違いはありません。イテレータの語源は、おそらく、次のようなよくあるパタンの for 文からの類推です。

int aiTable[10];                       // 長さ 10 の配列
{for (int iIter = 0; iIter < 10; ++iIter) {
    int iElement = aiTable[iIter];     // iIter を使って繰り返し、配列要素を扱う。
}}

上記では、iIter を使って繰り返し、配列 aiTalbe の要素を扱っていますね。英語では、上記のような繰り返しを iteration といいます。簡単に言えば、STL でこのような繰り返し行うために用意されたポインタのようなものがイテレータであるということになります。

上記のコードでは、iIter はポインタではありませんが、ポインタを使って for 文を書き換えてみると、次のようになります。

int aiTable[10];                    // 長さ 10 の配列
{for (int* piElement = aiTable; piElement < &aiTable[10]; ++piElement) {
    int iElement = *piElement;       // piElement を使って繰り返し、配列要素を扱う。
}}

では、STL のコンテナである vector を使って、上記と同じことをしてみましょう。ここで、イテレータの登場です。コードは次のようになります。

vector<int> veciTable(10);          // 長さ 10 の配列
{for (vector<int>::iterator itiElement = veciTable.begin(); itiElement != veciTable.end(); ++itiElement) {
    int iElement = *itiElement;      // itiElement を使って繰り返し、配列要素を扱う。
}}

イテレータのサンプル iterator1.cpp

変数 itiElement がイテレータです。上記二つのコードを比較してみてください。ポインタを使った実装での piElement は、イテレータを使った実装では itiElement に変わっています。これは、ポインタ p がイテレータ it に替わったということですね。あと二つ違うところがあります。一つは、新しいコードでは begin() end() を使っていることです。これらは vector のメンバ関数で、配列の最初と最後(の次)を指すイテレータ(ポインタ)を返します。もう一つは、for 文を抜けるための判定部分で != 演算子を使っていることです。イテレータ同士は演算子 < で比較できるとは限らないからです(vector のイテレータでは実は可能ですが)。

STL を使うことによって、コードが複雑になっただけじゃないか、と思われるかもしれませんが、可変長配列が使えるという決定的なメリットがあることを忘れてはいけません。

上記で、イテレータとはポインタのようなものであるということが分かっていただけると思います。

ランダムアクセス・イテレータ イテレータとはへ ページの先頭へ

ランダムアクセス・イテレータを itRandom と書けば、次の演算子が使用可能です。

  1. *itRandom (ポインタから実体を参照する
  2. ++itRandom (前置きインクリメント
  3. itRandom++後置きインクリメント
  4. --itRandom (前置きデクリメント
  5. itRandom--後置きデクリメント
  6. itRandom[iIndex]配列の添字参照)<---これが、ランダムの名前の由来。ランダムな位置の要素にアクセスできる。

イテレータの実体は、実際には、ポインタではなく、クラスオブジェクトですが、上記のような演算子が定義されているため、ポインタと同様な使い方が可能なわけです。ランダムアクセス・イテレータは、通常のポインタで使用可能な演算子がすべて定義されているので、通常のポインタと同様の使い方が可能というわけです。コンテナ vector<T> のイテレータ vector<T>::iterator は、ランダムアクセス・イテレータです。deque も同様です。

ランダムアクセス・イテレータは、双方向/前方/入力/出力イテレータが使えるところなら、どこでも使用可能です。つまり、イテレータとしては、万能です。

双方向・イテレータ イテレータとはへ ページの先頭へ

双方向・イテレータは、ランダムアクセス・イテレータから、ランダムアクセスの [] 演算子の性能を除いたものです。つまり、双方向・イテレータを itBidirectional と書けば、次の演算子が使用可能です。

  1. *itBidirectional (ポインタから実体を参照する
  2. ++itBidirectional (前置きインクリメント)<---これらが、双方向と呼ばれる所以です。
  3. itBidirectional++後置きインクリメント)<---これらが、双方向と呼ばれる所以です。
  4. --itBidirectional (前置きデクリメント)<---これらが、双方向と呼ばれる所以です。
  5. itBidirectional--後置きデクリメント)<---これらが、双方向と呼ばれる所以です。

コンテナ list<T> のイテレータ list<T>::iterator は、双方向・イテレータです。map、multiset、set も同様です。

前方・イテレータ イテレータとはへ ページの先頭へ

前方・イテレータは、後方には戻れません。つまり、前方・イテレータを itForwad と書けば、次の演算子が使用可能です。

  1. *itForwad (ポインタから実体を参照する
  2. ++itForwad (前置きインクリメント)
  3. itForwad++後置きインクリメント)

前方・イテレータは、例えば、単方向リストのイテレータがこれに当たると思われますが、STL には、単方向リストコンテナはありません。

入力・イテレータ イテレータとはへ ページの先頭へ

入力・イテレータは、これを介して、要素を読むことしかできません。入力・イテレータを itInput と書くと、次の演算子が使用可能です。

  1. *itForwad (ポインタから実体を参照する)
  2. ++itForwad (前置きインクリメント)
  3. itForwad++後置きインクリメント)

演算子の種類としては、前方・イテレータと同じですが、次のように、読むことしかできず、書くことはできません。同じ位置からは、何度でも同じ値を読むことはできます。

    T tX = *itForward;  // 読むことは可能。
    tX   = *itForwad;   // 何度でも、同じ値を読み込み可能。
    *itForward = tX;    // これは、書いているので不可。

入力・イテレータの例としては、コンソールから文字列を入力する場合などが考えられます。

出力・イテレータ イテレータとはへ ページの先頭へ

出力・イテレータは、これを介して、要素を書くことしかできません。出力・イテレータを itOutput と書くと、次の演算子が使用可能です。

  1. *itOutput (ポインタから実体を参照する
  2. ++itOutput (前置きインクリメント)
  3. itOutput++後置きインクリメント)

演算子の種類としては、前方・イテレータと同じですが、次のように、書くことしかできず、読むことはできません。また、一つの位置には一回しか書けないので、書く前か後に ++ 演算子を使う必要があります。

    T tX = *itForward;  // これは、読んでいるので不可。
    *itForward++ = tX;  // 書くことは可能。

出力・イテレータの例としては、コンソールに文字列を出力する場合などが考えられます。

イテレータが、ポインタとは異なる振る舞いをする場合とは? イテレータとはへ ページの先頭へ

上記のように、イテレータには、ポインタで使用可能な *、++、--、[] などの演算子が定義されているため、普通はほぼポインタと思って使っても問題ないわけですが、それでは、まったくポインタと同じかというとそうでない場合もあります。例えば、次のような場合です。

#include <vector>
using namespace std;

int main() {
    vector<int> veciBuffer(3);              // 長さ 3 の配列
    int  iBegin    = *veciBuffer.begin();   // ポインタと思って * を適用すると、値が読めるが、
    int* piPointer = veciBuffer.begin();    // ポインタにイテレータを代入しようとすると、
                                            // コンパイラまたは STL の実装によっては、エラーになる。
    return 0;
}

上記をコンパイルすると G++ と VC++2005 では、イテレータをポインタに変換できないというエラーになりました。BorlandC++5.5 と VC++6 では、エラーにならず、コンパイルできてしまいます。詳しく調べていませんが、これは、コンパイラの差というよりも、STL の実装によって違いが出ているのであろうと想像されます。

回避方法は、あまりスマートには行きませんが、次のようにします。

#include <vector>
using namespace std;

int main() {
    vector<int> veciBuffer(3);                 // 長さ 3 の配列
    int* piPointer0 = &veciBuffer.begin()[0];  // 要素の参照を得て、それのアドレスをとる。または、
    int* piPointer1 = &*veciBuffer.begin();    // これでも、上記と書き方は異なるが、同じことになる。
    return 0;
}

上記の方法で、エラーなくコンパイルできるようになります。まっ、生活の知恵ということで。

アルゴリズムとは ページの先頭へ

STL のアルゴリズムとは、各種繰り返し計算などをテンプレート関数のコレクションとして定義してあるものです。これらアルゴリズムは、STL の他の要素、例えばコンテナ、イテレータなどと協働して動作するようになっています。アルゴリズムを使用するにはヘッダ <algorithm> をインクルードします。具体的な内容については、各項目をご覧ください。

  1. for_each
  2. transform、toupper、tolower、文字列変換
  3. sort

... to be continued!

functional とは ページの先頭へ

STL の functional とは、STL のほかの要素、例えばアルゴリズム、コンテナなどと協働して動作する各種関数をテンプレート関数のコレクションとして定義してあるものです。functional を使用するにはヘッダ <functional> をインクルードします。具体的な内容については、各項目をご覧ください。

  1. mem_fun

... to be continued!