C++0xのunordered コンテナ

N2588 Working Draft, Standard for Programming Language C++

unorderedコンテナは、内部的には、まあ、ハッシュだ。現在のSTLの、map、multimap、set、multisetのハッシュ版に相当する、unordered_map、unordered_multimap、unordered_set、unordered_multisetが存在する。

使い方はとても簡単。現在のmapやsetを使う場合と、なんら変わらない。いままで、まあ、あれは、単なるハッシュだろうと思って、別に気にしなかったが、実際に規格を読んでみても、やはり、特に気にする必要は無さそうだ。私のような素人は、中身を気にせずに、定数時間で同じ要素を探せるmapやsetとして使えばいい。

ただ、気にならないことが無いわけでもない。

まず名前だ。なぜ、unorderedなのか。hashではだめなのか。C++の規格というのは、具体的な実装方法を規定しているわけではないので、実装を連想させるような名前はダメなのだろうか。しかし、unordered_mapなどとタイプするのは、いささか面倒なのだが

それから、bucketという概念も気になる。bucketの個数や容量、使用量を取得するメンバがあり、さらには、あるキーがどのbucketに属するかを取得するメンバもある。しかし、bucketそのものにアクセスする方法は無い。bucketそのものにアクセスできないのに、あるキーが何個めのbucketに属しているかのインデックスを返されたって、一体なんの役に立つのだろう。

追記：
bucketにアクセスするlocal_iteratorというものがあった。しかし解せないのは、bucket単位でアクセスできる利点だ。

>Keys with the same hash code appear in the same bucket.

規格では、同じハッシュ値のキーは同じbucketに入ることしか規定されていないように読める。つまり、似たようなハッシュ値のキーが同じbucket、あるいは隣接するbucketに入るとは書かれていない。bucketという概念をエンドユーザに提供する利点が分からない。

追記2：
同じハッシュ値が同じbucketに入ることが保障されているので、似たようなキーから、同じハッシュ値が生成されるようにしておけば、似たようなキーが同じbucketに入る。コレを利用して、大量のキーから、似たようなキーを得ることができる。キーの値が偏っていない場合に特に有効。しかし、そんなに使うかなぁ。