2015-10-07-01-連想コンテナのやり直し
>> Site top >> weblog >> 月別アーカイブ >> 2015年10月のlog >> 2015-10-07-01-連想コンテナのやり直し
最終更新日付：2015/10/07 20:43:50
連想コンテナのやり直し
2015 年 10 月 07 日
9/21 に書いた通り、連想コンテナがバグっている。赤黒木の実装に関わる部分なのだけれど、追い詰めていくと根本的な問題であることがわかり始めてきた。そこで出直しをしてしまおうかというのが今回の話。
バグに気付く以前から、自分の赤黒木の実装にはちょっとした問題があった。「ヒント形式の insert 」がヒントを活用できていなかったのだ。実装では単純にヒントを無視していた。なんとかしなければと思っていたのだが、自分の実装では、ヒントが正しい場合でさえ定数時間での insert を実現できそうになかった。加えて、C++98 と C++11 以降でヒントとして渡すべき反復子の位置に関する（実装に対しての）要求仕様に変化があったことも（自分の）混乱に拍車をかけた。
さらに、自分の実装は処理をシンプルにするために、赤黒木の末端ノードに「外点」を持たせていた。これだとたしかに処理がシンプルになるのだけれど、空間的な無駄が大き過ぎた。汎用的に使えるコンテナとしては、これはやっぱり問題だ。
‥‥‥そんなわけで、もう全てを捨てて出直すことにした。STL の赤黒木実装を、Common Lisp に移植するのだ。この作業にどれくらいかかるかわからない。安定して動作するまでにはさらに時間がかかるかもしれない。まぁでも、頑張ってみる。
コメント
このページのタグ
Page tag : STLとその移植
Page tag : Common Lisp
Copyright(C) 2005-2018 project-enigma.
Generated by CL-PREFAB.
