[boost] Re: N1456 Hash table implementation

From: Dan W. (danw_at_[hidden])
Date: 2004-01-02 20:29:36

Sorry, I did not see the words "during a rehashing operation".

BTW, are iterators implemented as pointers? Will they be invalidated by 
rehashing? SGI's doc "HashedAssociativeContiners.html" contains...

................................................
Models

     * hash_set
     * hash_map
     * hash_multiset
     * hash_multimap

Notes

[1] There is an extensive literature dealing with hash tables. See, for 
example, section 6.4 of Knuth. (D. E. Knuth, The Art of Computer 
Programming. Volume 3: Sorting and Searching. Addison-Wesley, 1975.)

[2] If the hash function is poor (that is, if many different keys hash 
to the same value) then this will hurt performance. The worst case is 
where every key hashes to the same value; in this case, run-time 
complexity of most Hashed Associative Container operations will be 
linear in the size of the container.

[3] Resizing does not invalidate iterators; however, it does not 
necessarily preserve the ordering relation between iterators. That is, 
if i and j are iterators that point into a Hashed Associative Container 
such that i comes immediately before j, then there is no guarantee that 
i will still come immediately before j after the container is resized. 
The only guarantee about about the ordering of elements is the 
contiguous storage invariant: elements with the same key are always 
adjacent to each other.
..................................................

...where the last point says that iterators are not invalidated. Will 
this hold true?, or is it just SGI's guarantee?

dan