How can I erase() using a reverse iterator?

[Boltar]

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

 

[Ondra Holub]

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.

 

[Kai-Uwe Bux]

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

 

[Boltar]

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

 

[Kai-Uwe Bux]

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

 

[Gianni Mariani]

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 ?

 

[Boltar]

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]

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

 

[Clark S. Cox III]

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?

 

[Pete Becker]

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)

 

[Boltar]

Then what should rend() correspond to?

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

B2003

 

[Boltar]

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

 

[Marcus Kwok]

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

 

[Pete Becker]

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.

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)

 

[Clark S. Cox III]

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.


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.

 

[Gianni Mariani]

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() ?