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

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

最終更新日付：2015/09/18 01:00:00

≪ 2015-09-17-01-githubにCL-STLをアップし（て）ました

2015-09-19-01-STL書籍の掲載コードをCL-STLで書いてみよう ≫

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.6 倍程度だった。大きいと言えば大きい。とはいえ、SBCL の time で計測した限りでは、１回あたりのプロセッササイクルは微々たるものだ。人は (setf (stl:first obj) foo) のみにて生きるにあらず‥‥‥というワケでこれでいってしまおうかと思っているが、はて。

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