Am 09.05.2012 21:41, schrieb Kaba:
> I find it a reoccurring thing that iterators need to be stored in
> associative containers.

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?


> 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.


> However, storing iterators generically in associative containers is a
> bit problematic because there is no generic way to do either of the
> above. In all current cases (std::set, std::map, multi-such,
> unordered- such) one can use the address of the dereferenced element
> as a sorting value, or a hash value, as in
>
> &*iter
>
> This is of course assuming that there is an underlying 'persistent'
> object, so that the address does not change. That happens to be true
> in the listed cases.
>
> Generically this is not a satisfying solution. In addition, this is
> undefined behaviour, as far as I know, when 'iter' is an end-iterator
> of a container. But end-iterators are useful in exactly the same sense
> as null pointers are. It should be possible to use them as keys in
> associative containers. Perhaps the same should be said of default-
> constructed iterators.

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.


> 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.

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.

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.

There is a danger with blindly providing ordering though. The problem is
that you can still write "for(it=c.begin(); it<c.end(); it++)" for some
container types. Providing a general operator< for all iterators would
make this compile generally but not work generally. 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.


> Creating a layered data structure from more primitive data structures
> means that a part in one data structure needs to be able to refer to
> another part in another data structure. In many cases this means that
> a part simply stores, without need for association, an iterator or
> iterators to the other parts. But not all data can or should be stored
> in the parts themselves, in particular because the data might only be
> of temporal interest. Therefore, what is often needed is a fast
> association from an iterator to some other data. This requires using
> an iterator as a key in an associative container.

I see, the temporary data would have been e.g. a reference to the parent
vertex in a depth-first search, which is not part of the graph but of
the DFS. You can work around this by storing additional data in a
map<vertex*, data>. If you really need the iterator, you could store it
as part of "data", too.


Greetings!

Uli


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]