驚愕！gap buffer でのundo redoの難しさ！

つか、タイトル通りです。はい。
gapbufferをいちおう、バグ無し？までレベルを引き上げました。
とりあえず、gapbufferをtemplate引数で渡してundo redoを実現できるクラスを作ろうと思いましたが・・・
イカンセンむずかＣ。
とりあえず、満たしたい仕様は以下のような感じ

• 無制限 undo redo
• 専用コンテナではなく、std::listでもundo redo std::vectorでもundo redo 私の作った*1gapbufferクラスでもundo redoが出来る。*2

で、無制限 undo redo をする場合、とても都合のいいのはコンテナ内に入っている要素をerase(削除)せずにそのままにしておいて、
削除マーカーをつけてiterate(巡回)するときにその削除マーカーをつけたところだけアクセスしないようにフィルタリングして回るようにする事。
だと、私なりに調べて考えてみたのだが・・・。

もちろん以下のようなデータ構造はアホだと考えた。
struct char_type{
char charactor;
bool isDeleted;
};
説明するまでもないかもしれないが、1文字につき1byteのフラグ領域・・・無駄すぎ・・・。

私の理想としてはクラス内に とある型の配列があって、それとは別に削除しているマーカーを記すものがあれば良いと思った。
削除を示すマーカーは以下のようなデータ構造をlistとして実装する事にした。
mminからmmaxまで削除マーカーがついているというのをあらわそうとした。

//undo redoの記憶データ

struct operate_memory_data{

  typedef operate_memory_data self_type;

  operate_memory_data(size_type min_,size_type max_) :

 mmin(min_),mmax(max_){}

  size_type mmin;

  size_type mmax;

  bool operator<(const self_type &x){

    return mmin < x.mmin;

  }

};

削除を記すマーカーはどのような流れで更新するか？
ここラ変で頭痛がするのだ。

以下のようなフローチャートで作成していた。

text_edit_buffer buff;

while(1){

  buff,update();

  

  //insert とか push_back とか

  buff,イロイロな操作( );

  

  //必要があれば巡回

  buff.for_each();//(iterrator for ... みたいな

  

}

とりあえず、形的には大丈夫なのだが・・・
ちょっと実装上辛そうな面が・・・

毎回アップデートするたびに削除マーカーをしらべてイテレーションする。オーバーヘッドが辛そう。
実は、毎回アップデートする処理をするようにしていた。
ちょっと考えたら、undo redo は stack的な構造なので、
そんな意地悪しない限り毎回全部検索して削除マーカーを炙り出す必要はない事に気づいた。

テキストエディタ用のバッファなのでindexを指定すれば*3その値を返せるようにする。
これだ！これが辛い！！
いろんなコンテナで削除している要素を削除しないでmminからmmaxの間までみたいなフィルタリングするとなると、
毎回、削除マーキングされているのかどうかを調べるのが遅いような・・・
こんなイメージだ。

＊ 使用中
ー 削除済み
配列番号 :0123456789
こんな感じ:**----*-**

例えば、上記のようになっていると buffer[2]とすれば6番目の要素を返さないといけない。
これを実装するのは非常に遅そうだし、凄くメンドクサそう。
まずぃなぁ、もうちょっと 「STLの全コンテナでundo redoを実現できる構造」を考えてみたいと思う。

すでに、デファクトスタンダードな解があったりして＾＾；

*1:正確に言うとTakty氏http://aiwww.main.ist.hokudai.ac.jp/~takty/　が公開していたソースを元に私がSTL風味にしたもの

*2:ぽりもぉふぃずむ？っていうのか？

*3:例：buffer[1] みたいな buffer.at(1)みたいな