Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Storing iterators in associative containers
103 views
Skip to first unread message
Kaba
May 9, 2012, 3:41:10 PM5/9/12
to
Hi,
I find it a reoccurring thing that iterators need to be stored in
associative containers. 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.
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.
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.
What do you think?
Some optional abstract non-sense follows.
Abstractly, iterators are used to refer to parts in a whole. These
parts are stored in data structures with certain performance
guarantees. For example, in std::set the iterator is (usually) to a
tree node which is a part of the tree. These parts are arranged such
that they allow to fulfill the performance requirements of the
standard.
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.
--
http://kaba.hilvi.org
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
I find it a reoccurring thing that iterators need to be stored in
associative containers. 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.
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.
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.
What do you think?
Some optional abstract non-sense follows.
Abstractly, iterators are used to refer to parts in a whole. These
parts are stored in data structures with certain performance
guarantees. For example, in std::set the iterator is (usually) to a
tree node which is a part of the tree. These parts are arranged such
that they allow to fulfill the performance requirements of the
standard.
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.
--
http://kaba.hilvi.org
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Ulrich Eckhardt
May 14, 2012, 2:13:08 PM5/14/12
to
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
> I find it a reoccurring thing that iterators need to be stored in
> associative containers.
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.
> 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.
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.
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.
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
--
Kaba
May 14, 2012, 10:38:16 PM5/14/12
to
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
> Am 09.05.2012 21:41, schrieb Kaba:
> > I find it a reoccurring thing that iterators need to be stored in
> > associative containers.
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?
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.
> 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.
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.
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.
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.
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<c.end(); it++)" for some
> container types. Providing a general operator< for all iterators would
> make this compile generally but not work generally.
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.
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.
Instead, it could be an integer with equivalent behaviour to the memory
address of the node (i.e. simply convert the memory address to an equal-
sized integer). With those changes, I think it could be a practical
idea. It is also a more general technique than providing objects for
comparison and hashing.
> 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.
storage-wise. Referring to what I wrote at the top, the map can
(currently) be used to hold an iterator as a key as long as the iterator
is dereferencable (then the comparison or hashing key is given by
&*iter). The actual problem is to store a "missing iterator" as a key.
--
http://kaba.hilvi.org
Frank Birbacher
May 16, 2012, 8:24:13 PM5/16/12
to
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Hi!
Am 15.05.12 04:38, schrieb Kaba:
says:
The domain of == for forward iterators is that of iterators
over the same underlying sequence.
A default constructed iterator does not have an underlying sequence.
Since you cannot observe in any way that an iterator has a default
constructed way there is no sense in putting it into any container. I
mean the following function cannot be implemented in a conforming way:
template<typename Iter>
bool has_default_constructed_value(Iter && i);
> Yes, the problem with the end-iterator (and the
> default-constructed iterator) is the core of the problem.
Hmm, I can only suggest to use some comparison object that holds the
end-iterator of the underlying container:
template<typename Iter>
bool IterLessComparator::operator() (
Iter const lhs, Iter const rhs
) const
{
// compare end iterator less than any other:
if(rhs == this->end) return false;
if(lhs == this->end) return true;
return &*lhs < &*rhs;
}
Frank
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: keyserver x-hkp://pool.sks-keyservers.net
iEYEARECAAYFAk+z6OIACgkQhAOUmAZhnmpt/QCfd8n6GddQGla0b7dXwA7RExLD
legAnA5/bnbO9ayHiWiYXHAxyvlUBtp3
=+X9B
-----END PGP SIGNATURE-----
--
Hash: SHA1
Hi!
Am 15.05.12 04:38, schrieb Kaba:
> Hmm.. What do you mean by singular? Can't default constructed
> iterators really be copied?
They may be copied, but not used in any == comparison. Clause 24.2.5.2
> iterators really be copied?
says:
The domain of == for forward iterators is that of iterators
over the same underlying sequence.
A default constructed iterator does not have an underlying sequence.
Since you cannot observe in any way that an iterator has a default
constructed way there is no sense in putting it into any container. I
mean the following function cannot be implemented in a conforming way:
template<typename Iter>
bool has_default_constructed_value(Iter && i);
> Yes, the problem with the end-iterator (and the
> default-constructed iterator) is the core of the problem.
end-iterator of the underlying container:
template<typename Iter>
bool IterLessComparator::operator() (
Iter const lhs, Iter const rhs
) const
{
// compare end iterator less than any other:
if(rhs == this->end) return false;
if(lhs == this->end) return true;
return &*lhs < &*rhs;
}
Frank
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: keyserver x-hkp://pool.sks-keyservers.net
iEYEARECAAYFAk+z6OIACgkQhAOUmAZhnmpt/QCfd8n6GddQGla0b7dXwA7RExLD
legAnA5/bnbO9ayHiWiYXHAxyvlUBtp3
=+X9B
-----END PGP SIGNATURE-----
--
Kaba
May 17, 2012, 9:44:38 AM5/17/12
to
Frank Birbacher wrote:
> Am 15.05.12 04:38, schrieb Kaba:
> > Hmm.. What do you mean by singular? Can't default constructed
> > iterators really be copied?
>
> They may be copied, but not used in any == comparison. Clause 24.2.5.2
> says:
>
> The domain of == for forward iterators is that of iterators
> over the same underlying sequence.
>
> A default constructed iterator does not have an underlying sequence.
> Since you cannot observe in any way that an iterator has a default
> constructed way there is no sense in putting it into any container.
Thanks for this. This summarizes the current state that the default-
> Am 15.05.12 04:38, schrieb Kaba:
> > Hmm.. What do you mean by singular? Can't default constructed
> > iterators really be copied?
>
> They may be copied, but not used in any == comparison. Clause 24.2.5.2
> says:
>
> The domain of == for forward iterators is that of iterators
> over the same underlying sequence.
>
> A default constructed iterator does not have an underlying sequence.
> Since you cannot observe in any way that an iterator has a default
> constructed way there is no sense in putting it into any container.
constructed iterator can not be used for anything useful. Of course,
here I am interested in relaxed rules. Something like introducing a
concept of a null iterator, in analog to a null pointer.
> > Yes, the problem with the end-iterator (and the
> > default-constructed iterator) is the core of the problem.
>
> Hmm, I can only suggest to use some comparison object that holds the
> end-iterator of the underlying container:
>
> template<typename Iter>
> bool IterLessComparator::operator() (
> Iter const lhs, Iter const rhs
> ) const
> {
> // compare end iterator less than any other:
> if(rhs == this->end) return false;
> if(lhs == this->end) return true;
> return &*lhs < &*rhs;
> }
unsatisfying. I can imagine a generic algorithm not being able to use
this since it is unable to obtain the end-iterator (if it only works on
iterator ranges). In addition, the problem of hashing still remains:)
--
http://kaba.hilvi.org
Frank Birbacher
May 18, 2012, 8:21:38 PM5/18/12
to
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Hi!
Am 17.05.12 15:44, schrieb Kaba:
Hash: SHA1
Hi!
> That's one workaround for the comparison problem, although a bit
> unsatisfying. I can imagine a generic algorithm not being able to
> use this since it is unable to obtain the end-iterator (if it only
> works on iterator ranges).
I see, while there is a generic nullptr for any type T* there is no
> unsatisfying. I can imagine a generic algorithm not being able to
> use this since it is unable to obtain the end-iterator (if it only
> works on iterator ranges).
way to obtain the end iterator without knowing the container instance.
On the other hand a generic algorithm would require the comparison
object anyway which in turn knows the correct end iterator. You cannot
have the algorithm guess the correct ordering based on the iterator
range alone.
> In addition, the problem of hashing still remains:)
Frank
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: keyserver x-hkp://pool.sks-keyservers.net
sZUAoI6zL7ucS/XtAmcswXMoxjUu2Qxz
=/lzL
-----END PGP SIGNATURE-----
--
Kaba
May 19, 2012, 3:47:28 PM5/19/12
to
Frank Birbacher wrote:
> > In addition, the problem of hashing still remains:)
>
> Well, this can be solved as well using a custom hasher, can't it?
Hmm.. Yes, I guess you are right: Simply return 0 (or any other
> > In addition, the problem of hashing still remains:)
>
> Well, this can be solved as well using a custom hasher, can't it?
constant) for the end-iterator. That wouldn't affect asymptotic
complexity since it is just one special element.
Though if you need to store end-iterators as keys from multiple
containers (admittedly, probably a rare situation), then things go bad
performancewise.
--
http://kaba.hilvi.org
Frank Birbacher
May 22, 2012, 8:23:31 PM5/22/12
to
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Hi!
Am 19.05.12 21:47, schrieb Kaba:
Hash: SHA1
Hi!
> Though if you need to store end-iterators as keys from multiple
> containers (admittedly, probably a rare situation), then things go
> bad performancewise.
Well, you are not allowed to compare iterators from different
> containers (admittedly, probably a rare situation), then things go
> bad performancewise.
containers anyway. For a hash map aka unordered_map the keys must be
equality comparable. This requirement does not hold for iterators
from different containers (in general.) So all keys (=iterators) in a
hash map must be from the same container. This precludes the
possibility to store different end iterators in the same map.
On the other hand you could have custom containers whose iterators are
equality comparable regardless of their container. Then your point
holds: the hash function would either trivially map all end iterators
onto the same hash value and produce collisions or it would accumulate
complexity for each distinct end-iterator. But then you might
discover a way to hash your custom end iterators in a way that takes
constant time just like hashing any other iterator.
HTH,
Frank
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: keyserver x-hkp://pool.sks-keyservers.net
iEYEARECAAYFAk+6un8ACgkQhAOUmAZhnmoNgwCgkkxpkWpLdUx2h5X3qab2jWwi
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.17 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: keyserver x-hkp://pool.sks-keyservers.net
wvMAmwcD3l7EXxJorsrKSYSlRJjNtoYR
=0rTZ
-----END PGP SIGNATURE-----
--
0 new messages