Dangling references?

Discussion in 'C++' started by Matthias Kaeppler, Oct 10, 2005.

  1. 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?
    }
    Matthias Kaeppler, Oct 10, 2005
    #1
    1. Advertising

  2. Matthias Kaeppler wrote:
    > 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
    Victor Bazarov, Oct 10, 2005
    #2
    1. Advertising

  3. Matthias Kaeppler

    Kai-Uwe Bux Guest

    Matthias Kaeppler wrote:

    > 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
    Kai-Uwe Bux, Oct 10, 2005
    #3
  4. Matthias Kaeppler

    Ferdi Smit Guest

    "Victor Bazarov" <> wrote in message
    news:tvy2f.39952$01.us.to.verio.net...

    > 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
    Ferdi Smit, Oct 10, 2005
    #4
  5. Matthias Kaeppler

    Kai-Uwe Bux Guest

    Ferdi Smit wrote:

    > "Victor Bazarov" <> wrote in message
    > news:tvy2f.39952$01.us.to.verio.net...
    >
    >> 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


    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
    Kai-Uwe Bux, Oct 10, 2005
    #5
  6. Matthias Kaeppler

    Ferdi Smit Guest

    On Mon, 10 Oct 2005 17:10:34 -0400, Kai-Uwe Bux wrote:
    > 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.
    Ferdi Smit, Oct 11, 2005
    #6
  7. Matthias Kaeppler

    Greg Guest

    Kai-Uwe Bux wrote:
    > Ferdi Smit wrote:
    >
    > > "Victor Bazarov" <> wrote in message
    > > news:tvy2f.39952$01.us.to.verio.net...
    > >
    > >> 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

    >
    > 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
    Greg, Oct 11, 2005
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. rootz anabo
    Replies:
    0
    Views:
    453
    rootz anabo
    Feb 3, 2005
  2. Hans Van den Eynden

    dangling reference

    Hans Van den Eynden, Oct 16, 2004, in forum: Java
    Replies:
    1
    Views:
    2,848
    Joona I Palaste
    Oct 16, 2004
  3. Tony Johansson

    dangling references?

    Tony Johansson, Apr 6, 2005, in forum: C++
    Replies:
    6
    Views:
    541
    Alf P. Steinbach
    Apr 7, 2005
  4. Richard

    Detecting dangling memory references

    Richard, May 3, 2004, in forum: C Programming
    Replies:
    5
    Views:
    324
    Peter Nilsson
    May 4, 2004
  5. Jarek Blakarz
    Replies:
    2
    Views:
    330
    Jarek Blakarz
    Nov 6, 2012
Loading...

Share This Page