5.ACE コンテナ

C++ 標準には STL(Standard Template Library) と呼ばれる強力なコンテナ群とアルゴリズム群が存在する。しかしながら、これが利用できないコンパイラにも ACE は対応しているため、類似のコンテナ群を提供している。
STL のコンテナほどエレガントではないが、代わりに ACE のコンテナは高い性能と小さいメモリフットプリントを持っている。
一般的には STL のコンテナを利用した方が良いと思われるが、次のような場合には ACE のコンテナが有用かもしれない。

5.1 コンテナコンセプト

5.1.1 テンプレートベースコンテナ

テンプレートベースコンテナはコンパイル時に指定した型についてインスタンス化されるため、型安全である。また、型ごとに特殊化できるため、型によっては別な(効率が良いなどの)実装を利用するようにもできる。
一方、オブジェクトベースコンテナの場合には、作成時に指定したクラスと、そのサブクラスのみが格納できる。このため、通常は Java における Object 型のように一般的な型で利用できるように製作されることが多い。そのせいで、本来の意図とは全く無関係なオブジェクトが紛れ込んでしまう場合も有り得る。
また、タイプレスコンテナは更に悪い。これにはどんなオブジェクトでも格納することができる上、型情報が保存されない。

5.1.2 オブジェクトベースコンテナ

上で説明したように、オブジェクトベースコンテナには特定の型(とそのサブクラス)のオブジェクトを格納しておける。
ACE ではこのタイプのコンテナは、限られた特殊な用途に用意している。例としては ACE_Message_Queue が挙げられる。
このタイプのコンテナについては、必要になった時により詳しく説明する予定である。

5.1.3 イテレータ

コンテナ内の要素に関して処理を行いたい場合によく利用され、便利なのがイテレータである。これは C におけるポインタのようにコンテナ内部のある位置を示しており、その位置を前後させたり、位置の内容を取り出したりできる。
可能な動作はコンテナとイテレータの種類により異なる。例えば、ある場合は前にしか進めないイテレータであり、またある場合には双方向に進めるイテレータである。また、const なイテレータはデータの読み出しのみを許可する。
ACE の多くのコンテナでは C++ 標準形式と、ACE の古い版の独自形式の2種類のイテレータをサポートしている。このため、これらでは STL における標準アルゴリズムを利用することができる。

5.2 順序付きコンテナ

順序付きコンテナは、その名の如く要素間に順序を保持するコンテナである。イテレートの場合にはこの順序に沿ってオブジェクトが返される。
ACE の順序付きコンテナには双方向リスト、スタック、キュー、アレイ、セットが存在する。

5.2.1 双方向リンクリスト

双方向リストは文字通り双方向にリンクされ、前後に移動できるようになっているリストである。リンクリスト構造のため、インデックスによるランダムアクセスはできない。
このために使うクラスは ACE_DLList テンプレートクラスであり、テンプレートパラメータには格納したいオブジェクトのクラスを指定する。
実際に格納されるのはクラスオブジェクトのコピーではなく、オブジェクトへのポインタであることに注意が必要だ。この点でこのクラスは C++ 標準とは異なっている。
サンプルコードと説明が p.90-94 に記載されている。また、p.94 にはイテレータについての注意も書いてある。

5.2.2 スタック

スタックは LIFO(Last In First Out：後入れ先出し)形式のデータ構造である。つまり、最後に入れたデータが最初に取り出される。
スタックの利用は以下の3クラスによって行える。
スタックに格納されるのは指定したデータ型のオブジェクトのコピーである。この点で先の双方向リンクリストとは異なる。
要素の格納は push(v)、取出は pop(v) で行える。

5.2.3 キュー

キューは FIFO(First In First Out：先入れ先出し)形式のデータ構造である。最初に入れたデータが最初に取り出される。
ACE のキューは ACE_Ubounded_Queue クラスで利用できる。これは実質的には deque(両端キュー) であり、投入と取出が両端に対して行える。
データの格納は enqueue_head(v) あるいは enqueue_tail(v)、取出は dequeue_head(v) あるいは dequeue_tail(v) で行える。
こちらも格納されるのはスタックと同様に、指定したデータ型のオブジェクトのコピーとなる。

5.2.4 配列(アレイ)

配列はシーケンスコンテナではなく、C++ 言語によって直接サポートされている。ACE はこれに便利なラッパーを被せた。
ACE_Array<TYPE>(size) によって利用することができる。また、ACE_Array::ITERATOR がアレイ用のイテレータ型として用意されている。

5.2.5 セット

セットは重複した要素を持てないシーケンスコンテナである。ACE ではサイズ固定の ACE_Bounded_Set とサイズ無限の ACE_Unbounded_Setの2種類を用意している。
要素の重複チェックは operator== によって行われる。ポインタ型を格納する場合、比較されるのはオブジェクトではなく、オブジェクトへのポインタ値自体であることに注意すること。
データの格納は insert(v)、検索は find(v)、削除は remove(v) で行うことができる。

5.3 連想コンテナ

5.3.1 マップマネージャ

ACE はシンプルなマップ型を ACE_Map_Manager クラステンプレートで提供している。これはキー型と値型をテンプレート引数に取り、挿入時にキーと値のペアを指定して関連付けを行い、キーを指定して取り出しができるようになっている。
ACE_Map_Manager は動的配列によって実装されている。領域が不足すると自動的に再割り当てを行い、削除で余った分はフリーリストに追加される。ここで、コンパイル時に ACE_HAS_LAZY_MAP_MANAGER を指定しておくと、削除した要素のフリーリストへの追加がフリーリストが空の場合にのみ行われるようになる。
途中にイテレータに関する説明を挟みつつ、p.104-108 にサンプルが掲載されている。また、テンプレートの特殊化を利用した比較方法のカスタマイズが p.107-108 に、マルチスレッドのロックに関する話題が p.108 に載っている。

5.3.2 ハッシュマップ

ACE でのハッシュマップの実装は ACE_Hash_Map_Manager である。これに利用する型は、キー・値ともにコピーコンストラクタを持っている必要がある。
テンプレートパラメータの一番目と二番目にはキーと値の型を指定するが、三番目にはハッシュ関数のファンクタを、四番目には等値関数のファンクタを指定する。また、最後の五番目には並列性を指定する。
ACE はハッシュ関数と等値関数についてもテンプレートを用意している。これらは ace/Functor.h に含まれており、ACE_Hash<TYPE> および ACE_Equal_To<TYPE> で利用することができ、一般的な組み込み型については実装されている。
テンプレートクラスのインスタンスを準備できたら、バケットサイズを指定する必要がある。これには open(size) 関数を利用する。バケットサイズはハッシュ関数のばらけ具合と、実際に登録するデータ数などを参考に調整してみること。
ユーザ定義の型をキーに指定したい場合には p.110-111 のサンプルを参考に ACE_Hash と ACE_Equal_To ファンクタを特殊化する必要がある。

5.3.3 自動調整バイナリツリー

自動調整バイナリツリー(または平衡二分木)は、平均および最悪の場合に O(log n) の計算量となるため、ハッシュマップの最悪値 O(n) よりは効率が良い。ただし、挿入・削除にかかる計算量も O(log n) であるため、ハッシュマップの O(1) には敵わない。
ACE の自動調整バイナリツリーは Red Black Tree(赤黒木)と呼ばれる実装を利用している。この実装は ACE_RB_Tree と呼ばれ、マップクラスと同様の利用が可能である。このテンプレートパラメータにはマップと同様にキー・値の型を与え、それに続いて比較関数のファンクタ、並行性を指定する。
利用サンプルは p.112-114 に記載されており、ACE_Less_Than 比較関数ファンクタの特殊化例が p.115 にある。

5.4 アロケータ

ほとんどのコンテナライブラリと同様に、ACE にもコンテナのメモリ割り当て方法を管理できるアロケータが準備されている。また、ACE_Allocator クラスを継承することで独自のアロケータを設計することもできる。
アロケータはコンテナのコンストラクト時か open() 時に指定する。ほとんどの場合は open() を利用した方がエラー時に返り値を確認できて便利だろう。
もし読者が標準 C++ のアロケータに詳しいならば、ACE では次の2点が異なっていることに注意してほしい。
  1. アロケータは、テンプレートからの型のインスタンス化の時ではなくオブジェクトのインスタンス化の時に渡される。アロケータオブジェクトの参照はコンテナに保存され、メモリ割り当ての時に利用される。この動作は共有メモリへのメモリ割り当ての際に問題となるかもしれない。
  2. ACE のアロケータは、C の malloc のように、生の(raw)型化されていない(untyped)メモリを取り扱う。そのため、型を考慮しない。この点で標準 C++ のアロケータとは趣が異なる。この例外は ACE_Cached_Allocator で、これのみは強く型付けされている。

5.4.1 ACE_Allocator

ACE が提供しているアロケータは以下の4つである。
デフォルト以外のアロケータの利用サンプルが p.117-118 に記載されている。

5.4.2 ACE_Malloc

ACE では ACE_Allocator の他に一般的な用途向けインターフェースとして ACE_Malloc を用意している。こちらは (UNIXの)System V ベースの共有メモリやメモリマップドファイルに対するアロケートにも対応している。
コンテナのメモリ割り当てにこちらを利用したい場合には ACE_Allocator_Adapter を利用して ACE_Malloc テンプレートクラスを ACE_Allocator インターフェースへと変換する必要がある。
ACE_Malloc については共有メモリについて説明している17章で改めて解説する。
Index
Top