STLとは何か

まず最初に言い放っておきましょう。

「STLはオブジェクト指向とは何の関係もありません。」

言い換えれば、オブジェクト指向をマスターしているからと言ってSTLを理解し使いこなせるわけではありませんし、逆にSTLを理解するのにオブジェクト指向の知識が必要なわけでもありません。

従来のライブラリは特定のデータ構造とそれに対する操作(処理)の集合体です。これはANSI-Cで制定された標準Cライブラリも同様です。たとえば<string.h>に宣言されている関数memchrのプロトタイプを見てみましょう:

 void* memchr(const void* p, int c, size_t n);

関数memchrは、pから始まるnバイトの配列p[0]..p[n-1]の中にcと等しい要素が見つかればその位置を、見つからなければ0を返します。memchrを使って「バイト配列の中から特定の値を持つ要素を探し出す」ことができます。標準Cライブラリ関数memchrがやってくれることは:

と分解できます。memchrはバイトというデータ、配列というデータ構造に特化したアルゴリズムです。「long配列の中から特定の値を持つ要素を探し出す」のように、まったく同じアルゴリズムであるにもかかわらず、要素の型がバイト以外のデータに対して適用できません。

これに対し、STLの提供するアルゴリズムfindはどうでしょう:

  // char配列 ca[0]..ca[N-1]の中から'a'を探し出す
  char ca[N];
  char* cp = find(ca,ca+N,'a');
  if ( cp != ca+N ) {
    // 見つかった!
  }

findには第1引数に検索対象となる集合の先頭、第2引数に検索対象の末尾(の直後)、そして第3引数に検索する値を与えます。findは集合内の要素を順に比較し、検索値が見つかったらその位置を、見つからなければ第2引数に渡した値を返します。この引数の与え方に従ってさえいれば、findは検索対象の型を選びません:

  // long配列 la[0]..la[N-1]の中から12を探し出す
  long la[N];
  long* lp = find(la,la+N,12L);
  if ( lp != la+N ) {
    // 見つかった!
  }

さらに、検索対象となる集合は配列だけにとどまりません。おなじくSTLが提供する可変長配列vectorや双方向リストlistなど各種のコンテナ(要素の集合)に対しても配列同様にfindを利用することができます:

  vector<int> iv; // intを要素とする可変長配列
  vector<int>::iterator i = find(iv.begin(), iv.end(), 5);
  if ( i != iv.end() ) {
     // 見つかった!
  }

  list<string> sl; // stringを要素とする双方向リスト
  list<string>::iterator s = find(sl.begin(), sl.end(), "apple");
  if ( s != sl.end() ) {
     // 見つかった!
  }

"集合の中から与えられた条件を満たす要素を探し出す"アルゴリズムをフローチャートで表現すると次の図のようになります。

フローチャートにある各々の箱に書かれた処理:

のそれぞれが統一されたインタフェースで実現されているなら、このアルゴリズムをたったひとつ実装すれば

適用できることでしょう。オブジェクト指向プログラミングの目的のひとつが"データの抽象化"であるのに対し、STLは"アルゴリズムの抽象化"を実現しようとするものです。

"進化した手続き型プログラミング"

といえるかもしれません。

i種のデータ型(char,long,string,...)、データを格納するj種のデータ構造(配列,vector,list,...)そしてk種のアルゴリズムがあるとき、これらの任意の組み合わせを実現するために実装しなければならないコードの総数はi*j*k個となります。STLはtemplateを駆使することによってその総数をi+j+k個で済ませてしまうのです。このことが従来のライブラリとの大きな違いです。データ型、データ構造、アルゴリズム相互の直交性を極限まで追求したのがSTLです。

データ型、データ構造、アルゴリズムのあらゆる組み合わせを可能にするため、STLはコンテナ、イテレータ、関数オブジェクト、アルゴリズムなどの様々なコンポーネントから構成されており、プログラマはそれらを組み合わせて目的の処理を実現します。

STLにおいて、イテレータ、関数オブジェクト、アルゴリズムの関係は:

上の関係の中にコンテナ(データ構造)は姿を現しません。コンテナすなわち"データの集合"はアルゴリズムへの入力データ供給元あるいは出力データ格納先として機能するものですが、これとアルゴリズムは直接結び付けられることはありません。コンテナ内のデータの参照方法はコンテナの内部構造によって異なり、それをアルゴリズムに意識させたくないからです。コンテナ(データ構造)とアルゴリズムはイテレータ(コンテナ内の要素にアクセスするためのオブジェクト)を介して結び付けられるのです。生産プラントにたとえると:

ということになるかと思います。


※ コラム 名前空間

名前空間(namespace)は、関数名、変数名、クラス名の衝突を回避するための機構です。これによって、グローバルな名前空間を複数作成し、それらを区別することができます。

  namespace myspace {
    int x;
    void f(int);
    int my_func();
  }

  namespace yourspace {
    int x;
    void f(int);
    int your_func();
  }

このとき、グローバル変数、関数は名前空間で区別されます。名前はスコープ決定演算子::またはusingを使って参照します。

  void g() {
    myspace::f(3); // myspaceにあるvoid f(int)をコール
    myspace::x = myspace::my_func();
  }

  void h(void) {
    using namespace myspace;
    using namespace yourspace::your_func;
    f(3);          // myspace::f(3);
    x = my_func(); // myspace::x = myspace::my_func();
    your_func();   // yourspace::your_func();
  }

STLを含む標準C++ライブラリは名前空間stdの中にあります。したがって標準C++ライブラリを使うにはスコープ解決子std::を関数などの頭に付けるか、using namespace std;してください。

  // 旧いコード: 標準C++ではエラー
  #include <iostream.h>
  int main() {
    cout << "Hello, world" << endl;
    return 0;
  }

  // 標準C++での"Hello, world" その1
  #include <iostream> /* '.h'は付けないことになった */
  int main() {
    // cout,endlはnamespace stdにある
    std::cout << "Hello, world" << std::endl;
    return 0;
  }

  // 標準C++での"Hello, world" その2
  #include <iostream>
  using namespace std::cout;
  using namespace std::endl;
  int main() {
    cout << "Hello, world" << endl;
    return 0;
  }

  // 標準C++での"Hello, world" その3
  #include <iostream>
  using namespace std;
  int main() {
    cout << "Hello, world" << endl;
    return 0;
  }

※ コラム template

STL(Standard Template Library:標準テンプレートライブラリ)はその名が示すとおり、templateを駆使したライブラリです。STLを理解し利用するにはまずtemplateとはどんな機能であるか、基本的なところは押さえておかないわけにはいきません。

templateとは、簡単に言えば「コンパイラがサポートする超高性能マクロ」と思ってください。C/C++のマクロは、

 #define MAX(x,y) (((x)>(y) ? (x):(y))

のように#defineディレクティブで定義されます。この#defineによるマクロの展開はソースコードのコンパイルに先立ってプリプロセッサが行ないます。すなわちプリプロセッサがソースコードを読み込んで'#'から始まるプリプロセッサ命令を解析し、文字列の置換を行なってマクロ展開を完了したソースが(内部的に)作られ、それがコンパイラに流し込まれます。したがってソースコード:

  #define MAX(x,y) ((x)>(y) ? (x):(y))
  int a = 3;
  int b = 3;
  int m = MAX(a,++b);

はプリプロセッサによって

  int a = 3;
  int b = 3;
  int m = ((a)>(++b) ? (a):(++b));

と展開されます。結果的に++bが2度評価され、bとmは5になってしまいます。#defineマクロは単なる文字列の置き換えに過ぎないからです。

通常の(非template)関数でMAXを定義すればこのような事は起こりません。

  int MAX(int x, int y) { return x > y ? x : y; }

  int a = 3;
  int b = 3;
  int m = MAX(a,++b);

しかしこれではint以外の型に対してMAXを呼ぶことができなくなります。

MAXをtemplateを使って書くと:

  template<class T>
  T MAX(T x, T y) {
    return x > y ? x : y;
  }

  int a = 3;
  int b = 3;
  int m = MAX(a,++b);

というコードがコンパイラに送り込まれたとき、MAXの引数がintであることから上記コードの'T'はintであると判断し、以下のようなコードであると見なします:

  // これは疑似コード
  int MAX_int(int x, int y) {
    return x > y ? x : y;
  }

  int a = 3;
  int b = 3;
  int m = MAX_int(a,++b);

これならm,bには正しい値4が代入されますね。

templateは#defineと同じく、定義された時点ではコードが解釈されません。

  template<class T> // <>内にある'class T'を"テンプレート引数"という
  T MAX(T x, T y) {
    return x > y ? x : y;
  }

は、Tの型が確定しない限りコンパイラは解釈のしようがありませんから。

Tの型が確定するのはMAX()が使われたときです。

  int  i = MAX(1,2);     // T:int
  char c = MAX('a','b'); // T:char

この場合、型Tがint,charの2種類のMAX(MAX<int>,MAX<char>)が生成されます。templateの定義はひとつでも、その実体は使われた型Tの数だけ作られます。したがって闇雲にtemplateを使いまくると生成される実行形式のサイズが膨れ上がる危険をはらんでいます。

templateは上の例MAXのような関数(関数テンプレート)だけでなく、classやstructに対しても適用できます(クラステンプレート):

  template<class X, class Y>
  struct some {
    X x;
    Y y;
  };

  some<int,long> s; // some<int,long> { int x; long y; }

通常の(templateを使わない)クラスでは、たとえばスタックを作るときpush/popする要素の型ごとに別個のクラス定義が必要です:

  class Stack_of_int {
    int*  data_;
    int   index_;
    int   capacity_;
  public:
    Stack_of_int(int n) : capacity_(n), index_(0)
      { data_ = new int[capacity_]; }
   ~Stack_of_int()
      { delete[] data_; }
    void push(int x)
      { if ( index_ < capacity_ ) data_[index_++] = x; }
    int top() const
      { return data_[index_-1]; }
    void pop()
      { if ( index_ > 0 ) --index_; }
  };

  class Stack_of_long {
    long* data_;
    int   index_;
    int   capacity_;
  public:
    Stack_of_long(int n) : capacity_(n), index_(0)
      { data_ = new long[capacity_]; }
   ~Stack_of_long()
      { delete[] data_; }
    void push(long x)
      { if ( index_ < capacity_ ) data_[index_++] = x; }
    long top() const
      { return data_[index_-1]; }
    void pop()
      { if ( index_ > 0 ) --index_; }
  };

上記のStack_of_intとStack_of_longは内包する要素の配列が異なるだけで、push/popなどのメソッドはまったく同じものです。

templateを使えばStack_of_int,Stack_of_longだけでなくあらゆる型を要素とするスタックをひとつのクラスで表現できます。

  template<class T>
  class Stack {
    T*    data_;
    int   index_;
    int   capacity_;
  public:
    Stack(int n) : capacity_(n), index_(0)
      { data_ = new T[capacity_]; }
   ~Stack()
      { delete[] data_; }
    void push(T x)
      { if ( index_ < capacity_ ) data_[index_++] = x; }
    T top() const
      { return data_[index_-1]; }
    void pop()
      { if ( index_ > 0 ) --index_; }
  };

  // 3種のStackを使う...
  Stack<int>   istack(5);
  Stack<long>  lstack(8);
  Stack<void*> pstack(10);

なお、2つ目以降のテンプレート引数にはデフォルトを指定することができます(デフォルトテンプレート引数)

  template<class X, class Y =char, class Z =Y>
  struct any {
    X x;
    Y y;
    Z z;
  };

  any<int>          s0; // any<int,char,char>
  any<int,long>     s1; // any<int,long,long>
  any<int,long,int> s2; // any<int,long,int>