ハッシュとイテレータ

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
アバター
SUE
記事: 41
登録日時: 7年前

ハッシュとイテレータ

#1

投稿記事 by SUE » 6年前

件名のまんま、ハッシュでイテレータを取得し使用するときの疑問です。今回ハッシュの実装はboost::unordered_setを使います。

コード:

#include <iostream>
#include <boost/unordered_set.hpp>
using namespace std;
using namespace boost;

int main()
{
	unordered_set< int > hash;
	unordered_set< int >::iterator it;
	hash.rehash( 10 );

	for( int i = 0; i < 10000; ++i ){
		hash.insert( i );
		if( i == 5 ){ it = hash.find( i ); }
	}

	cout << *it;
	hash.erase( it );
	return 0;
}
以上のコードにおいて、ハッシュ表は一旦サイズ10で再ハッシュされています。
そしてループ内で要素数がそれを越えたため、また再ハッシュが行われるはずです。
しかし、2度目の再ハッシュ以前に取得したイテレータitは、その後も使用することができました。これは何故なのでしょう。

ハッシュ表の仕組みに対する理解が足りないのでしょうか。
pop'n music 20 fantasia ポップンクエストPhase MAX Ⅱ ムラクモ/少年は空を辿る【Power Of Nature】

アバター
h2so5
副管理人
記事: 2212
登録日時: 8年前
住所: 東京
連絡を取る:

Re: ハッシュとイテレータ

#2

投稿記事 by h2so5 » 6年前

Unlike C++ TR1 unordered associative containers (which are also hashed containers), the contents of these semi-intrusive containers are not rehashed to maintain a load factor: that would require memory management and intrusive containers don't implement any memory management at all. However, the user can request an explicit rehashing passing a new bucket array. This also offers an additional guarantee over TR1 unordered associative containers: iterators are not invalidated when inserting an element in the container.
http://www.boost.org/doc/libs/1_38_0/do ... tiset.html

boostのドキュメントにはinsertしてもイテレータは無効化されないと書いてあります。
"semi-intrusive" の詳しい実装はよくわかりませんが、イテレータがハッシュ表とは独立して要素へのポインタを持っているのだと思います。

[追記]
一般的なハッシュ表に適用される話ではなく、boostに限った実装です。

アバター
SUE
記事: 41
登録日時: 7年前

Re: ハッシュとイテレータ

#3

投稿記事 by SUE » 6年前

おお…お早い。本当に無効化されない、かつ、自分が勉強不足でないなら独自実装だろうなとは思っていましたが、これは何やらすごいことをしてそうですねw

semi-intrusiveとかその文章からしてbucketごとに動的確保してる訳でもなさそうなので良かったです。もし間違ってたら訂正してください。
回答ありがとうございました。
pop'n music 20 fantasia ポップンクエストPhase MAX Ⅱ ムラクモ/少年は空を辿る【Power Of Nature】

閉鎖

“C言語何でも質問掲示板” へ戻る