Question regarding boost.unordered
Hello list, I have downloaded unordered library from the vault and plan to start using it. However, looking at the documentation, there might be issues that prevent it being useful for me. Could someone please comment on the following: If the user holds a reference (or pointer) to some element in the container (e.g. T const *p = &*it), is that reference guaranteed to remain valid after the insertion/erase of some other elements? I ask because doc says that erasing through an iterator can be O(size) - which seems to suggest that erase can lead to a rehash, invalidating iterators. This appears to contradict the iterator lifetime guarantee posited by the standard (after all, tree based containers don't rebalance after erase, do they?) Another question: any thoughts on whether it is better to use boost::hash for pointers and wstrings, or would a modification of the FNV hash included with unordered give better results? Also, I'm assuming that I can plug this library into boost-1.33.1. Many thanks Amit
Lipik Contact escribió:
Hello list,
[...]
If the user holds a reference (or pointer) to some element in the container (e.g. T const *p = &*it), is that reference guaranteed to remain valid after the insertion/erase of some other elements? I ask because doc says that erasing through an iterator can be O(size) - which seems to suggest that erase can lead to a rehash, invalidating iterators. This appears to contradict the iterator lifetime guarantee posited by the standard (after all, tree based containers don't rebalance after erase, do they?)
For unordered containers, the standard says that insert members shall not affect the validity of references to container elements, but may invalidate all iterators to the container. The erase members shall invalidate only iterators and references to the erased elements. So a pointer to an inserted element remains valid until is erased. An iterator to an inserted object is invalidated after an insertion (because the insertion might have triggered a rehash operation). Erasures only invalidate iterators and pointers/references to erased elements. Regards, Ion
On 03/01/2008, Lipik Contact <contact.lipik@gmail.com> wrote:
Another question: any thoughts on whether it is better to use boost::hash for pointers and wstrings, or would a modification of the FNV hash included with unordered give better results?
It's hard to say. boost::hash makes a good default, and if you then find that the container is slow it might be worth investigating alternatives (using typedefs will make it easier to experiment). I'll be adding some more example hash functions soon which might also be appropriate. But boost::hash should give good results. I don't thing the FNV hash would be appropriate for pointers though.
Also, I'm assuming that I can plug this library into boost-1.33.1.
I think so, although I haven't tested it. Looking in the repository, boost::hash is present, and so is a required fix in boost/detail/allocator_utilities.hpp which I think are the main requirements. You might not be able to run the exception tests against 1.33.1, but the other tests should be runnable if you want to check. Also, I'll be adding the library to trunk soon (hopefully for release in 1.36) and once I've got the unit tests passing on the main compilers will upload a new version to the vault, so look out for that. Daniel
participants (3)
-
Daniel James -
Ion Gaztañaga -
Lipik Contact