vector, list の問題点

STL の std::vector, std::list は扱いやすく非常に便利なコンテナだが、一長一短がある。

std::vector は、O(1) でランダムアクセス可能だが、末尾以外での1文字挿入・削除は O(N) である。
std::listは、任意箇所での1文字挿入・削除は O(1) だが、ランダムアクセス不可で、任意位置への移動は O(N) である。
末尾への挿入（push_back()）はどちらも O(1) であるが、下図の測定結果をみるとわかるように list は vector の100倍程度遅い（vector: 2.375*10^(-9), list:5.375*10^(-7)）。

速度計測環境：C2D（ウルフデール） 3Ghz, 4GMem, WinXP, VC9

テキストエディタ用バッファなどの様に非常に大きなサイズになる可能性のあるバッファとして使用するには、どちらも速度的問題がある。
また、list は前後要素へのポインタを保持するので、小領域を多数保持するのはメモリ効率が悪い。
（なので、テキストエディタ用バッファに list を使用する場合は、行をひとつの文字列（string）とし、list で管理するのが普通）

gap_vector

gap_vector とは、下図の様にギャップ（空白）を挟んで保持するデータをアロケートしたメモリ領域の先頭と末尾に振り分けたものである。
ギャップは直前に編集（挿入 or 削除）された位置に設定される。
（※ ギャップバッファ＝gap_vector は、初期の Emacs で採用されていたデータ構造である。最近の版は未調査）

ギャップを考慮してインデックス計算を行えばよいので、O(1) でランダムアクセスが可能

編集位置に 'ａ' が挿入された場合：
編集位置から文書先頭方向に1文字が削除された場合（BackSpace)：

編集位置から文書末尾方向に1文字が削除された場合（Delete)：

編集箇所が局所化されていれば、ほぼ O(1) で1文字の挿入・削除が可能となる。

gap_vectorの実装

コンテナクラスがギャップ先頭位置とギャップ最終位置（またはギャップサイズ）情報を保持する。
vector を内部コンテナとして利用する簡易的実装と、std::vector, std::deque などと同様の本格的実装方法がある。

前者の方法による実装例：ギャップ・バッファ、後者の方法による実装例：プログラミング素材集

template<typename T, class Allocator = std::allocator<T>>
class gap_vector {
    .....
protected:
    size_t	_GapBegin, _GapEnd;       //  ギャップ位置
    std::vector<T, Allocator> m_gv;   //  データ、ギャップを格納する vector
        または
    pointer    _First, _GapBegin, _GapEnd, _Last;
};

gap_vectorのパフォーマンス

内部に vector を保持する簡易的な方法で筆者が実装した gap_vector のパフォーマンス計測を行った。

速度計測環境：C2D（ウルフデール） 3Ghz, 4GMem, WinXP, VC9

シーケンシャルアクセス

1億文字（100メガバイト）までのバッファについて、先頭から末尾までシーケンシャルにアクセスするのに要する時間。
list<char> は構築・破棄に異様に時間がかかるので、1*10^7, 2*10^7 のみ計測した。
結果は下図の通り。どのクラスも次の要素に移動する処理時間は O(1) である。

末尾挿入、先頭挿入

list<char> は挿入位置によらず処理時間は一定。（だが、末尾挿入は vector より2桁遅い）
gap_vector<char> の末尾挿入処理速度は vector<char> と同等。
gap_vector<char> の先頭挿入処理は O(1) で、末尾挿入処理の約10倍の処理時間がかかった。