[[Hirofumi Fujii Start Page]]

データ収集や機器制御において、可変長データを扱う需要が多々ある。C++ では、可変長
データを扱うことのできる class が STL としていくつか用意されている。この文書は、
それらを使う際の覚書である。

STL に用意されている、これらの class は container と呼ばれ、
- vector
- dequeue （発音は慣習として "deck" と同じ発音）
- list
の3つがある。

更に、これらの class に対する adapter (container adapter) として
- stack
- queue
- priority_queue

が、
また assosiative container として
- set
- multiset
- map
- multimap
- bitset

が用意されている。

最初の3つは、同一 type の object を線形に並べて格納するもので、
その意味では同じ機能を果たす。しかし、要素の追加・削除・access に
対する制約や効率が異なる。
--------------------
vector は C の配列と互換性を持つ。先頭要素の pointer は
C の配列の先頭要素の pointer として扱うことができる。
例を示す。

vector は C の配列と互換性を持つ。先頭要素の address は
C の配列の先頭要素として扱うことができる。

 double rbuf[5];
 int result;
     :
 result = myfunc(rbuf, 5);
     
という C のコードは（myfunc の宣言を extern "C" で囲むなどの処理を
した上で）

 std::vector<double> rbuf(5);
 int result;
     :
 result = myfunc(&*rbuf.begin(), 5);

という C++ のコードに焼き直すことが可能である。
という C++ のコードに焼き直すことが可能である。注意すべきは、
iterator と pointer を同一視しないという点で、上記例では
先頭要素の "pointer" は rbuf.begin() ではなく &*rbuf.begin()
である（実装によっては、同一視できる場合もあるが、そのような
仮定をするべきではない）。 

一方、program 上、注意すべきは（C で見て連続配列に見えるように実装する
関係で）要素の追加など、size が増加するような操作の後では、
その前に取得した iterator が無効になる可能性があることである。
vector には index による要素への access が用意されており、
各要素の access には index を用いるのが安全である。

また、確保してある size を越えて
大きくなる場合に、現在より大きな size の記憶域を確保し、現在の内容を
copy して前の記憶域を解放するという操作が入るために、大きくなってからの
要素の追加には多大な memory 操作 cost がかかる可能性がある。
このような状況が起こりえる場合には、処理時間の予測が非常に困難である。
処理時間の効率化という観点からは、最大 size がわかっているような場合は、
最初からその size を確保しておくのが望まれる。
最初からその size を確保しておくのが望まれる。もし、C の配列との
互換性は必要なく、index による access がしたくて、しかも最大 size が
大きくなる可能性があるなら次の dequeue を使うことも検討すべきである。
-------------------------
dequeu は index による access （要するにあちこち random に読み書きする）
を想定した container である。字句的には double ended queue の略であり、
vector と異なり、後方だけでなく前方へも伸ばすことができる
（double ended）。

一つの配列をblock に分けて管理する実装を想定しており、C の配列との互換性は無い。
その代わり、巨大 size になっても、巨大な memory の再取得や巨大な copy は
発生しない。
-------------------------
list は前後関係による並びである。一度取得した iterator は、iterator が
指す object を削除したり変更しない限り有効であることが特徴である。
Sort しても、前後関係が変わるだけなので、その iterator が指す object は
変わらない。また、途中への挿入・削除も高速に行える（挿入・削除される
object とその前後の object の前後関係を書き換えるだけ）。

一方、index による access は STL としては用意されていない。もちろん
実装は可能であるが効率的ではない（先頭もしくは末尾から順にたどりながら
index を数えていくことになる）。
トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS