From: kaba@nowhere.com   
      
   25.7.2012 4:07, Nevin ":-]" Liber wrote:   
      
   >> In the new data structure you use existing data structures to refer   
   >> to each other in useful ways. Therefore, when you create a part,   
   >> you are not just creating it to be stored and later be traversed as   
   >> part of a sequence (say). Rather, you are creating it to be   
   >> referred to _directly_ (giving you strict constant-time access and   
   >> direct identification for, say, removal).   
   >   
   > Except for list (which is node based), this gets dangerous, as   
   > iterators can be invalidated at the drop of a hat.   
      
   Iterators are not invalidated at the drop of a hat. A data structure   
   specifies rules by which they are invalidated (as the C++ standard   
   also does for its containers). For example, if in a graph data   
   structure I remove a vertex, then also all the edges incident to it   
   are removed.  Then the iterator to the vertex, and the iterators to   
   incident edges are all invalidated. But this isn't a problem;   
   actually, it is the only sensible action. Additionally, this is not   
   about iterators at all: it is about the removal of parts from a data   
   structure. What is removed can not be referred to again, no matter   
   what the technique of referring-to is.   
      
   Out of the STL containers, std::list, std::forward_list, std::set, and   
   std::map are safe in their iterator invalidation. They invalidate only   
   what necessarily needs to be invalidated (e.g. an iterator to the   
   removed element). A graph data structure built using these primitives   
   has the same property.   
      
   The unordered containers need a bit more attention because of their   
   iterator invalidation. The contained parts (the elements, the   
   references) are never invalidated until removal. Here I am unsure what   
   the iterator invalidation actually means in the C++ standard. If I   
   take an iterator to an unordered container before rehashing, can I   
   still dereference it after rehashing (and also get the same element)?   
   If yes, then the unordered containers too are to be included in the   
   basic building blocks of data structures. If no, then the unordered   
   containers are dangerous as you say, since the stored iterators in the   
   data structure can not be used after a rehash.   
      
   Since I have implemented the unordered containers fully, I know that   
   for a chaining-based implementation the answer is naturally yes. But,   
   of course, that does not help much: you need the standard to get   
   portable programs.   
      
   --   
   http://kaba.hilvi.org   
      
      
         [ See http://www.gotw.ca/resources/clcm.htm for info about ]   
         [ comp.lang.c++.moderated.    First time posters: Do this! ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)