LRUSet

キャッシュのデータ構造について。「キャッシュのデータ構造 with Boost.MultiIndex」と「slist LRUMap」でできるっぽいので、それぞれでLRUSetを実装してみた。GetかAddするとキューの末尾に並び替えられるというもの。

まずBoost.MultiIndexのほう。http://github.com/firewood/test/blob/master/MultiIndexTest.cpp
modify()でlast_accessメンバを更新すると自動的にソートしなおされる。この手軽さと強力さはすばらしい。ただVC++だとエラーメッセージからエラーの原因をつかむのが難しかったりする（「'boost::multi_index::detail::bidir_node_iterator' から 'boost::multi_index::detail::bidir_node_iterator' に変換できません」とか）。

でstd::setとslistの組み合わせのほう。http://github.com/firewood/test/blob/master/LRUSet.cpp
set+slistを実現するためにsetにはノード構造体のポインタを入れることにした。ノード構造体はnextとvalueを保持していて、setは次のノードの値（next->value）でソートするという変則仕様。リンクチェーンの更新はnextとvalue、自分と前後で計6箇所書き換えている。kinabaさんの元のソースではポインタの差し替えをしているのだが、ポインタのsetにおけるポインタは要素の値であり直接書き換えられない（ポインタのポインタのsetにすれば差し替え可能になるが、余計なメモリを消費するくらいなら双方向リストにしたほうがよい）。そのためわざわざ前のノードのポインタも取得している。実用性はないがパズルとしては楽しめた。