株式会社エス・スリー・フォー

STLコンテナに起因するコード膨張の抑止

templateの光と影

templateはgeneric programingという新たなプログラミング・スタイルを私たちに提供してくれます。
従来の手続き型そしてオブジェクト指向型プログラミングでは到底実現できなかったスタイルです。

すなわち ‘仮の型’をクラス/関数に導入し、その’仮の型’を自由に交換することでコンパイル時に様々なバリエーションのオブジェクトを生成するメカニズムです。

templateの代表的な応用例が標準C++ライブラリに組み入れられたSTL(StandardTemplate Library)です。
特に’コンテナ’と呼ばれる一連の’集合’は、その集合の’要素’の型をプログラマに委ねます。

可変長配列 std::vector を例に取ると、
int を要素とする可変長配列は std::vector<int>
std::string を要素とするなら
std::vector<std::string>
のように、異なる型を要素とする可変長配列をたった一つのクラス-テンプレート
std::vector<T> で実装することを可能にしています。

ただし、templateは十分に注意して用いなければなりません。
特に組み込み用途など、潤沢なメモリが用意できない環境でtemplateを濫用すると、コードの膨張を引き起こします。

#include <vector>

int main() {
  std::vector<int>  iv;
  std::vector<long> lv;
  std::vector<char> cv;
  return 0;
}

このコードではint, long, char の3つの型を要素とするvectorを宣言しています。
コンパイラはそれぞれに対して3種のvectorを生成します。 すなわち、vectorの要素が n
種あるなら、vector のコードも n 倍に膨れることになります。

参照ベースコンテナ (1)

同様の例を参照ベースコンテナで見てみましょう:

#include <vector>

class Animal { ... };
class Cat : public Animal {};
class Dog : public Animal {};

int main() {
  std::vector<Animal*>  av;
  std::vector<Cat*> cv;
  std::vector<Dog*> dv;
  return 0;
}

この例でも前述の int/long/char の場合とまったく同じです。 Animal*,Cat*, Dog* の各要素それぞれについて異なる vector が生成されます。

参照(ポインタ)ベースコンテナの場合、継承関係にあるクラスを要素としているのであれば、若干型チェックが弱くなるものの、コード膨張を抑えることができます。すなわち:

#include <vector>

class Animal { ... };
class Cat : public Animal {};
class Dog : public Animal {};

int main() {
  std::vector<Animal*> av;
  std::vector<Animal*> cv;
  std::vector<Animal*> dv;
  return 0;
}

のように、導出クラス(Cat,Dog)を基底クラス(Animal)に置き換えてしまいます。
こうすると要素へのアクセス時に適切な down-cast を要しますが、生成される vectorは型’Animal*’のものだけとなり、 コード膨張を抑制することになります。

参照ベースコンテナ (2)

それでは継承関係のない複数のクラスについてはどうでしょうか:

#include <vector>

int main() {
  std::vector<int*> iv;
  std::vector<long*> lv;
  std::vector<char*> cv;
  return 0;
}

このケースでは、基底クラス(型)が存在しないので、 この3つをたとえばstd::vector<char*> に置き換えるわけにはいきません。

メモリ制約により、どうしてもこのような複数の参照ベースコンテナによるコード膨張を抑えたいなら、void*でまとめることになるでしょう:

#include <vector>

int main() {
  std::vector<void*> iv;
  std::vector<void*> lv;
  std::vector<void*> cv;
  return 0;
}

しかしこれではあまりに危険です。void* が要素であるということは、どんなポインタであっても代入可能ということであり、コンパイラの型チェックをすり抜けてしまいます。

代替案として、やはり若干の使い心地が悪くなるものの、強い型チェック機構を殺さない方法があります。
class-templateでstd::vector<void*>を包み込むのです:

#include <vector>

template<typename T>
class ptr_vector {
public:
  T& operator[](unsigned i) {
    return (T&)v[i];
  }
  // etc...

  std::vector<void*> v;
};

nt main() {
  ptr_vector<int*>  iv;
  ptr_vector<long*> lv;
  ptr_vector<char*> cv;
  return 0;
}

これによって iv[n] は (void*&ではなく) int*&を返してくれます。

operator[]と同様、型を必要とするメソッドはptr_vectorで再定義、size()など型を必要としないメソッドはcv.v.size() のようなインタフェースとなるでしょう。

継承関係のある/ない場合を統一的に扱う、少しだけ修正してみます:

#include <vector>

template<typename T, typename Impl =void* >
class ptr_vector {
public:
  T& operator[](unsigned i) {
    return (T&)v[i];
  }
  // etc...

  std::vector<Impl> v;
};

class Animal { ... }
class Cat : public Animal { ... };
class Dog : publid Animal { ... };

nt main() {
  ptr_vector<int*>  iv;
  ptr_vector<long*> lv;

  ptr_vector<Animal*,Animal*> av;
  ptr_vector<Cat*,   Animal*> cv;
  ptr_vector<Dog*,   Animal*> dv;
  return 0;
}

比較オブジェクトをまとめる

たとえ集合の要素が一種類でも、他のtemplate引数の型が異なるためにいくつもの集合が生成される場合があります。

#include <set>
#include <string>

struct person {
  std::string name;  // 名前
  std::string phone; // 電話番号
};

// 名前で比較
struct less_name {
  bool operator()(const person& x, const person& y) const {
    return x.name < y.name;
  }
};

// 電話番号で比較
struct less_phone {
  bool operator()(const person& x, const person& y) const {
    return x.phone < y.phone;
  }
};

int main() {
  std::set<person, less_name>  nset; // 名前順
  std::set<person, less_phone> pset; // 電話番号順
  return 0;
}

この例では、personの集合(set)として、名前をキーにしたset と電話番号をキーとしたset を宣言しています。
このように、キーすなわちsetの要素の大小関係を与える比較オブジェクトが異なるために、2種類の setが生成されます。

このような場合のコード膨張抑止法として、関数ポインタを使うという方法があります。
すなわち、比較オブジェクトを'比較関数へのポインタ'とし、setのコンストラクタで比較関数を与えるのです。


#include <set>
#include <string>

// 比較オブジェクト
template<typename T>
struct comp_fun_t {
  bool (*fun_)(const T&,const T&);
  comp_fun_t( bool (*fun)(const T&, const T&) ) : fun_(fun) {}
  bool operator()(const T& x, const T& y) const {
    reuturn fun_(x, y);
  }
};

// 比較関数ポインタ から 比較オブジェクトに変換する
template<typename T>
inline 
comp_fun_t<T>
comp_fun(bool (*fun)(const T&,const T&)) {
  return comp_fun_t<T>(fun);
}

struct person {
  std::string name;  // 名前
  std::string phone; // 電話番号
};

// 名前で比較
bool less_name(const person& x, const person& y) {
  return x.name < y.name;
}

// 電話番号で比較
bool less_phone(const person& x, const person& y) {
  return x.phone < y.phone;
}

int main() {
  std::set<person, comp_fun_t<person> > nset(comp_fun(less_name));  // 名前順
  std::set<person, comp_fun_t<person> > pset(comp_fun(less_phone)); // 電話番号順
  return 0;
}