2015-09-18-01-mapとmultimapのキー変更を禁止する話 - project-enigma

2015-09-18-01-mapとmultimapのキー変更を禁止する話

>> Site top >> weblog >> 月別アーカイブ >> 2015年09月のlog >> 2015-09-18-01-mapとmultimapのキー変更を禁止する話

最終更新日付:2015/09/18 06:42:46


mapとmultimapのキー変更を禁止する話

2015 年 09 月 18 日

そもそも Common Lisp には const という考え方はないみたいだ。だがなんとかして塞ぐことが必要な部分もある。今回は map と multimap の話。

STL で std::map<K,V> とした場合、内部ツリーの要素の型は std::pair<const K, V> になる。だから、そんな map オブジェクトの要素を指す反復子に対して first メンバを変更するようなコードを書いてもコンパイルには通らない。これができてしまうと、(それが過失だとしても)型 K のキー値で順序付けられているはずの map オブジェクトの内部状態に不整合をきたしてしまう。だから要素の型が std::pair<K, V> でなく std::pair<const K, V> であることは理に適っているし、必要なことでもある。

では、CL-STL ではどうだろうか。CL-STL では、stl:map の要素は単純に stl:pair だ。Common Lisp には const という概念がないため、これはどうしようもない。だから先に書いた「キー値で順序付けられているはずの map オブジェクトの内部状態に不整合をきたしてしまう」ような変更が実際に可能というのが現状なのだ。

個人的にはまぁ、なんというか、「だったらそんなことしなければいいのに」と思わなくもない。自分だったら絶対にやらないし、やることに意味もない。でも CL-STL はもう github にアップロードしてしまったのだ。誰かが使うことを止めることはできない(何言ってる)。だから、こういうリスクはできるだけ塞いでおく必要がある。

で、const のない言語でそれをやるにはどうするか。いくつか方法を考えたが、結局有力なのは「pair からクラスを派生させてどうにかする」というものだ。メンバが増えることはない。ただ、(setf (stl:first obj) x) ができないようにするだけだ。ひとまずはこれで用を足すことができる。この派生クラスにはひとまず __key-pair という名前をつけている。外部的には、「first に setf できないことを除けば pair ですよ」ということになる。

問題は、この措置によって first / second(とそれぞれの setf )が総称関数になってしまうということだ。これまでは pair オブジェクトだけが対象の機能だったため、これらは関数であり、そして inline 宣言されていた。それが総称関数メソッドになったことで、どれくらいパフォーマンスに影響が出るだろうか。簡単に試した限りでは、stl:first への setf 1回あたりで 1.6 倍程度だった。大きいと言えば大きい。とはいえ、SBCL の time で計測した限りでは、1回あたりのプロセッササイクルは微々たるものだ。人は (setf (stl:first obj) foo) のみにて生きるにあらず‥‥‥というワケでこれでいってしまおうかと思っているが、はて。

 

コメント

このページにコメントする

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.