Deleting items from std::list

[Markus Schoder]

std::list<int> data;

// [ code here to load data with values ]

std::list<int>::reverse_iterator ri = data.rbegin();

while (ri != data.rend())
{
// Get next iterator in case ri is erased.
std::list<int>::reverse_iterator next = ri;
++next;

// Check if ri needs to be erased
if (*ri == VALUE_TO_ERASE)
{
// [ code here to process *ri before erasing ]
data.erase(ri); // <-- Causes compiler error
}

ri = next;
}

Obviously an erase method is not defined for reverse iterators in
std::list.

The solution below is better but just for completeness sake

data.erase(ri.base());

should work.

for (std::list<int>::iterator ri = data.end(); ri != data.begin()
{
if (*--ri == VALUE_TO_ERASE)
{
// [ code here to process *ri before erasing ]
ri = data.erase(ri);
}
}

 

[P.J. Plauger]

std::list<int> data;

// [ code here to load data with values ]

std::list<int>::reverse_iterator ri = data.rbegin();

while (ri != data.rend())
{
// Get next iterator in case ri is erased.
std::list<int>::reverse_iterator next = ri;
++next;

// Check if ri needs to be erased
if (*ri == VALUE_TO_ERASE)
{
// [ code here to process *ri before erasing ]
data.erase(ri); // <-- Causes compiler error
}

ri = next;
}

Obviously an erase method is not defined for reverse iterators in
std::list.

The solution below is better but just for completeness sake

data.erase(ri.base());

should work.

for (std::list<int>::iterator ri = data.end(); ri != data.begin()
{
if (*--ri == VALUE_TO_ERASE)
{
// [ code here to process *ri before erasing ]
ri = data.erase(ri);
}
}

For completeness sake you have to specify how to make it past the
erased element with your reverse iterator. It's way messier than
for Hinnant's direct solution.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[Markus Schoder]

std::list<int> data;

// [ code here to load data with values ]

std::list<int>::reverse_iterator ri = data.rbegin();

while (ri != data.rend())
{
// Get next iterator in case ri is erased.
std::list<int>::reverse_iterator next = ri;
++next;

// Check if ri needs to be erased
if (*ri == VALUE_TO_ERASE)
{
// [ code here to process *ri before erasing ]
data.erase(ri); // <-- Causes compiler error
}

ri = next;
}

Obviously an erase method is not defined for reverse iterators in
std::list.

The solution below is better but just for completeness sake

data.erase(ri.base());

should work.

for (std::list<int>::iterator ri = data.end(); ri != data.begin()
{
if (*--ri == VALUE_TO_ERASE)
{
// [ code here to process *ri before erasing ]
ri = data.erase(ri);
}
}

For completeness sake you have to specify how to make it past the
erased element with your reverse iterator. It's way messier than
for Hinnant's direct solution.

Maybe I wasn't clear enough but I meant to say his (Hinnant's)
solution is better. Just wanted to point out that you can erase
through a reverse iterator. The way I did it is however not correct
since &*(ri.base()-1) == &*ri.

 

[P.J. Plauger]

Howard Hinnant wrote:
std::list<int> data;

// [ code here to load data with values ]

std::list<int>::reverse_iterator ri = data.rbegin();

while (ri != data.rend())
{
// Get next iterator in case ri is erased.
std::list<int>::reverse_iterator next = ri;
++next;

// Check if ri needs to be erased
if (*ri == VALUE_TO_ERASE)
{
// [ code here to process *ri before erasing ]
data.erase(ri); // <-- Causes compiler error
}

ri = next;
}

Obviously an erase method is not defined for reverse iterators in
std::list.

The solution below is better but just for completeness sake

data.erase(ri.base());

should work.

for (std::list<int>::iterator ri = data.end(); ri != data.begin()
{
if (*--ri == VALUE_TO_ERASE)
{
// [ code here to process *ri before erasing ]
ri = data.erase(ri);
}
}

For completeness sake you have to specify how to make it past the
erased element with your reverse iterator. It's way messier than
for Hinnant's direct solution.

Maybe I wasn't clear enough but I meant to say his (Hinnant's)
solution is better. Just wanted to point out that you can erase
through a reverse iterator. The way I did it is however not correct
since &*(ri.base()-1) == &*ri.

Maybe I wasn't clear enough:

1) You're right that erasing the element designated by base() is
off by one. But even if it were right, you'd then have an
invalid base(), useless for finding the next element in the list.

2) Your expression above is ill formed, since base() returns a
bidirectional iterator, which you can't subtract one from.

3) Thus, you're reduced to making a copy of base(), decrementing it,
then using that to erase the designated element.

So my point was that sketching a partial solution, which is
demonstrably hard to get right, doesn't add much to "completeness."
At least we're in violent agreement that Hinnant did it best.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[Markus Schoder]

Howard Hinnant wrote:
std::list<int> data;

// [ code here to load data with values ]

std::list<int>::reverse_iterator ri = data.rbegin();

while (ri != data.rend())
{
// Get next iterator in case ri is erased.
std::list<int>::reverse_iterator next = ri;
++next;

// Check if ri needs to be erased
if (*ri == VALUE_TO_ERASE)
{
// [ code here to process *ri before erasing ]
data.erase(ri); // <-- Causes compiler error
}

ri = next;
}

Obviously an erase method is not defined for reverse iterators in
std::list.

The solution below is better but just for completeness sake

data.erase(ri.base());

should work.

for (std::list<int>::iterator ri = data.end(); ri != data.begin()
{
if (*--ri == VALUE_TO_ERASE)
{
// [ code here to process *ri before erasing ]
ri = data.erase(ri);
}
}

For completeness sake you have to specify how to make it past the
erased element with your reverse iterator. It's way messier than
for Hinnant's direct solution.

Maybe I wasn't clear enough but I meant to say his (Hinnant's)
solution is better. Just wanted to point out that you can erase
through a reverse iterator. The way I did it is however not correct
since &*(ri.base()-1) == &*ri.

[snip]

2) Your expression above is ill formed, since base() returns a
bidirectional iterator, which you can't subtract one from.

I expect your defect report on comp.std.c++ shortly since the standard uses
similar notation in the reverse_iterator section. Hint: It is not actual
code but just explanatory.

[snip]

So my point was that sketching a partial solution, which is
demonstrably hard to get right, doesn't add much to "completeness."
At least we're in violent agreement that Hinnant did it best.

Since the OP stated that it is not possible to erase through a
reverse_iterator I consider it helpful and adding to "completeness" to
point out that it is indeed possible with the base() function even if it is
difficult to handle (which I proved by getting it wrong) and should better
be avoided if possible.

 

[Robbie Hatley]

There seems to be some functionality missing from the STL.

I am iterating through a linked list (std::list) using a reverse
iterator and attempting to erase certain items from the list. It is
important that I iterate through the list backwards, because the items
in it have to be processed in reverse order before erasing. However,
there does not appear to be an std::list::erase() method defined for
reverse iterators.

The erase() and insert() methods of all the STL containers require
iterators of type "iterator". The other three types ("reverse_iterator",
"const_iterator", "const_reverse_iterator") won't work.

No problem, though; just do this:

std::list<MyType> MyList;
std::list<MyType>::reverse_iterator RIter;
// ... some code ...
for (RIter = MyList.rbegin(); RIter != MyList.rend(); ++RIter)
{
// ... some code ...
// At this point, say you've decided you want to erase the
// element pointed to by RIter. Do this:
++RIter; // Advance RIter one-left.
MyList.erase(RIter.base()); // Erase element to right of RIter.
// ... some more code ...
}

That's actually snazzier in some ways than the "forward" version,
which requires you to capture the iterator returned by the erase()
function if you wish to continue iterating through the sequence.


--
Cheers,
Robbie Hatley
Tustin, CA, USA
lonewolfintj atsign pacbell period net
home period pacbell period net slantbar earnur slantbar