erase vs. erase

Discussion in 'C++' started by al.cpwn@gmail.com, Mar 25, 2006.

  1. Guest

    Is there a reason why erase for vector returns an iterator but erase
    for set doesn't? Is this something we should keep in mind while
    designing our own containers (like binary tree for example)?
     
    , Mar 25, 2006
    #1
    1. Advertising

  2. Mark P Guest

    wrote:
    > Is there a reason why erase for vector returns an iterator but erase
    > for set doesn't? Is this something we should keep in mind while
    > designing our own containers (like binary tree for example)?
    >


    My guess is that this is because in the vector case, the call to erase
    will invalidate all iterators at or beyond the location of the erasure.
    Thus it's useful to return a new iterator to the location after the
    erasure.

    For a set, only iterators pointing to the location of the erasure are
    invalidated, so this is easier to deal with manually. For example,
    mySet.erase(myIter++); will result in myIter pointing to the location
    after the erasure.

    Mark
     
    Mark P, Mar 25, 2006
    #2
    1. Advertising

  3. Rolf Magnus Guest

    Mark P wrote:

    > wrote:
    >> Is there a reason why erase for vector returns an iterator but erase
    >> for set doesn't? Is this something we should keep in mind while
    >> designing our own containers (like binary tree for example)?
    >>

    >
    > My guess is that this is because in the vector case, the call to erase
    > will invalidate all iterators at or beyond the location of the erasure.
    > Thus it's useful to return a new iterator to the location after the
    > erasure.
    >
    > For a set, only iterators pointing to the location of the erasure are
    > invalidated, so this is easier to deal with manually. For example,
    > mySet.erase(myIter++); will result in myIter pointing to the location
    > after the erasure.


    However, they could still have let set's erase return an iterator too, for
    the sake of constistency.
     
    Rolf Magnus, Mar 26, 2006
    #3
  4. In message <e06439$m7a$00$-online.com>, Rolf Magnus
    <> writes
    >Mark P wrote:
    >
    >> wrote:
    >>> Is there a reason why erase for vector returns an iterator but erase
    >>> for set doesn't? Is this something we should keep in mind while
    >>> designing our own containers (like binary tree for example)?
    >>>

    >>
    >> My guess is that this is because in the vector case, the call to erase
    >> will invalidate all iterators at or beyond the location of the erasure.
    >> Thus it's useful to return a new iterator to the location after the
    >> erasure.
    >>
    >> For a set, only iterators pointing to the location of the erasure are
    >> invalidated, so this is easier to deal with manually. For example,
    >> mySet.erase(myIter++); will result in myIter pointing to the location
    >> after the erasure.

    >
    >However, they could still have let set's erase return an iterator too, for
    >the sake of constistency.


    But incrementing set::iterator may be costly, since it involves some
    O(log(N)) tree navigation. Why pay for something you don't need?

    --
    Richard Herring
     
    Richard Herring, Mar 29, 2006
    #4
  5. red floyd Guest

    Richard Herring wrote:
    > In message <e06439$m7a$00$-online.com>, Rolf Magnus
    > <> writes
    >> However, they could still have let set's erase return an iterator too,
    >> for
    >> the sake of constistency.

    >
    > But incrementing set::iterator may be costly, since it involves some
    > O(log(N)) tree navigation. Why pay for something you don't need?
    >


    I don't know... That's an implementation issue. I could see an
    implementation that trades space in the set node for constant time
    incrementing. E.g. set searches are O(log n), and iteration is O(1) for
    each ++ operatation (each node knows its predecessor and successor --
    implemented as a linked list). Inserts and deletes would be a tad more
    expensive (though still O(logN)).

    I'm not saying that it *should* be done, I'm simply saying that I could
    see *how* it could be done.
     
    red floyd, Mar 29, 2006
    #5
  6. Pete Becker Guest

    red floyd wrote:
    > Richard Herring wrote:
    >
    >> In message <e06439$m7a$00$-online.com>, Rolf Magnus
    >> <> writes
    >>
    >>> However, they could still have let set's erase return an iterator
    >>> too, for
    >>> the sake of constistency.

    >>
    >>
    >> But incrementing set::iterator may be costly, since it involves some
    >> O(log(N)) tree navigation. Why pay for something you don't need?
    >>

    >
    > I don't know... That's an implementation issue. I could see an
    > implementation that trades space in the set node for constant time
    > incrementing. E.g. set searches are O(log n), and iteration is O(1) for
    > each ++ operatation (each node knows its predecessor and successor --
    > implemented as a linked list). Inserts and deletes would be a tad more
    > expensive (though still O(logN)).
    >
    > I'm not saying that it *should* be done, I'm simply saying that I could
    > see *how* it could be done.


    erase has to look at adjacent nodes in order to stitch the tree back
    together, and possibly rebalance it. Returning the next iterator is
    usually trivial, because you already have it.

    --

    Pete Becker
    Roundhouse Consulting, Ltd.
     
    Pete Becker, Mar 29, 2006
    #6
  7. In message <>, Pete Becker
    <> writes
    >red floyd wrote:
    >> Richard Herring wrote:
    >>
    >>> In message <e06439$m7a$00$-online.com>, Rolf Magnus
    >>><> writes
    >>>
    >>>> However, they could still have let set's erase return an iterator
    >>>>too, for
    >>>> the sake of constistency.
    >>>
    >>>
    >>> But incrementing set::iterator may be costly, since it involves some
    >>>O(log(N)) tree navigation. Why pay for something you don't need?
    >>>

    >> I don't know... That's an implementation issue. I could see an
    >>implementation that trades space in the set node for constant time
    >>incrementing. E.g. set searches are O(log n), and iteration is O(1)
    >>for each ++ operatation (each node knows its predecessor and successor
    >>-- implemented as a linked list). Inserts and deletes would be a tad
    >>more expensive (though still O(logN)).
    >> I'm not saying that it *should* be done, I'm simply saying that I
    >>could see *how* it could be done.

    >
    >erase has to look at adjacent nodes in order to stitch the tree back
    >together, and possibly rebalance it. Returning the next iterator is
    >usually trivial, because you already have it.


    Then I'm wrong about the cost. So why _doesn't_ set::erase return the
    next iterator?
    >


    --
    Richard Herring
     
    Richard Herring, Mar 30, 2006
    #7
  8. Pete Becker Guest

    Richard Herring wrote:
    >
    > So why _doesn't_ set::erase return the
    > next iterator?
    >


    It will. <g>

    As to the reason, best guess is that it's not strictly needed in user
    code, because if someone needs it, they can get it beforehand. So
    frugality kept it out. In this case, I think the frugality, while
    well-intentioned, was misplaced. Dinkumware's implementation has always
    provided it.

    --

    Pete Becker
    Roundhouse Consulting, Ltd.
     
    Pete Becker, Mar 30, 2006
    #8
    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. tom_usenet
    Replies:
    1
    Views:
    368
    Corno
    Jul 5, 2003
  2. Robert Sturzenegger

    How to erase node from deque?

    Robert Sturzenegger, Jul 28, 2003, in forum: C++
    Replies:
    0
    Views:
    327
    Robert Sturzenegger
    Jul 28, 2003
  3. John Harrison

    Re: STL insert/erase behaviour

    John Harrison, Aug 13, 2003, in forum: C++
    Replies:
    0
    Views:
    650
    John Harrison
    Aug 13, 2003
  4. Andrew Koenig

    Re: STL insert/erase behaviour

    Andrew Koenig, Aug 13, 2003, in forum: C++
    Replies:
    0
    Views:
    392
    Andrew Koenig
    Aug 13, 2003
  5. Paras

    stl list erase

    Paras, Aug 20, 2003, in forum: C++
    Replies:
    13
    Views:
    3,836
    Alan Chen
    Aug 21, 2003
Loading...

Share This Page