c++boost.gif (8819 bytes)

Generic Programming Techniques

これは boost ライブラリで使われている、 ジェネリックプログラミング技術の不完全な概観である。

Table of Contents

Introduction

ジェネリックプログラミングはソフトウェアコンポーネントに汎用化に関するものであり、 これによりコンポーネントを多様な状況で容易に再利用することが出来る。 C++ ではクラステンプレートと関数テンプレートがジェネリックプログラミング技術に対して特に効果的である。 なぜなら、これらは効率を犠牲にすることなく汎用化を可能にするからである。

ジェネリックプログラミングの簡単な例として、C 標準ライブラリの memcpy() 関数をどのように汎用化するか見てみよう。 memcpy() の実装は次のようになっている。

void* memcpy(void* region1, const void* region2, size_t n)
{
  const char* first = (const char*)region2;
  const char* last = ((const char*)region2) + n;
  char* result = (char*)region1;
  while (first != last)
    *result++ = *first++;
  return result;
}
memcpy() 関数は既に、 void* を使うことである程度汎用化されているので、 この関数は異なる種類のデータ配列のコピーに使うことが出来る。 しかし、コピーしたいデータが配列の中になかったらどうだろう。 これは、リンクリストかもしれない。コピーの概念を、 どんな要素のシーケンスにでも汎用化できるだろうか。 memcpy() の中身を見ると、この関数の 最小限の要求 は、ある種のポインタを使うことで、シーケンスを 横断 し、 指された要素に アクセス し、要素を目的地に 書き込み 、 いつ停止するかを知るためにポインタを 比較する 必要がある。 C++ 標準ライブラリはこのような要求を コンセプト の中にグループ化する。 この場合は、 Input Iterator コンセプト(region2) と Output Iterator コンセプト (region1) である。

もし memcpy() を関数テンプレートとして書き直し、テンプレート引数の要求を述べるために、 Input IteratorOutput Iterator を利用するなら、次のようにして、高度に再利用可能な copy() 関数を実装することが出来る。

template <typename InputIterator, typename OutputIterator>
OutputIterator
copy(InputIterator first, InputIterator last, OutputIterator result)
{
  while (first != last)
    *result++ = *first++;
  return result;
}
汎用の copy() 関数を使うことで、どんな種類のシーケンスからでも要素をコピーできるようになるのである。 これには、std::list のような、イテレータを外部に置いているリンクリストも含まれる。

#include <list>
#include <vector>
#include <iostream>

int main()
{
  const int N = 3;
  std::vector<int> region1(N);
  std::list<int> region2;

  region2.push_back(1);
  region2.push_back(0);
  region2.push_back(3);
  
  std::copy(region2.begin(), region2.end(), region1.begin());

  for (int i = 0; i < N; ++i)
    std::cout << region1[i] << " ";
  std::cout << std::endl;
}

Anatomy of a Concept

コンセプト は要求の集合であり、要求は有効な式、関連型、不変量、 そして計算量の保証から出来ている。要求の集合を満たす型は、コンセプトの モデル と言われる。 コンセプトは他のコンセプトの要求を拡張することが可能であり、これは 発展型 と呼ばれる。

C++ 標準ライブラリで使われているコンセプトは SGI STL site で文書化されている。

Traits

特性クラスは、情報から、コンパイル時の構成要素 (型、汎整数定数、アドレス) を連想する方法を提供する。 例えば、クラステンプレートstd::iterator_traits<T> は次のようになっている:

template <class Iterator>
struct iterator_traits {
  typedef ... iterator_category;
  typedef ... value_type;
  typedef ... difference_type;
  typedef ... pointer;
  typedef ... reference;
};
この特性クラスの value_type は、イテレータが "指し示す先の" 型に対して、 汎用的なコードを与える。 iterator_category はイテレータの能力に依存して、 より効率的なアルゴリズムを選択するために利用することが出来る。

特性テンプレートの核となる特徴は、これらが でしゃばりではない ということである: これらは情報から、組み込みの型、サードパーティのライブラリで定義された型を含め、 任意の型のを連想することを可能にする。通常、特性は特性テンプレートを(部分的に)明示することで、 特定の型に特化されている。

std::iterator_traits についての詳細な記述は、 SGI が提供している このページ を見よ。 標準ライブラリでの、大きく異なる別の特性の式は std::numeric_limits<T> である。これは、 数値型の範囲と能力を記述する定数を提供している。

Tag Dispatching

特性クラスと同時に使われることが多い技術に、タグ分岐がある。 これは、型の性質に基づいて分岐するために、関数オーバーロードを使う方法である。 これについてのよい例は、C++ 標準ライブラリの std::advance() 関数である。 これは、イテレータを n 回インクリメントする。 イテレータの種類によって、実装の中では適用される、異なる最適化がある。 もしイテレータが random access (前方、後方に任意の距離、ジャンプすることが可能である) なら、 advance() 関数は単に i += n で実装され、これは非常に効率的、つまり定数時間である。 他のイテレータでは、 ステップ数が 上昇 し、演算は n に対する線形時間になる。 もしイテレータが、 双方向 なら、 n が負であっても良いので、 イテレータをインクリメントするかデクリメントするか選ばなければならない。

タグ分岐と特性クラスの関係は、分岐に使われる性質(この場合では iterator_category) が特性クラスによってアクセスされることが多い、ということである。 主たる advance() 関数は iterator_category を得るために iterator_traits クラスを使う。 それから、オーバーロードされた advance_dispatch() 関数を呼び出すのである。 iterator_category をどんな型に解決するかに基づいて、 コンパイラにより、 input_iterator_tagbidirectional_iterator_tagrandom_access_iterator_tag の中から適した advance_dispatch() が選ばれるのである。 タグ はタグ分岐や、似たような技術で使うための性質を伝える、 という目的だけを持つ単純なクラスである。 イテレータタグのより詳細な記述については、このページ を参照すること。

namespace std {
  struct input_iterator_tag { };
  struct bidirectional_iterator_tag { };
  struct random_access_iterator_tag { };

  namespace detail {
    template <class InputIterator, class Distance>
    void advance_dispatch(InputIterator& i, Distance n, input_iterator_tag) {
      while (n--) ++i;
    }

    template <class BidirectionalIterator, class Distance>
    void advance_dispatch(BidirectionalIterator& i, Distance n, 
       bidirectional_iterator_tag) {
      if (n >= 0)
        while (n--) ++i;
      else
        while (n++) --i;
    }

    template <class RandomAccessIterator, class Distance>
    void advance_dispatch(RandomAccessIterator& i, Distance n, 
       random_access_iterator_tag) {
      i += n;
    }
  }

  template <class InputIterator, class Distance>
  void advance(InputIterator& i, Distance n) {
    typename iterator_traits<InputIterator>::iterator_category category;
    detail::advance_dispatch(i, n, category);
  }
}

Adaptors

アダプタ は別の型や、新しいインタフェース、ビヘイビアの変種を提供する型を構築する、 クラステンプレートである。 標準のアダプタの例は、 std::reverse_iterator にある。これは、インクリメント、デクリメントに対しその動きの逆転させる、イテレータ型に対するアダプタである。 std::stack は単純なスタックインタフェースを提供するコンテナに対するアダプタである。

標準でのアダプタについての、より解りやすいレビューは ここ にある。

Type Generators

type generator はテンプレート引数 [1] に基づいて新しい型を合成することだけが目的のテンプレートである。 生成された型は通常、ネストされた typedef で名前付けされ、いかにもふさわしく type として表現される。 型生成は通常、複雑な型表現をひとつの型に制止するために使われる。例えば、 boost::filter_iterator_generator では、次のようになっている:

template <class Predicate, class Iterator, 
    class Value = complicated default,
    class Reference = complicated default,
    class Pointer = complicated default,
    class Category = complicated default,
    class Distance = complicated default
         >
struct filter_iterator_generator {
    typedef iterator_adaptor<
        Iterator,filter_iterator_policies<Predicate,Iterator>,
        Value,Reference,Pointer,Category,Distance> type;
};

いまこれは複雑だが、適応するフィルタイテレータを作るのは簡単である。 あなたは普通、ただこう書くだけでよい:

boost::filter_iterator_generator<my_predicate,my_base_iterator>::type

Object Generators

object generator は関数テンプレートであり、唯一の目的は、 引数から新しいオブジェクトを構築することである。 汎用コンストラクタの一種として考えることが出来るだろう。 オブジェクト生成器は、生成される実際の型を表現するのが難しかったり、出来なかったりするときに、 単なるコンストラクタよりも役立つだろう。 そして生成器の結果は変数に格納するのではなく、直接関数に渡すことも出来る。 多くの Boost オブジェクト生成器は接頭辞 "make_" がつけられている。 これは、std::make_pair(constT&,constU&) に倣ってのことである。

たとえば、次のようなものを考えてみる:

struct widget {
  void tweak(int);
};
std::vector<widget *> widget_ptrs;
2つの標準のオブジェクト生成器、 std::bind2nd()std::mem_fun() を連鎖することで、全ての装置を簡単につまむことが出来る:
void tweak_all_widgets1(int arg)
{
   for_each(widget_ptrs.begin(), widget_ptrs.end(),
      bind2nd(std::mem_fun(&widget::tweak), arg));
}

オブジェクト生成器を使わなければ、上の例は次のようになる:

void tweak_all_widgets2(int arg)
{
   for_each(struct_ptrs.begin(), struct_ptrs.end(),
      std::binder2nd<std::mem_fun1_t<void, widget, int> >(
          std::mem_fun1_t<void, widget, int>(&widget::tweak), arg));
}

表現がより複雑になるにつれて、型指定の冗長性を減らす必要性はどうしても大きくなるのである。

Policy Classes

ポリシークラスはビヘイビアを伝達するために使われるテンプレート引数である。 標準ライブラリからの例は std::allocator である。これは、メモリ管理のビヘイビアを標準の containers に伝える。

ポリシークラスは Andrei Alexandrescu によって、 この文書 の中で詳しく探求されている。彼は次のように書いている:

ポリシークラスは几帳面なデザイン選択の実装である。 これらは他のクラスから派生しているか、他のクラスに含まれていて、 構文的に同じインタフェースの下で、異なる戦略を提供する。 ポリシーを使うクラスは、それが使うそれぞれのポリシーに対してひとつのテンプレート引数を持って、 テンプレート化されている。 このためユーザは必要なポリシーを選択することが出来るのである。

ポリシークラスの力は、その能力を自由に組み合わせることから来る。 テンプレートクラスの中のいくつかのポリシークラスを複数の引数と組み合わせることで、 コードの量をそれほど増やすことなく、組み合わせたビヘイビアを実現する。

Andrei のポリシークラスについての記述は、その力を、 粒状性と直交性から引き出されるものとして述べている。 Boost はおそらく、Iterator Adaptors ライブラリの中でこの特徴を弱めている。 このライブラリでは、適用されたイテレータのビヘイビア全てをひとつのポリシークラスに伝えている。 しかし、これには前例がある: std::char_traits はその名前にもかかわらず、std::basic_string のビヘイビアを決定するポリシークラスとして働いているのである。

Notes

[1] 型生成器は、 C++ に ``テンプレートの typedef'' が存在しないことに対する代替手段である。

Revised 14 Mar 2001

© Copyright David Abrahams 2001. Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose.


Japanese Translation Copyright (C) 2003 Kohske Takahashi

オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の 複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」 に提供されており、いかなる明示的、暗黙的保証も行わない。また、 いかなる目的に対しても、その利用が適していることを関知しない。