Dangling references?

[Matthias Kaeppler]

Hi,

I have a question regarding references, and their chance to "dangle" (if
that's possible at all):

Say I have a collection ob objects, and I take a reference to one of
them. Now I sort this collection, or invoke whatever action it takes to
copy around the elements in the collection.
What happens to the reference?

Example:

class A {};

int main()
{
list<A> coll;
// ... add elements to coll

A &ref = *(coll.begin());
coll.sort(); // assume that referenced element gets copied around

// at this point, is 'ref' dangling or is it still valid?
}

 

[Victor Bazarov]

I have a question regarding references, and their chance to "dangle" (if
that's possible at all):

It is entirely possible.

int *pint = new int(42);
int &r = *pint; // r is now a reference to a dynamic object of type int
delete pint;
// r is now "dangling"

I can set 'pint' to 0 to indicate that it's not pointing to anything, but
there is no way to do this with 'r'.

Say I have a collection ob objects, and I take a reference to one of
them. Now I sort this collection, or invoke whatever action it takes to
copy around the elements in the collection.
What happens to the reference?

It depends on the collection and what is done to the elements when they
are sorted.

Example:

class A {};

int main()
{
list<A> coll;
// ... add elements to coll

A &ref = *(coll.begin());
coll.sort(); // assume that referenced element gets copied around

// at this point, is 'ref' dangling or is it still valid?
}

The Standard actually doesn't specify _how_ elements' values are exchanged
but I'll venture a guess that 'swap' is used. And the Standard requires
that 'swap' does not invalidate references. YMMV, of course. I'd ask in
comp.std.c++ for clarification, they know legalese and can explain why the
Standard is so vague re sorting of a list.

V

 

[Kai-Uwe Bux]

Hi,

I have a question regarding references, and their chance to "dangle" (if
that's possible at all):

Say I have a collection ob objects, and I take a reference to one of
them. Now I sort this collection, or invoke whatever action it takes to
copy around the elements in the collection.
What happens to the reference?

Example:

class A {};

int main()
{
list<A> coll;
// ... add elements to coll

A &ref = *(coll.begin());
coll.sort(); // assume that referenced element gets copied around

a) Iterators remain valid. The standard is silent about references [I
think].

b) However, depending on how the sorting is done, you may or may not find
the smallest element. You should not assume that the values of the list
elements change. The list container is somewhat special in that the
standard allows for sort to just rearrange the pointers without actually
shuffling the nodes around:

#include <list>
#include <iostream>
#include <cstdlib>

int main() {
std::list<unsigned long> coll;
for ( unsigned long i = 0; i < 10; ++i ) {
coll.push_front( i );
}

std::list< unsigned long >::iterator iter = coll.begin();
std::cout << "reference value: " << *iter << '\n';
coll.sort();
std::cout << "reference value: " << *iter << '\n';
std::cout << "lowest value: " << *(coll.begin()) << '\n';
}


prints on my machine:

reference value: 9
reference value: 9
lowest value: 0

If you use a reference instead of an iterator, I would expect the result to
be the same.


Best

Kai-Uwe Bux

 

[Ferdi Smit]

The Standard actually doesn't specify _how_ elements' values are exchanged
but I'll venture a guess that 'swap' is used. And the Standard requires
that 'swap' does not invalidate references. YMMV, of course. I'd ask in
comp.std.c++ for clarification, they know legalese and can explain why the
Standard is so vague re sorting of a list.

Nothing is said about invalidating iterators (but also not of not
invalidating them). For other items, such as splice or erase, iterator
invalidation is explicitly mentioned, so the converse would be implicit?
Therefore I think you ought to be able to assume the iterator still points
to the beginning of the list, and so the reference is also still valid (but
possibly refering to a different actual item). But indeed it is rather
vague... tho it implies that when iterators are not invalidated the sort
must be done in-place, which is a good space requirement.

Ferdi

 

[Kai-Uwe Bux]

Nothing is said about invalidating iterators (but also not of not
invalidating them). For other items, such as splice or erase, iterator
invalidation is explicitly mentioned, so the converse would be implicit?
Therefore I think you ought to be able to assume the iterator still points
to the beginning of the list, and so the reference is also still valid
(but possibly refering to a different actual item). But indeed it is
rather vague... tho it implies that when iterators are not invalidated the
sort must be done in-place, which is a good space requirement.

Ferdi

From 23.1/11:

Unless otherwise specified (either explicitly or by defining a function in
terms of other functions), invoking a container member function or passing
a container as an argument to a library function shall not invalidate
iterators to, or change the values of, objects within that container.


So, yes, it is implicit. However, there is a little catch. If you say

typedef std::list<T> T_List;
T_list the_list;
// fill the list
...
T_list::const_iterator front_iter = the_list.begin();
the_list.sort();
assert( front_iter == the_list.begin() );

you may find that the assertion fails: the iterator is not invalidated, but
that the_list.begin() returns a different value now. The member function
the_list.sort() is allowed to just redirect pointers and not shuffle around
the actual data.


Best

Kai-Uwe Bux

 

[Ferdi Smit]

From 23.1/11:

Unless otherwise specified (either explicitly or by defining a function in
terms of other functions), invoking a container member function or passing
a container as an argument to a library function shall not invalidate
iterators to, or change the values of, objects within that container.


So, yes, it is implicit. However, there is a little catch. If you say

typedef std::list<T> T_List;
T_list the_list;
// fill the list
...
T_list::const_iterator front_iter = the_list.begin();
the_list.sort();
assert( front_iter == the_list.begin() );

you may find that the assertion fails: the iterator is not invalidated, but
that the_list.begin() returns a different value now. The member function
the_list.sort() is allowed to just redirect pointers and not shuffle around
the actual data.

Ok, I missed that issue; you're right of course. But considering this,
what does it actually mean when iterators are not invalidated when they
can a) point to any item in b) any location in the list. Ie. they are as
good as random. The only guarantee is them pointing in the list... not
very useful.

 

[Greg]

From 23.1/11:

Unless otherwise specified (either explicitly or by defining a function in
terms of other functions), invoking a container member function or passing
a container as an argument to a library function shall not invalidate
iterators to, or change the values of, objects within that container.


So, yes, it is implicit. However, there is a little catch. If you say

typedef std::list<T> T_List;
T_list the_list;
// fill the list
...
T_list::const_iterator front_iter = the_list.begin();
the_list.sort();
assert( front_iter == the_list.begin() );

you may find that the assertion fails: the iterator is not invalidated, but
that the_list.begin() returns a different value now. The member function
the_list.sort() is allowed to just redirect pointers and not shuffle around
the actual data.

The important point about list::sort is that front_iter (and every
other iterator in list) will still reference the same element in
the_list after the list has been sorted - even though that element's
position in the the_list may have changed. As a consequence, any code
in possession of an iterator in the_list will not suddenly find
themselves with an iterator to some other element just because the
the_list has been sorted. In other words, calling list::sort
invalidates none of the the_list's iterators, it invalidates only
properties of the_list itself. std::sort on the other hand provides the
opposite behavior: it invalidates the iterators it sorts while
preserving the properties of their container.

If

assert( front_iter == the_list.begin() );

really has to be true after the_list has been sorted, than std::sort()
and not list::sort() should be called to sort the_list - although it's
hard to imagine the circumstances in which this assertion would make
sense. Since one of the primary advantages of std::list is the
constancy of its iterators, calling list::sort() instead of std::sort()
is usually the right way to sort std::list elements.

Greg