xor_list

C++ Hamigaki

暇つぶしにSTL風にXOR連結リストを書いてみました。
<hamigaki/xor_list.hpp>
ドキュメント
wikipedia:XOR連結リスト
要するに、某巨大掲示板で昔話題になった「マジックリスト」のことです。
そのときアップされていた某氏のコードを参考にしました。
自分も途中まで書いていたので、それも参考にしつつ、「XOR連結リスト」の方が一般的みたいなので、xor_listと改名しています。

実用性はあまりないと思うのですが、割とまじめに書いています。
以下、特徴。

  • Boostなしで1ファイルだけで利用可能(一部Boostの劣化コピー品含む)
  • 等価でないアロケータ対応
  • sort()も実装(マージソート)
  • VC++9.0(32/64bit)、g++4.4.0で動作確認済み
  • 一応ドキュメントも書いた

コンテナ実装の参考になればと。
気が向いたら解説書きます。