g++ unordered_map iterator/pointer invalidation policy
Hello,
I have a question about unordered_map implementation in g++, and I am hoping someone can answer it:
What is the iterator/pointer invalidation policy (upon inserting) for the unordered_map implementation of g++ (4.2)? According to the TR1 draft, invalidation of iterators, not pointers, is allowed (since rehashing can occur).
However, I found this out just recently, and until then I was silently assuming iterators dont get invalidated, and my code is working fine. However, I would like to know how thin that ice I am skating on is. Does anybody know of an unordered_map (or similiar interface) implementation that does neither invalidate iterators nor pointers?
Any help is appreciated!
-Julius
I have a question about unordered_map implementation in g++, and I am hoping someone can answer it:
What is the iterator/pointer invalidation policy (upon inserting) for the unordered_map implementation of g++ (4.2)? According to the TR1 draft, invalidation of iterators, not pointers, is allowed (since rehashing can occur).
However, I found this out just recently, and until then I was silently assuming iterators dont get invalidated, and my code is working fine. However, I would like to know how thin that ice I am skating on is. Does anybody know of an unordered_map (or similiar interface) implementation that does neither invalidate iterators nor pointers?
Any help is appreciated!
-Julius
It is never safe to assume iterators are still valid after you modify a container. Just because it works now doesn't mean it will work some other time... Sorry.
Hello Duoas,
that is not true, it depends on your container model. std::list<T>, e.g., guarantees iterator validity after most operations (including insertion). Same applied to the hash_map implementation from g++, that know appears obsoleted (due to the TR1 almost-standard). Nobody here with some insight into g++'s TR1 implementation? Am I right to assume unordered_map is implemented with hash_map?
Thanks,
-Julius
that is not true, it depends on your container model. std::list<T>, e.g., guarantees iterator validity after most operations (including insertion). Same applied to the hash_map implementation from g++, that know appears obsoleted (due to the TR1 almost-standard). Nobody here with some insight into g++'s TR1 implementation? Am I right to assume unordered_map is implemented with hash_map?
Thanks,
-Julius
Iterators and references to the erased elements are invalidated, as per
23.2.2.3.
Never assume anything about iterators. If you are using a container like 'list 'and you can guarantee in your code that your iterator is not damaged by erase() or some other operation, then sure, it is fine. But making that guarantee is harder than you'd think in non-trivial cases.
You are, however, guaranteed that pointers to elements remain valid no matter what you do.
TR1 unordered_map is a hash table... so yes.
Hope this helps.
23.2.2.3.
Never assume anything about iterators. If you are using a container like 'list 'and you can guarantee in your code that your iterator is not damaged by erase() or some other operation, then sure, it is fine. But making that guarantee is harder than you'd think in non-trivial cases.
You are, however, guaranteed that pointers to elements remain valid no matter what you do.
TR1 unordered_map is a hash table... so yes.
Hope this helps.
Topic archived. No new replies allowed.