From: kaba@nowhere.com   
      
   Ulrich Eckhardt wrote:   
   > Am 09.05.2012 21:41, schrieb Kaba:   
   > > I find it a reoccurring thing that iterators need to be stored in   
   > > associative containers.   
      
   The title and this sentence are typed incorrectly. I meant that   
   iterators need to be stored as _keys_ in associative container.   
      
   > Interestingly, I have rarely found the need for this. Maybe I never see   
   > such a need because I instinctively either avoid such situations or use   
   > different solutions. Could you give an example?   
      
   It seems to me that for a necessary use-case you need to fulfill the   
   following three conditions:   
      
   1) a ("persistent") object A is stored in some data structure D,   
   referred to by an iterator,   
      
   2) the object A needs to be associated to some data, i.e. there is a   
   need for a unique label for the object (e.g. its memory address) which   
   can then be used as a key in an associative container C, and   
      
   3) the keys of the associative container C are also used to refer to the   
   objects, rather than simply access the associated information (e.g. do   
   something to those objects in D referred to by the keys in C).   
      
   If 3 does not hold, then the object pointer is sufficient (the iterator   
   can always be used to obtain the object pointer).   
      
   But even if these conditions hold, and you necessarily need to use an   
   iterator as a key, then for _dereferencable_ iterators you can use   
   &*iter for comparison or hashing.   
      
   My problem then really comes to the question on how to support   
   "missing" iterators as keys in associative containers. There are two   
   candidates to denote a missing iterator: the end-iterator of the   
   container, or the default-constructed iterator. Neither can currently be   
   used as a key in an associative container.   
      
   > > However, the standard seems to be missing support in this respect.   
   > > Could this be improved? Consider the following:   
   > >   
   > > 1) To store an iterator into an ordered associative container requires   
   > > a way to order the iterators into a sequence (say, for brevity).   
   > >   
   > > 2) To store an iterator into an unordered associative container   
   > > requires a way to compute a hash value for an iterator.   
   >   
   > So the iterator is the key for map-like containers.   
      
   Yes.   
      
   > I think I see where you are getting at. You could of course store a   
   > pointer to the according object instead of the iterator, but that again   
   > precludes the use with the real container that requires the iterator for   
   > certain operations.   
      
   Exactly. If you are only given the pointer, and you need the iterator,   
   then accidental complexity is caused performance- and storage-wise by   
   the need to create a hash map from the pointer to its corresponding   
   iterator. Accidental because the hash map could be avoided altogether by   
   using the iterator instead.   
      
   > > It seems to me that there should be the following additional   
   > > requirements for iterators (or some sub-group of them):   
   > >   
   > >     * an order comparison which allows to use iterators in ordered   
   > >     containers, and   
   > >   
   > >     * a hash computation method which allows to use iterators in   
   > >     unordered containers.   
   > >   
   > > These requirements would include the end-iterator and perhaps also the   
   > > default-constructed iterators.   
   >   
   > Default-constructed iterators are problematic as they are singular,   
   > AFAIK. This in an off itself already creates a few problems with   
   > containers if they require default-constructible objects and general   
   > copiability(sp?). You can default-construct an iterator, but you can't   
   > copy it, I think. Anyway, lets leave this question aside.   
      
   Hmm.. What do you mean by singular? Can't default constructed iterators   
   really be copied?   
      
   I haven't thought the default-constructed iterators through completely.   
   In my red-black tree implementation a default-constructed iterator   
   refers to a null pointer to a node. Presumably that would be the case   
   with many other data structures too. The null-pointer is as hashable or   
   orderable as other values, so it makes sense to me to allow it as a   
   "first-class citizen" in this respect. The advantage of the default-   
   constructed iterator over the end-iterator to denote a "missing"   
   iterator is that it does not require a container to obtain it.   
      
   The requirement for a default-constructed iterator, with respect to   
   hashing an ordering could be that it should always be ordered, or   
   hashed, the same, no matter when it is compared to. In addition, it   
   should not match in order any other iterator (expect other default-   
   constructed ones). For example, the null-pointer approach above would   
   fulfill these requirements.   
      
   > Just for the record, there are also pure input and output iterators,   
   > like those working on streams, but I gues that's irrelevant to your   
   > considerations.   
      
   Yes, I am only interested in iterators which dereference to an object   
   with a "persistent" memory address. Iterators to std::vector are also ok   
   as long as they don't invalidate.   
      
   > Concerning the rest, I do agree that there is room for improvement. You   
   > could impose an ordering via the address of the pointee, either by   
   > sorting the addresses or hashing them. However, I don't think there is a   
   > way to get at the address of an object without causing UB on a   
   > past-the-end iterator, although the address of a past-the-end element   
   > can usually be obtained.   
      
   Yes, the problem with the end-iterator (and the default-constructed   
   iterator) is the core of the problem.   
      
   > There is a danger with blindly providing ordering though. The problem is   
   > that you can still write "for(it=c.begin(); it container types. Providing a general operator< for all iterators would   
   > make this compile generally but not work generally.   
      
   Agreed. The problem is that the comparison operators could be confused   
   to describe the ordering induced by ++ and --. To avoid this, the   
   ordering could be given by a predicate object instead.   
      
   > If the iterator   
   > interface only provided a way to get at an address (this address would   
   > only be dereferencable if the iterator was dereferencable), you could   
   > construct all you need on top of it, which would be much safer.   
      
   This is a nice idea; let's refine it a bit.   
      
   The question is: which address? The data structure can not return an   
   address to an object, since an object does not exist for the end-   
   iterator (or a default-constructed iterator). To be useful, it should   
   "return" the memory address of the referred-to part (e.g. a node in a   
   tree). Clearly, the type of the returned thing should not be a pointer   
   at all, since you want to protect the internals from being exposed.   
      
   [continued in next message]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)