Strange behaviors of Iterator for set

Discussion in 'C++' started by Bo Yang, Nov 19, 2008.

  1. Bo Yang

    Bo Yang Guest

    Hi,
    Today, I make some test on the C++ STL iterators of set containers
    with GNU g++ compiler. The code is:

    #include <set>
    #include <iostream>

    using namespace std;

    int main(int argc, char **argv)
    {
    set<int> ms;
    int i;
    for (i=1; i<10; i++)
    ms.insert(i);

    set<int>::iterator it = ms.begin();
    it++;

    ms.erase(it);
    cout << "Deleted: " << *(it) << endl;
    set<int>::iterator ii = it;
    cout << "++: " << *(++ii) << endl;
    cout << "+2: " << *(++ii) << endl;
    cout << "--: " << *(--it) << endl;
    it++;
    cout << "--++: " << *(it) << endl;

    ms.insert(2);
    it = ms.begin();
    it++;
    it++;
    it++;
    it++;

    ms.erase(it);
    cout << "Deleted: " << *(it) << endl;
    ii = it;
    cout << "++: " << *(++ii) << endl;
    cout << "+2: " << *(++ii) << endl;
    cout << "--: " << *(--it) << endl;
    it++;
    cout << "--++: " << *(it) << endl;

    it = ms.end();
    it--;
    ms.erase(it);
    cout << "Deelted: " << *(it) << endl;
    cout << "++: " << *(++it) << endl;
    cout << "+2: " << *(++it) << endl;

    return 0;
    }

    and the output is:
    Deleted: 2
    ++: 1
    +2: 3
    --: 1
    --++: 3
    Deleted: 5
    ++: 6
    +2: 7
    --: 6
    --++: 7
    Deelted: 9
    ++: 8
    +2: 7

    I find that, when I erase something, the whole iterator's behavior is
    unpredicted. I can't make sure what is a next ++ is in a set unlike I
    am sure with a vector...
    Does this a right behaviors? And when I use the remove_if and many
    other algorithm on set, it will make some crash, why?

    Thanks a lot!

    Regards!
    Bo
     
    Bo Yang, Nov 19, 2008
    #1
    1. Advertising

  2. Bo Yang

    James Kanze Guest

    On Nov 19, 3:35 am, "Victor Bazarov" <> wrote:
    > Bo Yang wrote:


    [...]
    > > ms.erase(it);


    This action invalidates "it".

    > > cout << "Deleted: " << *(it) << endl;


    > Undefined behaviour. You're trying to dereference an invalid
    > iterator.


    > > set<int>::iterator ii = it;


    > You're constructing another iterator and initialising it from
    > the invalid iterator; the 'ii' becomes invalid immediately.


    Actually, I think this statement is also undefined behavior,
    even if you never use ii later. The concept of iterators is
    designed so that a pointer into an array is an iterator, and
    just copying an invalid pointer is undefined behavior, so
    presumably the same holds for iterators.

    > > And when I use the remove_if and many other algorithm on
    > > set, it will make some crash, why?


    > Don't know. Show the code, then we can talk.


    It shouldn't compile, if your library implementation and
    compiler are conformant. You can't modify members of a set,
    which means that none of the mutating algorithms can be used on
    it. remove_if is a mutating algorithm.

    Note that historically, there was some discussion about this,
    and many early implementations of std::set allowed mutating its
    members, as long as the mutations didn't affect the
    ordering---if they did, it was undefined behavior. (The
    mutations done by remove_if will definitely affect the
    ordering.) It's highly likely that some implementations
    continue with this policy, despite the standard, in order to
    avoid breaking existing code. The behavior he describes would
    seem to correspond to the behavior of such an implementation; a
    core dump is certainly one possibility of undefined behavior.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Nov 19, 2008
    #2
    1. Advertising

  3. Bo Yang

    Brian Luk Guest

    What'z up Bo?
     
    Brian Luk, Nov 19, 2008
    #3
  4. Bo Yang

    Bo Yang Guest

    On Nov 20, 12:25 am, Pete Becker <> wrote:
    > On 2008-11-19 09:22:25 -0500, Victor Bazarov <> said:
    >
    >
    >
    > > James Kanze wrote:
    > >> On Nov 19, 3:35 am, "Victor Bazarov" <> wrote:
    > >>> Bo Yang wrote:

    >
    > >>     [...]
    > >>>> And when I use the remove_if and many other algorithm on
    > >>>> set, it will make some crash, why?

    >
    > >>> Don't know.  Show the code, then we can talk.

    >
    > >> It shouldn't compile, if your library implementation and
    > >> compiler are conformant.  You can't modify members of a set,
    > >> which means that none of the mutating algorithms can be used on
    > >> it.  remove_if is a mutating algorithm.

    >
    > > It's mutating to the sequence, not to the elements.  Removing from a
    > > set is well-defined and it keeps the set in stable state, doesn't it?

    >
    > remove_if, like all the standalone algorithms, operates on the elements
    > of a sequence and not on the underlying data structure. That's the
    > essential abstraction that iterators present. Think of how remove_if
    > would work on a vector: copy elements downward, but don't copy elements
    > that should be removed.
    >
    > The key thing here is that algorithms operate on sequences, not on
    > containers. Containers are a way of producing sequences, but algorithms
    > don't know where the sequence came from, so cannot apply operations
    > like removing an element from a set. And that's why list has its own
    > sort member function: the generic sort algorithm doesn't work for a
    > list, so you need a container-specific sort function.


    Ah, that is a good point. If STL algorithms operate on sequences, I
    understand why my program failing. Thanks!

    Regards!
    Bo
     
    Bo Yang, Nov 20, 2008
    #4
  5. Bo Yang

    Bo Yang Guest

    On Nov 19, 5:24 pm, James Kanze <> wrote:
    > On Nov 19, 3:35 am, "Victor Bazarov" <> wrote:
    >
    > > Bo Yang wrote:

    >
    >     [...]
    >
    > > >  ms.erase(it);

    >
    > This action invalidates "it".
    >
    > > >  cout << "Deleted: " << *(it) << endl;

    > > Undefined behaviour.  You're trying to dereference an invalid
    > > iterator.
    > > >  set<int>::iterator ii = it;

    > > You're constructing another iterator and initialising it from
    > > the invalid iterator; the 'ii' becomes invalid immediately.

    >
    > Actually, I think this statement is also undefined behavior,
    > even if you never use ii later.  The concept of iterators is
    > designed so that a pointer into an array is an iterator, and
    > just copying an invalid pointer is undefined behavior, so
    > presumably the same holds for iterators.
    >
    > > > And when I use the remove_if and many other algorithm on
    > > > set, it will make some crash, why?

    > > Don't know.  Show the code, then we can talk.

    >
    > It shouldn't compile, if your library implementation and
    > compiler are conformant.  You can't modify members of a set,
    > which means that none of the mutating algorithms can be used on
    > it.  remove_if is a mutating algorithm.
    >
    > Note that historically, there was some discussion about this,
    > and many early implementations of std::set allowed mutating its
    > members, as long as the mutations didn't affect the
    > ordering---if they did, it was undefined behavior.  (The
    > mutations done by remove_if will definitely affect the
    > ordering.)  It's highly likely that some implementations
    > continue with this policy, despite the standard, in order to
    > avoid breaking existing code.  The behavior he describes would
    > seem to correspond to the behavior of such an implementation; a
    > core dump is certainly one possibility of undefined behavior.


    Do you mean all associative containers such as set/multiset/map/
    multimap can't be dealt with mutating algorithms? And that is to say
    that only vector/list/deque can be applied by this algorithm? Thanks!

    Regards!
    Bo
     
    Bo Yang, Nov 20, 2008
    #5
  6. Bo Yang

    James Kanze Guest

    On Nov 19, 3:22 pm, Victor Bazarov <> wrote:
    > James Kanze wrote:
    > > On Nov 19, 3:35 am, "Victor Bazarov" <> wrote:
    > >> Bo Yang wrote:


    > > [...]
    > >>> And when I use the remove_if and many other algorithm on
    > >>> set, it will make some crash, why?


    > >> Don't know. Show the code, then we can talk.


    > > It shouldn't compile, if your library implementation and
    > > compiler are conformant. You can't modify members of a set,
    > > which means that none of the mutating algorithms can be used
    > > on it. remove_if is a mutating algorithm.


    > It's mutating to the sequence, not to the elements. Removing
    > from a set is well-defined and it keeps the set in stable
    > state, doesn't it?


    Removing elements from a set is well defined, but the standard
    library changes the meanings of some common English words, so
    remove (and remove_if) don't mean remove (which is spelled erase
    in the standard), but reorder. And any attempt to reorder a set
    is going to cause problems somewhere, because in the standard,
    set doesn't mean set, but is a list ordered on some specified
    criterion.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Nov 20, 2008
    #6
  7. Bo Yang

    James Kanze Guest

    On Nov 20, 2:25 am, Bo Yang <> wrote:
    > On Nov 19, 5:24 pm, James Kanze <> wrote:
    > > On Nov 19, 3:35 am, "Victor Bazarov" <> wrote:


    [...]
    > Do you mean all associative containers such as
    > set/multiset/map/ multimap can't be dealt with mutating
    > algorithms?


    No. It is only the key_type which can't be mutated. In set and
    multiset, the key_type is the entire element, but in map and
    multimap, it's only part of the element. (Internally, the
    associative containers maintain their elements ordered on the
    key_type; if you mutate the key_type, you can violate the
    invariants maintaining the ordering.)

    Of course, remove_if reassigns the entire element, so it can't
    be used on any of the associative containers. (From a quick
    glance, I think that this is true for all of the mutating
    algorithms. But you could write an algorithm of your own for
    std::map which only mutated the mapped_type.)

    > And that is to say that only vector/list/deque can be applied
    > by this algorithm?


    Or any container of your own which allows mutation of a complete
    element through an iterator.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Nov 20, 2008
    #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. Sylvain Munaut
    Replies:
    2
    Views:
    2,216
    Sylvain Munaut
    Dec 22, 2004
  2. VB Programmer
    Replies:
    3
    Views:
    379
    William F. Robertson, Jr.
    Jul 1, 2003
  3. Scupper

    DHTML Behaviors and ASP.NET

    Scupper, May 28, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    477
    Vidar Petursson
    May 28, 2004
  4. Li Chen
    Replies:
    5
    Views:
    104
    Patrick Doyle
    Sep 12, 2008
  5. Mark Kremers

    Behaviors in Behaviors

    Mark Kremers, Jul 31, 2003, in forum: Javascript
    Replies:
    0
    Views:
    125
    Mark Kremers
    Jul 31, 2003
Loading...

Share This Page