2015-09-18-01-mapとmultimapのキー変更を禁止する話
>> Site top >> weblog >> 月別アーカイブ >> 2015年09月のlog >> 2015-09-18-01-mapとmultimapのキー変更を禁止する話
最終更新日付:2015/09/18 01:00:00
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-2021 project-enigma.
Generated by CL-PREFAB.