ハッシュとイテレータ

[SUE]

件名のまんま、ハッシュでイテレータを取得し使用するときの疑問です。今回ハッシュの実装は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;
}

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

ハッシュ表の仕組みに対する理解が足りないのでしょうか。

[h2so5]

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]

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

semi-intrusiveとかその文章からしてbucketごとに動的確保してる訳でもなさそうなので良かったです。もし間違ってたら訂正してください。
回答ありがとうございました。