私リスト、魔法の国から来た11歳の女の子だよ！♪
…という話じゃないです。
以前、単方向リストの話題を振りました。
単方向リストは双方向リストほど自由度がない反面、
要素に付与しているポインタが半分で済むため、メモリ消費量が抑えられます。
要素が10000個あれば、32bit環境だと40KBの節約になるわけです。
40KB分のメモリを増設すれば解決ですね。
これを丸く収めるいい方法があります。
それがマジックリスト。
単方向のメモリ消費量で、双方向の自由度！
つまり、正方向、逆方向のどちらでも辿れるのに、
要素毎のポインタが１つだけというリストです。
ってなわけで作ってみました。[download]
要点を抜粋したソースが以下です。
template<typename T>
class _magic_Node{
unsigned int addpointer;
T value;
_magic_Node<T> *otherside(_magic_Node<T> *p){
unsigned int io = addpointer ^ ((unsigned int)p);
return (_magic_Node<T> *) io;
}
void setptr(_magic_Node<T> *prev, _magic_Node<T> *next){
addpointer = ((unsigned int) prev) ^ ((unsigned int) next);
}
void changeptr(_magic_Node<T> *before, _magic_Node<T> *after){
addpointer ^= ((unsigned int) after) ^ ((unsigned int) before);
}
_magic_Node(T t, _magic_Node<T> *prev, _magic_Node<T> *next):value(t){
setptr(prev, next);
}
~_magic_Node(){}
};
見てのとおり、Tの他にはunsigned intしかメンバ変数を持っていません。
setptr()はprev, nextのポインタを受け取り接続情報として格納します。
othersize()は、片方のポインタを受け取り、もう一方のポインタを返します。
changeptr()は、接続情報を変更します。
リストは基本的に先頭か末尾から順に辿ることしか出来ません。
つまり、prevとnextのどちらかの情報は持っているわけです。
そこで二つのポインタのアドレスを重ね合わせた値を持っておいて、
片方の情報を受け取ることでもう一方の情報を取り出すようにすればいいのです。
本来のマジックリストは加算を使うのですが、ここではXORを使ってみました。
アドレスをただの整数としてみなした計算を行っているので、
セーフティを謳う言語ではこれを実装することはできません。
分かりやすく言い換えると、フリーダムなC言語万歳。
なお、イテレータの前後で要素が追加/削除された場合、
イテレータの移動が未定義になってしまいます。
また、イテレータ側で要素の前後の面倒を見ないといけないので、
イテレータのサイズが通常の双方向リストより大きいです。
end()の生成コストも大きくなっているのが問題ですね…。