How can I erase() using a reverse iterator?

Discussion in 'C++' started by Boltar, Jan 25, 2007.

  1. Boltar

    Boltar Guest

    Hi

    I'm going through an STL list container using a reverse iterator but it
    seems the erase() method only accepts ordinary iterators. Is there a
    similar method that will accept reverse iterators or alternatively is
    there a way to convert a reverse iterator to a normal one?

    Thanks for any help

    B2003
     
    Boltar, Jan 25, 2007
    #1
    1. Advertising

  2. Boltar

    Ondra Holub Guest

    Boltar napsal:
    > Hi
    >
    > I'm going through an STL list container using a reverse iterator but it
    > seems the erase() method only accepts ordinary iterators. Is there a
    > similar method that will accept reverse iterators or alternatively is
    > there a way to convert a reverse iterator to a normal one?
    >
    > Thanks for any help
    >
    > B2003


    I do not know which type of container are you using. Anyway I think you
    are not erasing all items in one step. So iterators will become
    invalid. You should use

    erase(container.rbegin(), container.rend());

    Or simillar and it should work.
     
    Ondra Holub, Jan 25, 2007
    #2
    1. Advertising

  3. Boltar

    Kai-Uwe Bux Guest

    Boltar wrote:

    > I'm going through an STL list container using a reverse iterator but it
    > seems the erase() method only accepts ordinary iterators. Is there a
    > similar method that will accept reverse iterators or alternatively is
    > there a way to convert a reverse iterator to a normal one?


    The reverse_iterator has a member function base() that will give you the
    value of the underlying iterator. Beware, however, that the underlying
    iterator points to a different element. It's off by one, and the precise
    relation ship is given in the standard [24.4.1/1] as:

    &*(reverse_iterator(i)) == &*(i - 1)


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Jan 25, 2007
    #3
  4. Boltar

    Boltar Guest

    On 25 Jan, 11:39, Kai-Uwe Bux <> wrote:
    > value of the underlying iterator. Beware, however, that the underlying
    > iterator points to a different element. It's off by one, and the precise
    > relation ship is given in the standard [24.4.1/1] as:
    >
    > &*(reverse_iterator(i)) == &*(i - 1)


    Thanks. That sounds like another triumph of committee decision making.
    Why on earth did they think having it off by one would be useful? Ah
    well....

    B2003
     
    Boltar, Jan 25, 2007
    #4
  5. Boltar

    Kai-Uwe Bux Guest

    Boltar wrote:

    >
    >
    > On 25 Jan, 11:39, Kai-Uwe Bux <> wrote:
    >> value of the underlying iterator. Beware, however, that the underlying
    >> iterator points to a different element. It's off by one, and the precise
    >> relation ship is given in the standard [24.4.1/1] as:
    >>
    >> &*(reverse_iterator(i)) == &*(i - 1)

    >
    > Thanks. That sounds like another triumph of committee decision making.
    > Why on earth did they think having it off by one would be useful?


    Well, this way, rbegin() corresponds to end() and rend() corresponds to
    begin(). If you had rbegin() be end()-1, what would rend() be? Before you
    answer begin()-1, you should consider the fact that that value simply does
    not exist (not even for built-in arrays).


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Jan 25, 2007
    #5
  6. Boltar wrote:
    >
    > On 25 Jan, 11:39, Kai-Uwe Bux <> wrote:
    >
    >>value of the underlying iterator. Beware, however, that the underlying
    >>iterator points to a different element. It's off by one, and the precise
    >>relation ship is given in the standard [24.4.1/1] as:
    >>
    >> &*(reverse_iterator(i)) == &*(i - 1)

    >
    >
    > Thanks. That sounds like another triumph of committee decision making.
    > Why on earth did they think having it off by one would be useful? Ah
    > well....


    What would your alternative definition be ?
     
    Gianni Mariani, Jan 25, 2007
    #6
  7. Boltar

    Boltar Guest

    On 25 Jan, 12:16, Gianni Mariani <> wrote:
    > What would your alternative definition be ?


    Make them the same. Why would you want anything else? If I want to get
    an iterator from a reverse iterator why would I want them to point at
    different container entries? Its illogical.

    B2003
     
    Boltar, Jan 25, 2007
    #7
  8. Boltar

    Boltar Guest

    On 25 Jan, 12:04, Kai-Uwe Bux <> wrote:
    >Well, this way, rbegin() corresponds to end() and rend() corresponds to
    > begin().


    Hardly useful and also logically incorrect since it implies end() is
    the last element in the container which it isn't. Far more useful to
    have the iterators correspond to each other IMO.

    B2003
     
    Boltar, Jan 25, 2007
    #8
  9. Boltar wrote:
    >
    > On 25 Jan, 12:16, Gianni Mariani <> wrote:
    >> What would your alternative definition be ?

    >
    > Make them the same. Why would you want anything else? If I want to get
    > an iterator from a reverse iterator why would I want them to point at
    > different container entries? Its illogical.


    Then what should rend() correspond to?


    --
    Clark S. Cox III
     
    Clark S. Cox III, Jan 25, 2007
    #9
  10. Boltar

    Pete Becker Guest

    Boltar wrote:
    >
    > On 25 Jan, 12:04, Kai-Uwe Bux <> wrote:
    >> Well, this way, rbegin() corresponds to end() and rend() corresponds to
    >> begin().

    >
    > Hardly useful


    On the contrary: it's exactly what you need when you pass reverse
    iterators to algorithms.

    > and also logically incorrect since it implies end() is
    > the last element in the container which it isn't.


    It implies that cont.end() returns an iterator that is past the end of
    the sequence held in the container, and that cont.rend() returns an
    iterator that is past the end of the reverse sequence held in the container.

    > Far more useful to
    > have the iterators correspond to each other IMO.
    >


    You're focusing too much on containers. The fundamental concept in STL
    is the range: a pair of iterators [first, last) that describes a
    sequence of elements. The iterator first points to the first element in
    the sequence. The iterator last points past the end of the sequence. You
    visit all the elements in that range by incrementing first until it
    equals last:

    while (first != last)
    do_something(first++);

    If reverse iterators worked the way you suggest, you'd have to duplicate
    all of the algorithms with a different control loop to handle reverse
    iterators.

    --

    -- Pete
    Roundhouse Consulting, Ltd. (www.versatilecoding.com)
    Author of "The Standard C++ Library Extensions: a Tutorial and
    Reference." (www.petebecker.com/tr1book)
     
    Pete Becker, Jan 25, 2007
    #10
  11. Boltar

    Boltar Guest

    On 25 Jan, 13:58, "Clark S. Cox III" <> wrote:
    >Then what should rend() correspond to?


    I wouldn't expect to correspond to anything, its not a valid position
    in the container.

    B2003
     
    Boltar, Jan 25, 2007
    #11
  12. Boltar

    Boltar Guest

    On 25 Jan, 14:23, Pete Becker <> wrote:
    > equals last:
    >
    > while (first != last)
    > do_something(first++);


    If your "last" variable really is the last entry and not the end()
    value then it won't call the do_something() method for the last one. I
    think possibly the naming was wrong with thes methods since begin()
    really does return the beginning position of the list (if there is one)
    but end() does not return the end position, it returns a value that
    signifies you've already gone past the final valid position, which is
    not the same thing at all. Its the difference between fgetc() returning
    the final character in a file and returning EOF.

    >
    > If reverse iterators worked the way you suggest, you'd have to duplicate
    > all of the algorithms with a different control loop to handle reverse
    > iterators.


    I don't see why , so long as the begin() and end() methods are
    consistent within the iterator type.

    B2003
     
    Boltar, Jan 25, 2007
    #12
  13. Boltar

    Marcus Kwok Guest

    Boltar <> wrote:
    > On 25 Jan, 11:39, Kai-Uwe Bux <> wrote:
    >> value of the underlying iterator. Beware, however, that the underlying
    >> iterator points to a different element. It's off by one, and the precise
    >> relation ship is given in the standard [24.4.1/1] as:
    >>
    >> &*(reverse_iterator(i)) == &*(i - 1)

    >
    > Thanks. That sounds like another triumph of committee decision making.
    > Why on earth did they think having it off by one would be useful? Ah
    > well....


    Maybe this article can shed some light on the subject:
    http://www.ddj.com/dept/cpp/184401406

    --
    Marcus Kwok
    Replace 'invalid' with 'net' to reply
     
    Marcus Kwok, Jan 25, 2007
    #13
  14. Boltar

    Pete Becker Guest

    Boltar wrote:
    >
    > On 25 Jan, 14:23, Pete Becker <> wrote:
    >> equals last:
    >>
    >> while (first != last)
    >> do_something(*first++);


    I added the missing * in the line above.

    >
    > If your "last" variable really is the last entry and not the end()
    > value then it won't call the do_something() method for the last one.


    The algorithm does not call do_something when first == last. That's
    fundamental. And it's the right behavior when you call an algorithm with
    a pair of iterators from a container, whether that pair is obtained by
    calling begin() and end() or by calling rbegin() and rend().

    > I
    > think possibly the naming was wrong with thes methods since begin()
    > really does return the beginning position of the list (if there is one)
    > but end() does not return the end position, it returns a value that
    > signifies you've already gone past the final valid position,


    They return iterators that mark the beginning and the end of the
    sequence that's managed by the container. Again: a sequence is
    designated by a pair of iterators. The first iterator points to the
    first element in the sequence and the second iteraotr points past the
    end of the sequence. It doesn't matter where the sequence comes from:
    that's what they have to be.

    > which is
    > not the same thing at all. Its the difference between fgetc() returning
    > the final character in a file and returning EOF.
    >


    Not really. begin() and end() [and rbegin() and rend()] return
    iterators. To check whether you're at the end of a sequence you compare
    the iterators for equality.

    >> If reverse iterators worked the way you suggest, you'd have to duplicate
    >> all of the algorithms with a different control loop to handle reverse
    >> iterators.

    >
    > I don't see why , so long as the begin() and end() methods are
    > consistent within the iterator type.
    >


    Iterator types do not have begin() and end() methods, so I don't know
    what you're trying to say here.

    The reason that rbegin() and rend() hold the iterator that points to the
    element that precedes the element that they point at is simply that
    rend() can't be implemented any other way. Using vector, for example,
    you can't have an iterator that points to the element before the first
    element in the contained array. So rend() creates an iterator that
    points to the first element.

    --

    -- Pete
    Roundhouse Consulting, Ltd. (www.versatilecoding.com)
    Author of "The Standard C++ Library Extensions: a Tutorial and
    Reference." (www.petebecker.com/tr1book)
     
    Pete Becker, Jan 25, 2007
    #14
  15. Boltar wrote:
    >
    > On 25 Jan, 14:23, Pete Becker <> wrote:
    >> equals last:
    >>
    >> while (first != last)
    >> do_something(first++);

    >
    > If your "last" variable really is the last entry and not the end()
    > value then it won't call the do_something() method for the last one.


    That's the point. Without that convention, there would be no way to
    indicate an empty sequence using iterator notation.

    > I think possibly the naming was wrong with thes methods since begin()
    > really does return the beginning position of the list (if there is
    > one) but end() does not return the end position,


    But it *does* return the end position (as distinct from the last element
    *in* the sequence). Perhaps visualizing it will help(requires a
    mono-spaced font):

    In a sequence of 5 objects (that may or may not be in a container):

    +---+---+---+---+---+
    | 0 | 1 | 2 | 3 | 4 |
    +---+---+---+---+---+
    ^ ^
    | |
    begin end
    rend rbegin

    > it returns a value that signifies you've already gone past the final
    > valid position, which is not the same thing at all. Its the
    > difference between fgetc() returning the final character in a file
    > and returning EOF.
    >
    >> If reverse iterators worked the way you suggest, you'd have to
    >> duplicate all of the algorithms with a different control loop to
    >> handle reverse iterators.

    >
    > I don't see why , so long as the begin() and end() methods are
    > consistent within the iterator type.


    Because, under your suggestion that reverse iterators and the underlying
    iterators dereference to the same element, dereferencing the iterator
    returned by rbegin() wouldn't be valid (as it would be like
    dereferencing the iterator returned by end()).

    Every algorithm would have to be rewritten to take this into account
    when dealing with reverse iterators.


    --
    Clark S. Cox III
     
    Clark S. Cox III, Jan 25, 2007
    #15
  16. Boltar wrote:
    >
    > On 25 Jan, 13:58, "Clark S. Cox III" <> wrote:
    >
    >>Then what should rend() correspond to?

    >
    >
    > I wouldn't expect to correspond to anything, its not a valid position
    > in the container.


    OK. Is it undefined to call base() on rend() ?
     
    Gianni Mariani, Jan 25, 2007
    #16
    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. Harald Grossauer

    set<>::erase(iterator) question

    Harald Grossauer, Sep 23, 2003, in forum: C++
    Replies:
    9
    Views:
    4,886
    Harald Grossauer
    Sep 24, 2003
  2. Kenneth Massey
    Replies:
    3
    Views:
    1,661
    Kenneth Massey
    Jul 21, 2004
  3. erase vs. erase

    , Mar 25, 2006, in forum: C++
    Replies:
    7
    Views:
    391
    Pete Becker
    Mar 30, 2006
  4. Dalbosco J-F
    Replies:
    3
    Views:
    908
    Marcus Kwok
    Aug 3, 2006
  5. Replies:
    6
    Views:
    490
    Howard
    Dec 4, 2006
Loading...

Share This Page