Undo,Redoの実装法について

Question

こんばんは。

先日、以前に作ったundo,redoの実装を改良する展開になりました。

見てみると以前は双方向連結リストと「現在を表す」ためのポインタで実装していたのですが

様々な角度から考えまくった結果、片方向連結リストによるスタック二つ（undo用とredo用）の方が、さらにシンプルで無駄なく出来るという結論が浮かび上がってきました。

連結するデータはコマンドパターン（っていうのかな？）の、抽象（親）クラスのポインタです。

そうなると、その抽象クラスにおけるnextポインタとundo用とredo用へのポインタが一つずついるだけで、undo,redo実行する際も、先頭のポインタをいじるだけで済んでしまいますが

これより良い方法ってあるでしょうか？

っていうか、ここでもいらなかったとなると

片方向連結リストを使いこんできたら、段々双方向連結リストが必要な状況が分からなくなってきました。

実際のアプリで、双方向連結リストを「こういう時にはどうしても使いたい」っていう（片方向じゃなく双方向であるべき）状況をご存知の方いらっしゃいましたら、教えていただけませんか？

Answer 1

　C++ での実装方法はわかりませんが。

　INotifyPropertyChanged イベントを利用し、これのイベント引数を拡張して「変更前後の値」も通知できるようにする。イベント引数をスタックして、リフレクションを利用してプロパティを変更する。

なんてのはどうでしょう。

---

Jitta＠わんくま同盟

Answer 2

Jittaさん、早速回答ありがとうございます♪

＞INotifyPropertyChanged イベント

それっていうのはSystem.ComponentModelのやつでしょうか

あ～、そうかｗ

今作ってるアプリは、結構パフォーマンスが求められるのと、マーシャリングが面倒だったのでいっそのことマネージなしで行くか、ということで

実はここまで完全ネイティブを貫き通してきてるので、出来ればネイティブC++で書きたいのです。（説明不足で済みませんｗ）

そんでもって、今後最低もう一つはフォーム系のネイティブアプリを作る予定があり、当然UndoRedo機能はそれも装備するので

保守性、拡張性が十分に高いコードで、尚且つメモリや実行時間に対するコストは最小限となるようにしたいですね。

（そのために一端は相当面倒なことに突入しているのかもしれませんがｗ　それでもかなり出来て来てるので、このまま作っちゃった方が早いかなっていう）

＞イベント引数を拡張して「変更前後の値」も通知できるようにする。

もし「あるクラスのインスタンスのメンバ変数の変更」の類であれば、バイナリレベルで考えると

①そのインスタンスが格納されているコンテナを探り当てるための最小限の情報

②メンバのうちどれが変更されたかを示す情報

③そのコンテナ中のどれがそれに当たるかを示す、インデックスの役目を果たす情報（任意の型。インスタンス毎に）

④変更後、または変更前の情報（任意の型。インスタンス毎に必要ですが、どちらか片方だけ格納出来るスペースがあればOK。UndoまたはRedoのたびにswapで）

といった情報だけで出来ますよね。

①や②はコマンドクラスにつき一つあればいいです。具体的には

①はポインタ一つで足りるか、それ以外の方法があって2バイトで足りる、とかいうケースは実在してます。

②は、256個以上もメンバ変数持つクラスなんて作んないので、ほとんどの場合に置いて1バイトで足ります。（どっちみちアラインメント的には４バイトとか８バイトとかで十分な話になりますが）

③と④は別々に持たせ、それぞれ一つずつのバイナリ列にシリアライズ（および、undo, redo時にデシリアライズ）するのが非常にコードにしやすかった感じ、ですかね。（現状では）

Answer 3

汎用的なUNDO/REDOに使えそうなコレクションクラス(何らかのデータの集合を扱うクラスの総称)ならば、標準C++ライブラリ(STL)の std::stack/list/deque あたりで賄えると思いますが、STLでは実現は難しいのでしょうか？

---

わんくま同盟,Microsoft MVP for Visual C++(Oct 2005-) http://blogs.wankuma.com/tocchann/

Answer 4

とっちゃんさん、ご回答ありがとうございます♪

実現は十分可能だと思います。（それらのコンテナを隅々まで把握してはいませんが）

ただし、追加削除が激しい部分では、少なくとも線形リストとして一端処理したり

どっちみち速度を求めるところではポインタ配列などへ移し替えて・・・といったことを、状況に応じてやろうとした場合、結果としては、逆に「STLを採用する理由が乏しい」のではないか、という風に感じるのです。

出来ればコンテナに格納するのはインスタンスではなくポインタが良いのですが、STLは確実にそういう風に使われる、ということを知ることが出来ないのではないかと危惧しています。

std::stack/list/deque

これらのメリットとデメリット（使用が最大限に推奨される状況）はそれぞれどんな感じでしょうか？

Answer 5

本題書くの忘れた...

双方向の連結リストか片方向の連結リストかですが、多くの場合は片方向で済むと思います。

双方向の必要があるのは、片方向では毎回最初から移動しないと。。。となる場合があって処理が遅くなるときくらいではないでしょうか？

具体的には、検索などで見つけた時の位置を覚えておき、その前後に任意にアクセスする、後ろからいくつ、前からいくつというアクセスがあるというような状況の時など。。。

ですが、こういう用途ってほとんどないので、たいていの場合は片方向「でも」問題になることはないということだと思います。

もっとも、いまどき連結リストなどのコレクションクラスなら、自前で実装ではなく、各種アルゴリズムが適用できるSTLの利用を最初に考えるとなると思うので、双方向か片方向かなどという、実装詳細な話題はあまり出てこない気がしますが。

実際自分で汎用的なUNDOクラスを作るとしたら(任意のUNDO/REDOのためのブロックデータを管理するクラスという意味)、自前でデータ管理しないでSTLでデータ管理してそれにラッパーかぶせる形にしてると思います。

---

わんくま同盟,Microsoft MVP for Visual C++(Oct 2005-) http://blogs.wankuma.com/tocchann/

Answer 6

速度を求める。。。がどのようなものかによりますが、それでもSTLで十分に賄えると思いますよ。

STLの各コレクションクラスは格納対象をtemplateで指定していますので、operator=()や、operator<() などいくつかのアクセス方法があれば何を格納してもよいように作られています。

例えば、ポインタ配列などに移し替えるとした場合、std::list<hoge*> を std::vector<hoge*> や、std::array<hoge*> にしてから操作するというやり方もあります。

例えば、ポインタを格納だと解放処理が。。。ということであれば、std::auto_ptr や std::shared_ptr を使う方法もあります。標準ライブラリの使い方なので漠然とした質問はおそらくほぼ全員が漠然としか答えてくれません。

メリットは、何と言ってもリファレンスがあってすでに実用実績があり、世界中にサンプルコードが転がっていること。それと標準ライブラリなので、どのコンパイラにも用意されていることです(将来のVC++でも提供され続ける)。

デメリットは、template を多用しているので、今でも毛嫌いされることが多々あることと、利用者側にもそれ相応のスキルを要求すること(templateってなに？から始まるようでは効率よく利用するのは厳しいと思います)、C++の実装効率に対しての偏見がいまだに根強く残っていること。それと、スキルのある人がカリカリにチューニングを施した専用処理と比較した場合、速度あるいはメモリ利用効率などの面では勝てないというところですかね。

ちなみにSTLの実装は標準ライブラリであるだけに、すでにかなりチューニングがされていてメモリ利用効率も、実行効率も相当高いですよ。それでも片方向リストか双方向かのように専用処理のほうが効率がいい場合は多いです。

---

わんくま同盟,Microsoft MVP for Visual C++(Oct 2005-) http://blogs.wankuma.com/tocchann/

Answer 7

再度ありがとうございます♪

>双方向の必要があるのは、片方向では毎回最初から移動しないと。。。となる場合があって処理が遅くなるときくらいではないでしょうか？

概念的にはそうですよね。

＞後ろからいくつ、前からいくつというアクセスがあるというような状況の時など。。。

こう言う風にやる場合ってのが、考えてみるとなかなかないんですよね。大量にランダムアクセスが欲しいならポインタ配列に一度移し替えといた方が良い可能性が高いし、場所付け変えるだけならRemoveしてからInsertだけで話は足りますので、大抵の場合ではいらないんじゃないかと思ったのですが

冷静に考えてみると、ほぼ一貫して線形リストとして処理しつつ

その除外処理（Remove）を高速に行いたい状況が、唯一最大の説得力を持つ、「双方向リスト」の用途に思えてきました。

具体的に最も適切だと思うのは「可変長のブロックサイズをもてるメモリプール」です。

それも、双方向ではnextとprevポインタを両方持っているために、小さいデータを大量に扱う場合には適していませんが

そこそこ大きめのデータを大量に扱い、かつその解放タイミングが予測できない、といった場合は、削除の際に無駄な探索時間が生じない双方向リストが良い、のかもしれません。

＞自前でデータ管理しないでSTLでデータ管理してそれにラッパーかぶせる形にしてると思います。

やっぱりでもラッパーは欲しいですよね？ｗ

てことは、万が一使いたくなっても、コンテナ操作の概念を適切に切り分けておけば

後でそのラッパー（になり得る自前のデータ管理法）の内側にめり込む形にも、ほとんど手間なしで出来るはずです。

＞ちなみにSTLの実装は標準ライブラリであるだけに、すでにかなりチューニングがされていてメモリ利用効率も、実行効率も相当高いですよ。それでも片方向リストか双方向かのように専用処理のほうが効率がいい場合は多いです。

そこに関しては専用にはどうしても勝てない、でしょう

コンパイル時間をとんでもなく犠牲にするboostはともかく、いまのところそういう面ではSTLに勝てなかった試しはありませんｗ

ただ、どの程度のレベルかにもよりますね。普通に使ってる分では関知できないような差であれば・・・っていうことは常に付きまといますし。

＞デメリットは、template を多用している

これは、今回の用途では若干でかいんですよね。

私はクラスtemplateで無駄にコードサイズが膨らむ必要がない箇所とかでは

voidポインタと、インライン指定した関数templateによる、「最小限の範囲」での型の違い吸収で収まる場合はそうすることが多いのですが

それが出来る箇所でそうしてないと、コンパイル時間と実行サイズの両方に悪影響を及ぼしてしまうのではないかという危惧があります。

STLのコンテナのテンプレート引数にvoid*を指定しても可能ではあるかもしれませんが

見た目的にはそれは「故意に反発している」ような印象がして「う～ん」な感じなのですｗ

Answer 8

＞見た目的にはそれは「故意に反発している」ような印象がして「う～ん」な感じなのですｗ

ここだけ。STL側はC++でできることのいくばくかでも否定するようなことは可能な限り行わない実装になっています。もちろん、実装上不可能なものについてはその限りではありませんが。

ですので、void*をデータとして渡すことも別に問題ではありません。何に対する反発なのかわかりませんが、STL(やBoostなどのダックタイプ)は、明確な型を求めるためにtemplateを駆使しているのではなく、どんなものでもそれをあるがままに受け入れるためにtemplateを駆使しています。このあたりは感じ方の違い(templateに対する様々な思い込みや思い入れ)でだいぶ変わるようですけど。

なので、void*を持たせたいならvoid*を渡せばいいと思います。

---

わんくま同盟,Microsoft MVP for Visual C++(Oct 2005-) http://blogs.wankuma.com/tocchann/

Answer 9

ありがとうございます♪

う～んｗ

それは、そういう考えで行くともちろんそうでしょうが

その場合、使う時キャストをまた書くじゃないですか。

そういう事を考慮していくと、より一層ラッパーを作る手間と自作コンテナ作る手間に差異がなくなってくるので、STLを採用する理由が乏しくなるのです。

↓は自作のPtrArrayの宣言部のうち、一部分を削ったものですが

class PtrArray { 

	typedef Void* VP;
	typedef const Void* const CVPC;

        VP* pp;
	const szt ALLOC_CYCLE;
	szt num, len;

	Void Realloc( szt );

public:

	PtrArray( PtrArray&& );
	PtrArray( szt ALLOC_CYCLE_ = 8 );
    ~PtrArray();

	szt GetNum() const { return num; }
	
	template < class T > T Get( szt i ) const { return (T)pp[i]; }
	template < class T > Void Get( T* p, szt i ) const { *p = (T)pp[i]; }
	template < class T > Void DeleteAll() const { 
		const szt num_ = num;
		for ( szt i = 0; i< num_;++i ) delete (T)pp[i];
	}
	
	template < class T, class F > Void ForEach( const F& f ) const {
		const szt num_ = num;
		for ( szt i = 0; i< num_;++i ) f((T)pp[i]); 
	}
	
	template < class T > void DeleteInstancesAndResetNum(){ DeleteAll<T>();	num = 0; }
	Void CleanupWithoutDeleteInstances(){ 
		if ( pp ){ free(pp); pp = null; }
		len = num = 0; 
	}	
	
};

例えば↓の用に使えます

namespace MyEvent { class Super; } //があるとして

typedef MyEvent::Super* LPEVENT;

typedef const MyEvent::Super* LPCEVENT;

PtrArray a(32); //クラスtemplateは使ってないのでここでの型指定はなし

LPEVENT p; //任意の型のポインタ

a.Get(&p, 0);

LPCEVENT cp;

a.Get(&cp, 0); //受け取り手の型さえ明白になっていればそのまま同じように書ける

p = a.Get<LPEVENT>(0); //明示的に指定すればポインタのポインタを使ったり受け渡したりせずに使える。

a.Get<LPCEVENT>(0)->メンバ関数();　//nullにならないことがはっきりしているならこれも可

STLでこういう事を簡単にしようとすると、やっぱりラッパーが欲しいですよね？

ラッパーがあるとなると

実際に自作かどうかで差が出る「行数」って、だいたいのケースで100行もないくらいなんですよね。

Answer 10

このクラスそのものがポインタ配列を前提としたラッパークラスですよね？void** とすることで、任意のポインタ型を保持するポインタ配列に今風な皮をかぶせた構造(templateができる前によく見かけたものにそっくり)なのだと思われます。

そして、おそらくはこのコード自体はかなり古いものがベースになっていてそれを今風にアレンジして使っていませんか？

まぁそれはともかくとして、可変長のポインタ配列ということだとすると、std::vector あたりが候補に挙がると思います。STLのコレクションクラスは、本体以外にアロケータもあるため、どうしても最終的にはコードが大きくなってしまいます。そのため、単純な比較はできませんし、専用に小さくなるように作られたものと比べたらどうやっても勝てないと思います。

また、ラッパーですが、そのままでは使いにくいあるいは、利用する側にとって不自由であるのであれば、用意すればいいと思いますし、そうではないのなら別に用意しなくてもいいのではないでしょうか？

PtrArrayの場合、型を意識するのはコレクションクラスの外側で、その責任ごと利用者に押し付けてますよね。実装がそれでいいなら、なにもコレクションクラスが型情報を持つ必要はないと思います(設計論の話なのでここでは議論の対象としてません)。

CやC++の標準ライブラリを含め世の中の汎用あるライブラリは利用者の８０％程度がそのまま使えれば理想的と言われています。今回の例のような残りの２０％にあたる部分は無理して８０％側に合わせることはないと思いますよ。

---

わんくま同盟,Microsoft MVP for Visual C++(Oct 2005-) http://blogs.wankuma.com/tocchann/

Answer 11

ありがとうございます♪

このクラスそのものがポインタ配列を前提としたラッパークラスですよね？void** とすることで、任意のポインタ型を保持するポインタ配列に今風な皮をかぶせた構造(templateができる前によく見かけたものにそっくり)なのだと思われます。

そうですね。このクラスに関してはC++というよりベターCって感じに思いますｗ

っていうか、コンパイル時間と必要十分の汎用性とパフォーマンスと拡張性と保守性と記述の楽さを全部求めると、結構バリバリの近代的なC++より、もうちょっと低水準言語よりになりがちかもなって感じは、感覚的にありますね。

（インラインアセンブラまで行くと、CPUへの依存が強いので流石に「気軽に書く」って感じではないでしょうが）

std::vector あたりが候補に挙がると思います。

前計測した時、std::vectorは単純な配列と比べてそれなりに遅かったような気がしたので

これを使う目的が間違いなく「シーケンシャルアクセス・ランダムアクセス」問わず、アクセスの速度を求めるということになるので、PtrArrayで十分なところはこっちを使うと思います。

（そうやって拘りだすと、結局「重要なアプリ」ではいつも自作のを使いがちになるため、結局STLにあまり詳しくなくなるという循環になってる気がしますがｗ）

本体以外にアロケータもあるため

そうですね。前std::listの内部構造を調べることがあったのですが、アロケータの指定はSTLはふつーに出来るってことですね。

アロケータも込みでテンプレートで簡単に交換できるようにしっかり自作するのは、さすがにそこそこ骨なので、（書き方とか「どの程度の汎用性にするか」によってはそうでもないかなぁ）そういうチェックがしたくなったら、そのチェックには少なくともstdは優先的に使える可能性がありますし

また、stdのコードを見ながらその時々で考慮しようと思います

ただし、現状では、「非常に大きなデータ」に関してはメモリマップドファイルでファイル入出力を行って、それをメモリプールのかわりに使ってる、ってなこともやってるのですが(不要な時はマッピングを解除し、仮想メモリの圧迫を防ぎつつ、必要時のアクセスは結構速い)

それ＋必要な時はメモリプール（一括確保してからの切り分け）＋ふつーのメモリ確保＋スタック

の、４パターンの使い分けがほとんどうまく行ってしまっているので

とりあえずはアプリケーションの機能の実装を急ぐのが先決ですねｗ

PtrArrayの場合、型を意識するのはコレクションクラスの外側で、その責任ごと利用者に押し付けてますよね。実装がそれでいいなら、なにもコレクションクラスが型情報を持つ必要はないと思います(設計論の話なのでここでは議論の対象としてません)。

そうですね。この場合は使う側が意識して、適切にやってやる必要があります。

ただし、その場合、使う時に「ポインタを拾う方法がconstかどうかの指定がはっきり使用箇所ごとにコードに残る」という結果になるので、後で見たときに意外と意味が汲み取りやすかったりします。

それが面倒であれば、PtrArrayを継承するか包含するかなどして、別途クラスを作って、そこでtemplate引数をクラスtemplateとして固定してしまう、という方法もあります。「そういう自由を残す」って意味も持てますね。

今回の例のような残りの２０％にあたる部分は無理して８０％側に合わせることはないと思いますよ。

やはりそうですよね。

ありがとうございます。

Answer 12

ところで、単方向リストに関して、こんなん思いついたんですが、いかがなものでしょう？

struct LinearList {

	template <class T> static Void Release( T** pp ){ 
		for ( T* p; p = *pp; delete p ) *pp = p->next;
	}

	template <class T, class N, class F> 
	static Void Deserialize( T** pp, N count, const F& f ){		
		while ( count-- ){
			*pp = f();
			pp = &(*pp)->next;
		}
	}

	template <class T, class F> 
	static Void Serialize( const T* p, const F& f ){		
		for ( ; p ; p = p->next ) f(p);
	}
	
	template <class T> static szt GetCount( const T* p, szt i=0 ){
		for ( ; p; p=p->next ) ++i;
		return i;
	}

//その他諸々つづく↓

これだけだとなんのこっちゃということでしょうが

上のMyEvent::Superで例えるとこういうカラクリになります。

struct LinearList;

namespace MyEvent { 
	class Super;
	typedef LinearList ContainerType;
}

class MyEvent::Super {
	friend ContainerType;
	Super* next;
//その他諸々つづく↓
};

単方向リスト用の親クラスを継承するでもなく

STLのようにクラステンプレートで任意の型とnextポインタを持ったやつを作るでもなく、こういう風にfriend クラスに指定し

MyEvent::ContainerType::処理の概要を示した関数名（引数リスト）;

といった形に統一してしまう事で

・nextポインタと実データのメモリレイアウトが自由

・後でコンテナを変更するのは、STLでいうイテレータ的な概念に特別に頼らなくても、この方法でもほとんど苦にならない。

・nextポインタ一つ持ってれば他のクラスでも簡単に適用できる。

ということで、見慣れてしまえばほとんどデメリットがない気がします。

例えば、あるクラスがMyEvent::Superの先頭のノードへのポインタ(firstevent )をもってるとして解放処理に必要なのはこれだけです。

MyEvent::ContainerType::Release( &firstevent );

スタックとして「も」使えるだけですが先頭への追加と削除は線形リストとして既に宣言してあったので

PopとPushという別名を作ることにそれほど意味を感じなかったため、特に作っていませんが

処理内容としてはこんだけですよね。

//LinearList内で

	template <class T> static T* RemoveFirst( T** first ){		
		T* p( *first );
		*first = (*first)->next;
		return p;
	}
	
	template <class T> static Void AddFirst( T** first, T* p ){
		p->next = *first;
		*first = p;
	}

Answer 13

意図したとおりに動くのであれば、とくに問題はないと思いますよ。

オブジェクトの管理責任が分断している(セットアップされるブロックデータとリストの管理が一致していない)とか、利用者側に実装制約がある(nextポインタをTが持ってなければならないとか)ことを除けば、特別なにか。。。というのはないと思いますよ。

OOチックにやるよりはこっちのほうがいいということなんですよね?

ま、強いてあげるとすれば、Remove した時に返す p のnextは、nullptr を入れておけば、不用意に next にアクセスしたとしてもクラッシュを引き起こさないので、安定性が増すとかその程度ですかね。ま、その分代入の時間が増えると思いますけど。

---

わんくま同盟,Microsoft MVP for Visual C++(Oct 2005-) http://blogs.wankuma.com/tocchann/

Answer 14

ありがとうございます♪

>OOチックにやるよりはこっちのほうがいいということなんですよね?

（ちょいと長文になると思いますがｗ）

そういう場合はありますね。

その１として、仮に継承でnextポインタを持たせた場合はメンバの配置が自由に変えられません。

次に、STLでもとられてるような感じは、関数とかtypedefとかなしにして概念的にものすごくコンパクトにまとめると

template <class T>
struct NODE {
	T value;
	NODE* next;
};

こんな感じの物を、listとかが内部で管理してる（実際にはstd::listは双方向）っていう感じになりますよね。

それで、今までの流れで触れたように、ここでTをポインタにしたいと仮定してみます。

この場合上記

class MyEvent::Super {
	friend ContainerType;
	Super* next;
//その他諸々つづく↓
};

だと、nextはSuperのポインタであり、これ以上の情報は必要ありません。

対して

struct NODE {
	MyEvent::Super* value;
	NODE* next;
};

この場合

nextとはNODE構造体へのポインタとなり、Superへのポインタとは別に、インスタンス毎にもうひとつポインタの領域が必要になる、という点が一つありますね。

もうひとつは、キャッシュとの兼ね合いです。

nextをたどった時、前者ではその近くにメンバがあることになります。

対して後者だと、nextはSuperのポインタではないので、一端valueを介してSuperのthisポインタを得なければ非staticなメンバが使えません。

そしてその位置は、十分に離れている可能性があります。

なので、全部のインスタンスに対して一括処理をかけるなどの場合は、前者の方が優れる可能性が高いです。

ただし、メンバ変数が多ければ、前者はキャッシュに連続で乗る率は下がります。

対して後者では、独自のアロケータを使用してメモリ位置を明確に変えることにより、インスタンスのあるメモリ領域と

連続してNODEがあるメモリ領域とをわけることが可能です。

その場合、一括処理ではインスタンスとポインタのある領域が離れていて、L1キャッシュとかは「ほぼ確実にキャッシュミス」となりますが

NODEサイドを連続して作っておけば、「特定のポインタ」からコンテナ上の位置を割り出すような探索に関してはかなり有利になります。

ただし、そう言う事が大量に行われて、それゆえ速度が重要なのであれば、やはりそういう処理の周辺ではポインタ配列に移し替えて～

の方が良いかもしれないので、大抵の状況では前者が勝る可能性が高いように思います。

ただｗ

こっちだけの話なら

struct LinearList {

	template <class T> static Void Release( T** pp ){ 
		for ( T* p; p = *pp; delete p ) *pp = p->next;
	}

nextという名前以外別段束縛はしてないんですよねｗ

Superにnextを持たせるのをやめても

↓こういう事をしておいたNODEをTとしてやっても、LinearList::Releaseを使っていいわけですし

struct NODE {
	MyEvent::Super* value;
	NODE* next;
        ~NODE(){ delete value; }
};

少なくとも、メインで「先頭のインスタンスを指すポインタ」をもち、主に管理するクラス

というのは、セオリーとしてはやはり必須と思うので、そこにその辺の機敏をまとめておけば、変更する時も僅かな手間で済むと思います。

＞ま、強いてあげるとすれば、Remove した時に返す p のnextは、nullptr を入れておけば、不用意に next にアクセスしたとしてもクラッシュを引き起こさないので、安定性が増すとかその程度ですかね。ま、その分代入の時間が増えると思いますけど。

Removeするパターンは、実は現状かなり絞られていて

・インスタンス破棄の一瞬前

・UndoRedoで、任意の数、任意のインデックスのポインタをユーザーが選択中、「削除」処理を行った際、アプリ上ユーザーがコントロール出来る領域からの「削除」のために「ポインタを外す（だけ）」

・付け替える

などぐらいです。

いずれも、次に使う時が来る場合はnextをまた代入するか、破棄されるので使わないかってとこになります。

が！

とっちゃんさんのこのご返事により、まだベストを尽くしてなかったことに気付きました！

いやぁ、ありがたいｗｗ

『UndoRedoでの削除挿入』

このとき、今までは

インデックスを示すための情報と、外したポインタを律義に全部保存してたんですが、外してる最中はそれだとnextは役立たずになってしまいます。

しかし「外したもののリスト」をnextでつなぎ合わせておけば

その先頭のポインタ一つを保存しておくだけで、全部拾い直せますよねｗ

さらに踏み込むと、もう「インデックスを示すための情報」の部分に「prevに相当するポインタ」を順番に格納しとくとかでもいいかもしれませんｗ

そうすれば挿入位置を探索する必要がありません。

普段は単方向リストとして扱っといて、UndoRedoのときだけ挿入削除をめちゃめちゃ楽にするために疑似双方向リストとかにするって方法です。

ただし、インデックスでなくポインタで行う場合「如何なる編集がされたとしても指す先のポインタはdeleteされてない」という保証が出来るかどうかを綿密に検討しておく必要がありますね。

超巨大なデータになるのであれば、メモリマップドファイルとかでシリアライズし、マッピング解除、なんて事があると前提が崩れるかもしれませんので、考えどころですね。

あ、それと、例えばアロケータの解放サイドですが、一括解放とかで自由に行う方法は

struct LinearList {

         template<class T, class F> static Void ReleaseF( T** pp, const F& f ){
		for ( T* p; p = *pp ; f(p) ) *pp = p->next;
	}

これだけでOKそうな気がしてきましたｗ

Answer 15

コレクションクラス(UNDO/REDOに限らない)などの構造をどうするかはそれを使うのがだれか？や、どんなものを格納するのか？に強く依存する問題でもあるので、これが最良となるのは必ずしも一つとは限りません。

なので、利用する場面で struct LinearList が最良ならそれでいいのではないでしょうか？私からは利用場面が見えないので、最良なのかは判断できません。

あと、双方向にすると。。。という部分も実装全域が見えていないからよくわからないし。。。

UNDO<->REDOのそれぞれのバッファに持っていく時に楽かどうかは、もっと大きな視点も必要です。

とくにREDOバッファは頻繁にクリーンナップ処理が入ります(UNDOバッファに追加するタイミングで原則クリーンナップされます。REDO->UNDOの場合などの例外もありますが)。

他にもいろいろな状況があると思いますが、そのすべてが最速である必要があるかは何とも言えません。ある部分が最速であれば、ほかの部分でその最速を維持するために、遅くなる場合があるのは仕方ないかもしれません。全体を見てコードレビューしているなどではないので、何とも言えませんが、これだけは言えます。

UNDO/REDOバッファに格納するだけがUNDO/REDOの処理ではありません。バッファに格納する以外の部分(や使う人のスキル)も含めて最適化を行えばよいのではないでしょうか。

---

わんくま同盟,Microsoft MVP for Visual C++(Oct 2005-) http://blogs.wankuma.com/tocchann/

Answer 16

さきほどポインタの格納を修正しつつ、また良い感じになってきました。

ありがとうございます♪

struct LinearListが絡むべきクラスを使っている部分については、数万行(コマンドクラスの派生クラスやUndoRedoに関しての操作はものすごく微々たるものですが、それとは別の、めちゃめちゃアプリ全体の主役的なクラスに暫定的に使っていますので)

その「絡むべきクラス」のうち、Undo,Redoが絡む、疑似双方向にするかどうかが関係する可能性のある部分の全貌については数千行（ただし、特定の機能の修正はほんのちょっとの手間で済みます。）

程度になってしまうので、流石に全部を載せるのは無理ゲですがｗ

↓概要としてはこんな感じですね

UNDO/REDOバッファに格納するだけがUNDO/REDOの処理ではありません。バッファに格納する以外の部分(や使う人のスキル)も含めて最適化を行えばよいのではないでしょうか。

UNDO/REDOに関しては、ユーザーの操作（マウスやキーボードでの）なので、メモリへの配慮は欲しくても、コンテナの仕組み的な観点での速度は、まず不要と考えます。

また、「スキル」に関しては、よほど読み辛いもの以外ならなんでもござれで構いませんｗ

（設計の悪くない限りにおいて）

UNDO<->REDOのそれぞれのバッファに持っていく時に楽かどうかは、もっと大きな視点も必要です。

その時に楽かどうかって事ならどんなデータであっても問題ないです。（楽さは特に変化しない）

最初に書き込む時は、データを参照（か、今のところ単純な値型ばっかなので値渡し）として渡すだけで、内部的に、先頭と最後尾を示せるポインタを持った「可変長サイズのバッファとその確保サイズを持つ単方向リスト」が自動的に生成され （この単方向リストは、今までの話題のそれとはまた別の箇所の話です。↓宣言部はこんなイメージ）

Void WriteData( const Void*, szt size );

template <class T> Void WriteData( T t ){ WriteData( &t, sizeof(T) );  }   

最初の書き込みが終わったら 、コマンドの基底クラスのこんな感じのEndCreate関数を呼び出すことによって

Void EndCreate(){
     data.SerializeAndRelease();   
     index.SerializeAndRelease();    
}

一元化できます。

※SerializeAndReleaseは線形リストに含まれるデータをmalloc1回とmemcpy複数回で連続データにして、ここでの線形リストはその時解放されます。また、コマンドクラスのデストラクタで一元化されたデータはfreeされます。

data用とindex用のバッファは別々になっており（所詮はvoid*でmallocな任意の長さのメモリになるので、WriteDataやWriteIndexとかの時の型は自由。インデックスのところにポインタを入れようが、それぞれに入れた要素の数が違おうが、出すときと入れる時に同じことをやってさえいれば問題ありません。）

上記dataとindexは同じ型ですが、これはコマンドクラスから読み取ったりプロパティのswapなどを行う際

BeginRead関数（コマンドクラスのメンバ関数）などで、内部的に使用するcurrentアドレスを示すByteポインタのアドレスをリセットしてから

「同じ順番で同じ型として取り出す」

というのみの制約（ここだけは十分に注意が必要）により、「個数も型も簡単に自由に調整できる」仕様になっています。

そして、とりあえずはコマンドの基底クラスを継承してプロパティ変更用のクラスと、ポインタの追加削除用のクラスを作りました。

ただし、それ以上は型ごとに増えても際限ない可能性があったため

とくにREDOバッファは頻繁にクリーンナップ処理が入ります(UNDOバッファに追加するタイミングで原則クリーンナップされます。REDO->UNDOの場合などの例外もありますが)。

上記のとおり、バッファその物に関してはコマンドクラスのデストラクタ時に解放されるので無問題ですが

ユーザーから直に触れられないようにポインタを付け変える「だけ」の「削除（というか退避）」をされているポインタがあった場合は

それに対してデストラクタを全て掛けたいので

「継承した『ポインタの追加削除用のコマンド』クラス」は、デストラクタが呼ばれたときに「ポインタが退避済みだった場合に実行されるべき、関数へのポインタ」をメンバに持ちます。

この関数ポインタはconstかつprivateであり、これを指定せずにこのクラスをnewすることは出来ないという仕様になっています。（なのでそれを忘れるという事はないです）

class EditHistory::Command::AddRemove : public Super {

    virtual Void UndoRedo(Int) override{ 
        urfunc( this );
        added ^= True;
    }

        typedef Void (* const FUNC)(AddRemove*);
    
    FUNC urfunc; //UndoRedoの時だけ使われる
    FUNC delfunc; //デストラクタで呼ばれる
    const szt count; //削除または追加したアイテムの数
    Bool added; //追加済みフラグ（つまりつぎにUndoまたはRedoするときはRemove処理になるかどうか)

public:
//その他

こんな感じですかねｗ

「順番と型」はしっかり守らないといけないという注意点はありますが

その操作を同じクラスの、ソース上も近い位置にまとめておくことで、かなり危険は減らせます。

どういう風に記録するかって部分は

コマンドクラスをいじることなく、またテンプレートクラスで実行ファイルサイズを肥大化させることもなくて、かつかなり自由ですね。

Answer 17

＞「順番と型」はしっかり守らないといけないという注意点はありますが

それで賄えているのなら問題はないのでは？

ソース上の近い位置にまとめておけば視認性は上がるので、人的ミスの危険性はある程度は減らせます。まとめて書いてくれていれば。。。

でもそういう部分はコンパイラにさせるのが今の開発の潮流のような気がします。気がするだけですけど。

---

わんくま同盟,Microsoft MVP for Visual C++(Oct 2005-) http://blogs.wankuma.com/tocchann/

Answer 18

お気遣いありがとうございます♪

>でもそういう部分はコンパイラにさせるのが今の開発の潮流のような気がします。気がするだけですけど。

言われてみると確かにそんな感じがしますねｗ

今後書いていくにあたって、もし改変などの時にその正確なチェックが煩わしく感じたら

また「型や順番に関しての自由を束縛する代わりに、その辺のことをCommandクラス側に管理させるような」

Commandの派生クラスを作ればOKそうです。

そう言う方法なら、例えば「一つの操作につき型は一つ」「バッファにはその固定サイズの配列として、添え字指定でアクセスできる」

といった固定も出来るので

取り出し順番が任意で良いというメリットがありますね。（そっちで十分ならそっちの方がより扱いやすくて良いかもしれません。その辺はどういう状況が今後出てくるかわからないので、っていう模索段階ですね。）

なお、現状では「疑似Prevポインタ」案より「インデックス指定」案のほうが「他の処理との依存性が低い」ので良さそうだという感じになっていますが

それとは別に、UNDOREDOの際に、時間がそれなりにかかる可能性のある処理も出現可能性があるのですが

マルチスレッドが絡んだ時に、UI側のスレッド（Commandクラス生成や受け渡し時）および別スレッド（処理する側）の両方で、特定のオブジェクトの情報が必要になった場合

尚且つREDO除去などによるクリーンナップが入る可能性があって

しかも「出来れば実体のコピーをとらなくていい方法が欲しい」

となると、破棄タイミングの問題があるので

今までは参照カウント方式のスマートポインタの類は特別使用せずにやってたのですが

こういう状況では

最小限の手間で、記述も楽に済ますためには「スレッド間の参照についてのみ参照カウント方式を採用する」ような何らかの機構を、インスタンスごとに持つようにする、っていうのが一般的な方法なんでしょうか？（仮に一般的でなくても、思いついたらその方が圧倒的に便利そうなのでそうしようかなと思い始めてますがｗ）

なお、LinearListをSimpleLinearに

そして解放処理(Release,ReleaseF)の名前も微妙に変えましたｗ（中身は変わってませんがｗ）

struct SimpleLinear {
	
	template <class T> static Void DeleteAll( T** pp ){ 
		for ( T* p; p = *pp; delete p ) *pp = p->next;
	}
	
	template<class T, class F> static Void ReleaseAll( T** pp, const F& f ){
		for ( T* p; p = *pp ; f(p) ) *pp = p->next;
	}

どっちかというとこっちの方が意味が汲み取りやすそうに思います。

Answer 19

複数のスレッドから同時多発的にアクセスされる可能性があり、なおかつ寿命を管理する存在がない場合。。。ということでしょうか？

でもその話と、UNDO/REDOの抱えるバッファとは別では？

いや、確かにmallocとか低レベルのメモリアロケータから見ればどっちがどっちとか関係ないですけど。。。それはこの話とは別だろうし。論点がわからんです。

UNDO/REDO の話とは別に。。。どういう形がいいのか?という設計論であれば、また別のスレッド(議論のためのスレッド)を起こせばいいと思います。

でも、DeleteAll は

ReleaseAll( pp, []( T* p ){ delete p; } ); って書けますよね？ラムダの使える VS2010以上限定ですが、たしか環境はVS2010でしたよね？

どちらもインライン展開されるから最終的には同じ結果だとおもいますし、なんといってもソースが１つになるので、変更があっても変更漏れが発生する確率が０％になりますし、バグ修正のコストも半分以下になります。

ちなみに。。。

for( T* p; p = *pp ; )
{
  *pp = p->next;
}

が共通項なわけですが、バグってませんか？

ま、それはともかく、わたしなら

while( *pp != nullptr )
{
  T* p = *pp;
  f( p );
  *pp = p->next;
}

あるいは

for( T* p = *pp ; p != nullptr ; p = p->next )
{
  f(p);
}
*pp = nullptr;

と、書くかな。

もし、外部からこのリンクリスト(ppの指す先)にアクセスする可能性があるのなら、

T* p = *pp;
*pp = nullptr;
for( ; p ; p = p->next )
{
  f(p);
}

ですかね。

いずれの場合も p は最適化されれば、何らかのレジスタが使われるだろうし。この程度なら、ループはかなり高い確率でインライン展開されると思いますし。

---

わんくま同盟,Microsoft MVP for Visual C++(Oct 2005-) http://blogs.wankuma.com/tocchann/

Answer 20

ありがとうございます♪

>でもその話と、UNDO/REDOの抱えるバッファとは別では？

はい、確かに「切り離しも可能」ですね。

もちろん解放の「手段」自体は別概念なので、実際AddRemoveクラスでは、デストラクタで呼ばれる関数ポインタを通してコマンドクラスの外側で解放処理の記述を管理できるようになっています。

ただし、UNDO/REDOの時に「ポインタをデータに格納している」ことから、コマンドが原因で走るスレッドとコマンドの解放が原因でおこり得るポインタに対する解放処理

に起因する、ということであれば、無関係とは言い難いと思いましたので。

>ReleaseAll( pp, []( T* p ){ delete p; } );

はい、その件に関してはその通りです。載せた後で私もちょうど思いました。まぁ、現在ヘッダで、すぐ下に書いてあるし、片方向リストの解放処理は（私としては）見慣れてるから別段良いかなって思った、っていうことですが

そういう考え方でいけば確かにReleaseAll( pp, []( T* p ){ delete p; } ); の方が良いかもですね（別のコンテナ形式を作った場合にも、こっちはコピペだけで行けますし）

for( T* p = *pp ; p != nullptr ; p = p->next )
{
  f(p);
}
*pp = nullptr;

フツーの一括処理のあと外すとかならこれで良いんですが

解放処理の場合そうはいきません

f(p);の時点でpが死んでる（可能性がある）のでpのnextにアクセスできなくなってしまいます。

なので、「最低2つのポインタ」が必要になります。

私のコードではもうひとつのポインタは「受け渡す時にアドレス指定してポインタポインタに化けてる」形です。

いちおー、単なる一括処理ならこうですね。

	template<class T, class F> static Void ForEach( T p, const F& f ){
		for ( ; p ; p = p->next ) f(p);
	}

Tはconstポインタと非constポインタの両方をカバーします。

>が共通項なわけですが、バグってませんか？

一見「あれ？」っと思うかもしれませんが、これが実は全くバグってないんですよｗ

もしこのコードを使いたいという場合は、冷静に一つ一つの処理を考えてみてください。わかる瞬間は必ず来ます。

（なお私のコードでもちろん、元のポインタはnullptrになりますね。）

もちろん、もうちょっと本格的に考えると、「元のポインタ変数のアドレス」はヒープ上である可能性があるので、ポインタ変数を別途用意した方が、スタック操作になる可能性を考慮すると・・・

ということになりますが

	template<class T, class F> static Void ReleaseAll( T** pp, const F& f ){
		for ( T *a, *b = *pp; a = b ; f(a) ) b = a->next;
		*pp = nullptr;
	}

CPU特性によっては、必ずしも得策とはなり得ない場合もあることが判明しているので、ここら辺の機敏は微妙なとこ（解放処理はそんなに速度を求められるべきではない可能性もありますから、趣味の範囲、に近い）ですね。

＞もし、外部からこのリンクリスト(ppの指す先)にアクセスする可能性があるのなら、

それは、こっちサイドからは考えなくていいです。ppの指す先を保持してる側の責任です

※マルチスレッドを考慮するなら排他制御をおこなわないといけない。・・・といっても、実際のアプリでは別スレッドが走ってるときに「同じコンテナ」にアクセスするなら、そのタイミングで全解放はあり得ない、と言えますが。（それこそ、「ポインタだけはコピーしたコンテナ」を別スレッド用に作って、参照カウント方式、となり得ましょう。）

 

 

やっぱSimpleLinearからSinglyLinear（Singly Linked Linear Listを縮めて）にさらに変えましたｗ

例えばInsertはこんな感じですかね。（一応この関数はインライン指定は解除してあります。また、その他突っ込みどころあったらお願いします）

template < class T, class F >
Void SinglyLinear::Insert( T** pp, T* const to_insert, const F& f ){	
	
	T* p;
	for ( ;p = *pp; pp = &p->next ) if ( f( p ) ) break;	
	to_insert->next = p;
	*pp = to_insert;

}

ちょいと3時ごろからしばらく出かけてきますね♪

Answer 21

＞バグって。。。

あ、そうか。先に評価が来るからそこで代入されるので問題ないのか。。。何ともトリッキーな。。。

で、next ポインタはそうですね。先に書いた私のコードだとどうなってるかわかりませんね。

while( *pp != nullptr )
{
  T* p = *pp;
  pp = p->next;
  f(p);
}

こんな感じですかね。とりあえず、ソース上の変数の数は同じです。もちろん新たな変数は増えてません。最適化されればどっちも同じでしょうけどｗ

ここまでくるとどっちが好きか?という好みの問題に近いので、好きなほう使えばいいよ！でしょうしｗ

＞もちろん、もうちょっと本格的に考えると、「元のポインタ変数のアドレス」はヒープ上である可能性があるので、ポインタ変数を別途用意した方が、スタック操作になる可能性を考慮すると・・・

ヒープ上のオブジェクトにアクセスするのとスタック上にアクセスするのでは何か違うのか?と言ったら、スタックにあるものが、ebp など、スタック起点アドレスからのオフセットなのと、メモリという絶対値アクセスの違いくらいで、確か現状ではCPUのアクセス速度的には変わらなかったと思います（変わってても、CPUのコード処理のオーダーの中に埋もれるくらいの差でしかないと思いますけど）。

むしろ、ポインタが指し示す先がCPUキャッシュに入っているか?のほうが速度的な面では大きな影響店だと思いますよ。それを制御できるかどうかにかかわりなく。

---

わんくま同盟,Microsoft MVP for Visual C++(Oct 2005-) http://blogs.wankuma.com/tocchann/

Answer 22

どうもありがとうございます♪

さきほど帰ってきました

やっぱり自然の中は良いですね。

心が洗われたような気分です。（空気だけじゃなく「音」も全然違いますし）

while( *pp != nullptr )
{
  T* p = *pp;
  pp = p->next;
  f(p);
}

たしかにこういうコードの方が一般的に見かけそうな気がしますねｗ

ただおそらくは、「おおっと、ご注意を」ですねｗ

  pp = p->next;

↓

  *pp = p->next;

やはりポインタのポインタが絡んでくると、よほど触りなれたコードでない限り、かなりの上級者もポカミスしがちですから

それ相応の注意力が要りますね

例えば

*pp = (*pp)->next;

がやりたいのか

pp = &(*pp)->next;　

がやりたいのか、あるいは「その両方を一つの関数内で区別して行う必要がある」

のか、その辺も集中してないといけません。

引数にも注意が必要で

T** pp

と

T**& pp

ではまた違いますよね（いちいち僅かでも注意を払うのは面倒なので、別の角度から考えることによって、現状後者を使う事はないように組んでますがｗ）

私はもう片方向リストのコードを何度となくいじってて、この辺に関しては「自分の中である程度定型化」してしまってるので、「後で関数ごとの比較がしやすいように」縦の行数が少なくて済むほうを使ってますが、同じコードになる限り、この辺は任意ですね

「人に見せることを真っ先に考えなければならない」のであれば、とっちゃんさんのコードのように、一つ一つ分けた方がより親切かもしれませんｗ

＞ヒープ上のオブジェクトにアクセスするのと　～　それを制御できるかどうかにかかわりなく。

確かにそんな感じがしますね。

以前調査した時に、thisポインタからのオフセットかスタックかによって、命令数に変化はありましたし、計測上の差はありましたが、それが複数のループ内でさらにインライン化されてると、なんとインライン化されてない場合と比べて逆に遅くなった場合もありました。（私のCPUは2way set assosiativeで、「たぶん、あるループの先頭からL1命令キャッシュに読み込んでる可能性があります」）

その時は、インライン化されない場合はスタック上に展開した方が命令数が少なくなって高速になった

と記憶していますが

それも状況次第、CPU次第ってとこでしょうね。

いずれにせよ、デストラクタをはじめとする解放関数はそんなに頻繁に走らないようにすることの方が大切だと思うので、実際のアプリ上ではどうなろうと誤差の範囲でしかないでしょう。

参照カウント方式のことについては

現状「その案が良さそう」なことは確かなので、それで書いて見て、万が一うまくいかなかった、とか疑問が生じた場合には、新規にスレッドを立てさせていただいて、そこで質問させていただこうと思います。

少なくとも、現状でも結構な収穫があり、十分情報が集まってきたと思うので、今回はこの辺で再度、開発への「超集中期間」に戻ろうと思いますｗ

じっくりと様々な疑問にお付き合いいただき、本当にありがとうございました♪