汎用コンテナ作成用イディオム(Generic Container Idioms)

意図

値の型に対して最小の要求を持つ汎用コンテナクラス(vector, list, stack等)を作成する。その要求はコピーコンストラクタと throw しないデストラクタを持つことのみとなる。

動機

汎用的なコンテナを開発することは、(STLのような)本当に汎用的なコンテナが欲しい場合、複雑になりうる。型 T に対する要求を緩和することは、本当に汎用的なコンテナを作成する上で鍵となる。型 T に対する要求を可能な限り最小とするために、いくつかの C++ 的イディオムが存在する。

Stack を例としよう。

template<class T>
class Stack
{
    int size_;
    T * array_;
    int top_;
  public:
    Stack (int size=10)
      : size_(size),
        array_ (new T [size]), // T はデフォルトコンストラクタを持たねばならない。
        top_(0)
    { }
    void push (const T & value)
    {
      array_[top_++] = value; // T は代入演算子を持たねばならなない。
    }
    T pop ()
    {
      return array_[--top_]; // T はコピーコンストラクタを持たねばならない。デストラクタはここでは呼ばれない。
    }
    ~Stack () throw() { delete [] array_; } // T は throw しないデストラクタを持たねばならない。
};

配列境界に関する問題以外、上記実装は単純明快である。しかし、非常に認識の甘い実装である。型 T に対して必要以上の要求を課している。上記実装は、型 T に対して以下の操作が定義されていることを要求する。

T に対するデフォルトコンストラクタ
T に対するコピーコンストラクタ
T に対する throw しないデストラクタ
T に対する代入演算子

スタックは、理想的には、push された数以上のオブジェクトを生成するべきではない。同様に、pop される度に、stack から 1 オブジェクトが pop され、破棄されるべきである。上記実装は、いずれも満たしていない。理由の一つとして、型 T のデフォルトコンストラクタを使っていることがある。これは完全に不要である。

実際には、型 T に対する要求は、汎用コンテナ作成用イディオムである construct と destory を用いることで、以下のように削減できる。

コピーコンストラクタ
throw しないデストラクタ

解法とサンプルコード

この目的を達成するため、汎用コンテナは、未初期化のメモリを割り当てることが可能であり、かつ、各要素の「初期化」時に一度だけコンストラクタを呼び出すことが可能であるべきである。これは、以下の 3 つの汎用コンテナ作成用イディオム(Generic Container Idioms)を使うことで可能となる。

#include <algorithm>
// 配置形式 new(placement new)を使った生成用ヘルパ
template <class T1, class T2>
void construct (T1 &p, const T2 &value)
{
  new (&p) T1(value); // T はコピーコンストラクタを持たねばならない
}

// 明示的にデストラクタを呼び出す破棄用ヘルパ
template <class T>
void destroy (T const &t)  throw ()
{
  t.~T(); // T は throw しないデストラクタを持たねばならない。
}

template<class T>
class Stack
{
    int size_;
    T * array_;
    int top_;
  public:
    Stack (int size=10)
      : size_(size),
        array_ (static_cast <T *>(::operator new (sizeof (T) * size))), // T はデフォルトコンストラクタを持つ必要はない。
        top_(0)
    { }
    void push (const T & value)
    {
      construct (array_[top_++], value); // T は代入演算子を持つ必要はない。
    }
    T top ()
    {
       return array_[top_ - 1]; // T はコピーコンストラクタを持つべきである。
    }
    void pop()
    {
      destroy (array_[--top_]);     // T は破棄される。
    }
    ~Stack () throw()
    {
      std::for_each(array_, array_ + top_, destroy<T>);
      ::operator delete(array_); // グローバルスコープの delete 演算子
    }
};
class X
{
  public:
    X (int) {} // X にデフォルトコンストラクタは無い。
  private:
    X & operator = (const X &); // 代入演算子は private。
};
int main (void)
{
  Stack <X> s; // X は Stack に使える！

  return 0;
}

new 演算子は未初期化のメモリを割り当てる。 malloc を呼び出す (訳註：標準では operator new が malloc を呼び出すとも呼び出さないとも規定されていない) ヘルパテンプレート関数 construct は配置形式の new を呼び出し、結果、初期化されたメモリ上でコピーコンストラクタが呼び出される(訳註：正確にはコピーコンストラクタによって初期化される)。ポインタ p は operator new を使用することによって割り当てられた未初期化のメモリ領域の 1 つを指す。 end を初期化済み要素の末端を一つ超えた要素を指す反復子として、 end から割り当て末端までの範囲を指すポインタは、型 T のオブジェクトを指さず、未初期化のメモリを指すはずである。要素がコンテナから削除される場合、その要素に対するデストラクタが呼び出されるべきである。上記のように、ヘルパ関数 destroy がこの助けとなりうる。同様に、ある範囲を delete する場合、2 つの反復子を引数に取る別のオーバーロード関数 destroy が有用になるだろう。この destory は、基本的に 1 つ目の destory ヘルパを範囲中の各要素に対して呼び出す。

既知の利用

全ての STL コンテナは似たような技法を採用している。これらは、テンプレートパラメータの型に対して、可能な限り最小の要求しかしない。一方、よく知られた C++ ライブラリであっても、パラメタ化された型に対して、必要以上に強い要求を課すライブラリもある。

References

Designing Exception Safe Generic Containers -- Herb Sutter

More C++ Idioms/汎用コンテナ作成用イディオム(Generic Container Idioms)

汎用コンテナ作成用イディオム(Generic Container Idioms)

意図

動機

解法とサンプルコード

既知の利用

関連するイディオム

References