2015-10-07-01-連想コンテナのやり直し - project-enigma

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-2017 project-enigma.
Generated by CL-PREFAB.