Weird behaviour from std::list<>::reverse_iterator

[Rune Allnor]

(Sorry if this question appears in two posts)

I have a list of size_t objects, the numbers 0, 1 and 2,
that are referenced by three ..::reverse_iterators. When I
erase the middle iterator, the item referenced by the argument
to list.erase() remains, while some other item has been deleted.

As far as I can see, this behaviour is not correct. The screen
dump below explains what was actually done, and compare it
to what I naively would expect to see. I also ran a similar test
with std::list<>::iterator types, and in that case the outcome
was as expected. So there is something weird about the
reverse_iterators.

Any opinions about what the cause might be?

I'm using VS2008.

Rune

/*****************************************************************/
Reverse iterator 'start' refers to value 0 - expected value 0.
Reverse iterator 'middle' refers to value 1 - expected value 1.
Reverse iterator 'tail' refers to value 2 - expected value 2.

Value referenced by reverse iterator 'middle' has been erased
Reverse iterator 'start' refers to value 0 - expected value 0.
Reverse iterator 'tail' refers to value 1 - expected value 2.

1st item in list: 0 - expected value 0.
2nd item in list: 1 - expected value 2.
/*****************************************************************/

#include <list>
#include <iostream>

int main()
{
std::list<size_t> list;

for (int n=0;n<3;++n)
list.push_back(n);

std::list<size_t>::reverse_iterator start = list.rbegin();
std::list<size_t>::reverse_iterator tail = start++;
std::list<size_t>::reverse_iterator middle = start++;
std::cout << "Reverse iterator 'start' refers to value " << *start
<< " - expected value 0."<< std::endl;
std::cout << "Reverse iterator 'middle' refers to value " << *middle
<< " - expected value 1."<< std::endl;
std::cout << "Reverse iterator 'tail' refers to value " << *tail
<< " - expected value 2."<< std::endl;

// Erase middle item from list.
list.erase(middle.base());
std::cout << std::endl;
std::cout << "Value referenced by reverse iterator 'middle' has been
erased" << std::endl;
std::cout << "Reverse iterator 'start' refers to value " << *start
<< " - expected value 0." << std::endl;
std::cout << "Reverse iterator 'tail' refers to value " << *tail
<< " - expected value 2." << std::endl;
std::cout << std::endl;

std::list<size_t>::iterator i = list.begin();
std::cout << "1st item in list: " << *i
<< " - expected value 0." << std::endl;
++i;
std::cout << "2nd item in list: " << *i
<< " - expected value 2." << std::endl;

return 0;
}

 

[Victor Bazarov]

(Sorry if this question appears in two posts)

I have a list of size_t objects, the numbers 0, 1 and 2,
that are referenced by three ..::reverse_iterators. When I
erase the middle iterator, the item referenced by the argument
to list.erase() remains, while some other item has been deleted.

As far as I can see, this behaviour is not correct. The screen
dump below explains what was actually done, and compare it
to what I naively would expect to see. I also ran a similar test
with std::list<>::iterator types, and in that case the outcome
was as expected. So there is something weird about the
reverse_iterators.

Any opinions about what the cause might be?

Well, you think you're erasing the value '1' but to know what value
you're erasing you need to print out 'middle.base()' that you're using
to erase something from the list.

Your misconception is that *middle == *(middle.base()). It isn't. The
reverse iterator's 'base' iterator points to a different value in the
container. At least IME.

I'm using VS2008.

I don't believe it should matter.

Rune

/*****************************************************************/
Reverse iterator 'start' refers to value 0 - expected value 0.
Reverse iterator 'middle' refers to value 1 - expected value 1.
Reverse iterator 'tail' refers to value 2 - expected value 2.

Value referenced by reverse iterator 'middle' has been erased
Reverse iterator 'start' refers to value 0 - expected value 0.
Reverse iterator 'tail' refers to value 1 - expected value 2.

1st item in list: 0 - expected value 0.
2nd item in list: 1 - expected value 2.
/*****************************************************************/

#include <list>
#include <iostream>

int main()
{
std::list<size_t> list;

for (int n=0;n<3;++n)
list.push_back(n);

std::list<size_t>::reverse_iterator start = list.rbegin();
std::list<size_t>::reverse_iterator tail = start++;
std::list<size_t>::reverse_iterator middle = start++;
std::cout << "Reverse iterator 'start' refers to value " << *start
<< " - expected value 0."<< std::endl;
std::cout << "Reverse iterator 'middle' refers to value " << *middle
<< " - expected value 1."<< std::endl;
std::cout << "Reverse iterator 'tail' refers to value " << *tail
<< " - expected value 2."<< std::endl;

// Erase middle item from list.
list.erase(middle.base());
std::cout << std::endl;
std::cout << "Value referenced by reverse iterator 'middle' has been
erased" << std::endl;
std::cout << "Reverse iterator 'start' refers to value " << *start
<< " - expected value 0." << std::endl;
std::cout << "Reverse iterator 'tail' refers to value " << *tail
<< " - expected value 2." << std::endl;
std::cout << std::endl;

std::list<size_t>::iterator i = list.begin();
std::cout << "1st item in list: " << *i
<< " - expected value 0." << std::endl;
++i;
std::cout << "2nd item in list: " << *i
<< " - expected value 2." << std::endl;

return 0;
}

V

 

[Rune Allnor]

Well, you think you're erasing the value '1' but to know what value
you're erasing you need to print out 'middle.base()' that you're using
to erase something from the list.

The semantics is clear: I have used reverse_iterators
to work my way from list.rbegin() to some item in the
list. The semantically simple call

list.erase(middle);

spawns a compiler error.

Your misconception is that *middle == *(middle.base()).  It isn't.  The
reverse iterator's 'base' iterator points to a different value in the
container.  At least IME.

So how can one convert from a reverse_iterator to
something that *both* can be used as argument to list.erase()
*and* refers to the correct element?

Rune

 

[Victor Bazarov]

The semantics is clear: I have used reverse_iterators
to work my way from list.rbegin() to some item in the
list. The semantically simple call

list.erase(middle);

spawns a compiler error.

There is no member 'erase' in 'std::list' that takes 'reverse_iterator'.
Perhaps it's an oversight. Try asking in 'comp.std.c++', or look in the
open standard library issues, maybe it's already there...

So how can one convert from a reverse_iterator to
something that *both* can be used as argument to list.erase()
*and* refers to the correct element?

I believe the relationship between iterators and reverse iterators is
such that the reverse iterators created from a regular iterator point to
the object one before the 'base'. Using the example from Josuttis:

list<int> lst;
lst.push_back(1);
lst.push_back(2);
lst.push_back(3);
list<int>::iterator it = begin();
assert(*it == 1);
++it;
assert(*it == 2);
list<int>::reverse_iterator rit(it); // not the same
assert(*rit == 1); //!!!!!!!!
assert(*(rit.base()) == 2);

So, when you want to delete the one you *found* using the reverse
iterators, you need to step the 'base' forward one:

list<int>::reverse_iterator one = lst.rbegin(); // 3
// the base of 'one' here is in fact 'lst.end()'
list<int>::reverse_iterator three = one++; // 3
// the base of 'three' is 'lst.end()'
list<int>::reverse_iterator two = one++; // 2
// the base of 'two' is one before 'end()'
one; // 1
// the base of 'one' is one before one before 'end()'

When you dereference a 'reverse_iterator', it actually dereferences the
iterator one before its own 'base'. So, deleting the 'base' would
delete the wrong element.

There is no single equivalent that "points to the same" and "can be
erased using '.erase' member". In order to erase the actual element,
you need to do

lst.erase(--two.base());

V

 

[James Kanze]

The semantics is clear: I have used reverse_iterators to work
my way from list.rbegin() to some item in the list. The
semantically simple call

spawns a compiler error.

That's the opinion of the standard, too. In fact,
reverse_iterator<>::base is guaranteed to point to the element
after (in the original sequence) the one pointed to by the
reverse iterator. The reason for this is simple: you need a
one past the end iterator; if reverse_iterator<>::base pointed
to the same element as reverse_iterator itself, the one past the
end reverse_iterator would require a base iterator one in front
of the beginning, which doesn't exist. So reverse iterator not
only swaps ++ and -- relative to the base, it also keeps the
base one above its own current element. (So, for example, in the
iterator returned by list<>::rbegin(), the base is equal to
list<>::end(), and can't be dereferences without first being
decremented. Similarly, list<>::rend() returns an iterator with

So how can one convert from a reverse_iterator to something
that *both* can be used as argument to list.erase() *and*
refers to the correct element?

Decrement the returned value. E.g.

std::list< size_t > tmp = middle.base() ;
-- tmp ;
list.erase( tmp ) ;

 

[Rune Allnor]

That's the opinion of the standard, too.  In fact,
reverse_iterator<>::base is guaranteed to point to the element
after (in the original sequence) the one pointed to by the
reverse iterator.  The reason for this is simple:

I can see the technical arguments why things are done
like this, but I can't see why these technicalities are
exposed to the users of the STL.

Whenever I, as *user* of the STL, uses a reverse iterator
to search for an item in a container, the natural semantics
of iterators (as a general concept, not C++ type) is to
manipulate the element in the container referenced by that
iterator. Not the element before. Not the element after.

So from a semantic point of view, the obvious thing to
try is

std::list<T> list;
std::list<T>::reverse_iterator i = ...;

list.erase(i);

and then expect the item referenced by i to be erased.
Isn't that the philosophy behind the STL? That users
should only worry about semantics and not need to know
about implementation details?

Rune

 

[Francesco]

I can see the technical arguments why things are done
like this, but I can't see why these technicalities are
exposed to the users of the STL.

Whenever I, as *user* of the STL, uses a reverse iterator
to search for an item in a container, the natural semantics
of iterators (as a general concept, not C++ type) is to
manipulate the element in the container referenced by that
iterator. Not the element before. Not the element after.

So from a semantic point of view, the obvious thing to
try is

std::list<T> list;
std::list<T>::reverse_iterator i = ...;

list.erase(i);

and then expect the item referenced by i to be erased.
Isn't that the philosophy behind the STL? That users
should only worry about semantics and not need to know
about implementation details?

I agree with you, I think that such a detail should be completely
transparent to the final user. Maybe there is some reason for this,
maybe also a reason that _obliges_ to take on such interface design,
but it could be as well an oversight as pointed out by Victor, simply
don't know enough of the STL implementation to dig this issue.

In any case, I'd have expected "erase" to accept a reverse_iterator
too. On the other hand, it is easy to derive from std::list and add
such a feature:

-------
template<class T> class MyList : public std::list<T> {
public:
void erase(typename std::list<T>::reverse_iterator& r_iter)
{
std::list<T>::erase(--r_iter.base());
}
};
-------

With reference to the OP code, changing the following two lines:
-------
std::list<size_t> list;
list.erase(middle.base());
-------
to this
-------
MyList<size_t> list;
list.erase(middle);
-------
lets the code work as intended and give the expected results.

Disclaimer: easy on my template derivation, I've just added as much as
needed to let the code compile and work. A serious derivation should
take allocators in account, and the "erase" function I added should
return a reverse iterator on its turn, to be coherent to the existing
one that works on forward iterators. I'm not on firm ground doing such
things, that was just a pointer. Better coders can improve it.

Hope that helps,
have fun,
Francesco

 

[Pavel]

Sure. And that's exactly what the program did: the call
list.erase(middle.base()) erased the element that middle.base() refers
to. The problem, as Victor said, is that that's not the element that
middle refers to. So the answer is: don't do that. middle.base() does
not do what you want; that's not its purpose. Look it up.


The problem with that, of course, is that list::erase doesn't take a
reverse_iterator, so that code doesn't compile. You'd have the same
problem if you tried to use any other iterator type (except
list::iterator and list::const_iterator) here. And that's a legitimate
complaint. It's not legitimate to complain that an attempted workaround
that shouldn't work didn't work.

I second this, for a change

Reverse iterator is more like a syntactic sugar to access the last
element with minimum of code wherever the container does not have back()
(like in sets, for example).. The convenience come at a cost as every
dereferencing has to decrement the underlying base() iterator. I would
recommend against using reverse iterator for anything but finding the
last element; if you need to iterate, get the base and decrement it
directly until it reaches begin() (you need to "check after" in your
loops then) -- this works faster.

The above is of course very much IMHO, the following is even more so:

Personally, I find it difficult to remember that I deal with reverse
iterator (it can be defined somewhere else) so when I see ++, I assume
we are going forward. ++ means forward and -- means backward -- quite a
strong idiom, so I like when it does not set me up for trouble. I
consider the necessity to remember whether an iterator was defined as
reverse like one more unnecessary element of context that takes free
memory from my developer's brain that is supposed to be focused on the
domain problem and good design to the highest degree possible.
Fortunately, reverse iterator has that little extra performance cost
that helps fend it off during code reviews..

-Pavel

 

[James Kanze]

I can see the technical arguments why things are done like
this, but I can't see why these technicalities are exposed to
the users of the STL.

They're more than just technicalities. What should
list<>::rend().base() return? (Remember that the iterator
returned from list<>::rend() doesn't have access to the list
itself.) The standard generally tries to avoid specifying
something that is impossible to implement.

Whenever I, as *user* of the STL, uses a reverse iterator to
search for an item in a container, the natural semantics of
iterators (as a general concept, not C++ type) is to
manipulate the element in the container referenced by that
iterator. Not the element before. Not the element after.

So from a semantic point of view, the obvious thing to try is

std::list<T> list;
std::list<T>::reverse_iterator i = ...;

and then expect the item referenced by i to be erased.

That, on the other hand, could be done. As far as I know, no
one has suggested it, but it would certainly be possible to
overload list<>::erase (and the erase functions in the other
containers) to take a reverse iterator, and that these
overloaded functions encapsulate the necessary logic.

Isn't that the philosophy behind the STL?

Not really. The philosophy is generally let the user beware,
with undefined behavior lurking at every (mis)step.

That users should only worry about semantics and not need to
know about implementation details?

I'm game, but first you'll have to propose an implemenation that
works. Ignoring implementation details supposes that there is
an implementation, which supposes that an implementation is
possible.

Note too that there are contexts where returning an iterator one
beyond is exactly what is wanted:

std::string
rightTrim(
std::string const& s,
SetOfCharacter const&
toRemove )
{
return std::string(
s.begin(),
std::find_if(
s.rbegin(), s.rend(), std::not1
( toRemove.contains() ) )
.base() ) ;
}

(FWIW: SetOfCharacter::contains() returns a predicate object,
which evaluates to true if the set contains the character in
question.)

If you're iterating backwards, you're often looking for a new
end to the sequence. So you find the last element in the new
sequence, but the end iterator defining the new sequence should
be one past this end.

 

[James Kanze]

Rune Allnor wrote:

[...]

The problem with that, of course, is that list::erase doesn't
take a reverse_iterator, so that code doesn't compile. You'd
have the same problem if you tried to use any other iterator
type (except list::iterator and list::const_iterator) here.
And that's a legitimate complaint.

Just wondering... Is it too late to do something about this for
the next release of the standard. It doesn't look like it would
require a lot of work. (But note that I'm not volenteering, at
least not in the immediate future. Between moving, changing
jobs and countries, and getting my web site back up, I've more
than enough to do at the moment.)

 

[Rune Allnor]

If you're iterating backwards, you're often looking for a new
end to the sequence.  So you find the last element in the new
sequence, but the end iterator defining the new sequence should
be one past this end.

The application where this came up is a search for the
convex hull of a set of (x,y) points. The algorithm starts
with an ordered set of points, and then searches for
candidates that satisfy the conditions for belonging to
the hull.

The hull itself is a list of (indexes to) points that already
have been found to satisfy the condutions. However, any new
point under investigation might invalidate any number of points
already in the list. These points-to-be-found-invalid are
located at the end of the list, as it was before one added
the new candidate point.

So the far end is the starting point for the search. The
newest candidate point (the tail of the list) will remain,
but any number of consecutive points between the tail and
the start of the list might have to be deleted.

Rune

 

[Jerry Coffin]

[ ... ]

The hull itself is a list of (indexes to) points that already
have been found to satisfy the condutions. However, any new
point under investigation might invalidate any number of points
already in the list. These points-to-be-found-invalid are
located at the end of the list, as it was before one added
the new candidate point.

In this case, I don't think I'd use a linked list at all. I'd use a
vector.

Right now, you're apparently using a linked list because you're
adding the new point to the end, and then deleting an arbitrary
number of nodes prior to that point in the list.

I'd simply reverse the order of operations: when you're investigating
a new point, walk through the vector from the end, find how many
points are now invalid, copy the new point over the top of the first
invalid point, and resize the vector down so any subsequent items are
no longer part of the vector.

 

[James Kanze]

Rune Allnor wrote:

[...]

So from a semantic point of view, the obvious thing to
try is
std::list<T> list;
std::list<T>::reverse_iterator i = ...;
list.erase(i);
and then expect the item referenced by i to be erased.
Isn't that the philosophy behind the STL? That users
should only worry about semantics and not need to know
about implementation details?
The problem with that, of course, is that list::erase
doesn't take a reverse_iterator, so that code doesn't
compile. You'd have the same problem if you tried to use
any other iterator type (except list::iterator and
list::const_iterator) here. And that's a legitimate
complaint.

Just wondering... Is it too late to do something about this
for the next release of the standard. It doesn't look like
it would require a lot of work.

Iterator adaptors (such as reverse_iterator) work when you
pass them to generic algorithms. Making them work with
non-generic algorithms that make assumptions about details of
the underlying container is quite another thing.

I wasn't thinking of anything so generic. Reverse iterators are
IMHO a special case, because they can be returned by member
functions; they are known to the container.

Off the top of my head, I don't see a clean way to do it.

-- add a requirement that iterator adaptors provide a member
function that returns the underlying iterator. Currently there
are no explicit requirements for iterator adaptors, so someone
would have to define what iterator adaptors are and write a
complete set of requirements for them.

The problem would be to define the "underlying iterator".

-- add an ad hoc set of member functions (erase, sort, ...)
to all the container requirements for each of the standard's
iterator adaptors. Gack.

Only for the types of iterators the container can return. If
the container can return iterator, const_iterator,
reverse_iterator and const_reverse_iterator, it seems reasonable
to be able to call erase with any of these, either because of
overloading or implicit conversion.

(And while I'm at it, I note that the change of erase to take a
const_iterator, with, if I read correctly, no overload to take
iterator, breaks code. The cases are probably rare, but still,
it's unnecessary---it would be more reasonable to provide an
overload.)

-- specify a converter function that takes an iterator and
returns its underlying iterator; default is to return its
argument, specialize for various iterator adaptors. Maybe.

Of course, all of these would also have to address the
possibility of an adaptor that's constructed from another
adaptor. And that's not trivial.

The general case is IMHO to complicated to be addressed by the
standard. The only thing that I think might be considered is
requiring overloads for erase, insert and emplace so that they
can be called with any iterator type which is actually known to
the container.

 

[James Kanze]

James Kanze wrote:

Well, sure. We could add erase member functions that take each
of the standard's iterator adaptors to every container. But
that won't help with user-defined iterator adaptors.

You're thinking too generically. std::list<> has functions
which return a std::list<>::reverse_iterator, so it doesn't seem
too far fetched to say that such an iterator can be used to
specify the location for insertion or erasure.

I think that would be a minimum extension, and not to difficult.
Handling arbitrary adapters would be a major project---it might
be nice, but I'd like to see a proof of concept implementation
first.

When a program calls list::erase with a reverse iterator the
requirement is clear. list::erase takes an argument of type
list::const_iterator, so the program is ill-formed. No
undefined behavior in sight.

In this case.

And in the current standard, list::erase takes an iterator, and
not a const_iterator. Changing that (rather than adding an
overload) breaks user code, e.g.:

template< typename T >
class MyIterator
{
public:
operator std::list< T >::iterator() const
{
return something ;
}
// ...
} ;

void
f( std::list< int >& l )
{
MyIterator i( ... ) ;
l.erase( i ) ;
}

According to C++03, that's legal code, and guaranteed to work.
According to the draft C++0x, it's not, and requires a compiler
diagnostic.