
Boost : 
From: Dan W. (danw_at_[hidden])
Date: 20040102 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. AddisonWesley, 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, runtime
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk