By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,657 Members | 994 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,657 IT Pros & Developers. It's quick & easy.

Deleting items from std::list

P: n/a
Hi,

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.

I am using STLport 4.5 with Borland C++ Builder 6.

The following example code shows what I am trying to do:

// Arbitrary value to remove from the list
const int VALUE_TO_ERASE = 12;

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.

Is there a nice solution to this problem? Do I need to get a more
recent version of STLport?

Thanks,
Markus.

Jun 25 '06 #1
Share this Question
Share on Google+
25 Replies


P: n/a
* Markus Svilans:

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

Is there a nice solution to this problem?


Reverse the list (call data.reverse()), then iterate in the forward
direction.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Jun 25 '06 #2

P: n/a

Alf P. Steinbach wrote:
* Markus Svilans:

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

Is there a nice solution to this problem?


Reverse the list (call data.reverse()), then iterate in the forward
direction.


Thanks for your response.

If the list were to be reversed before processing, and then reversed
again afterwards, this would only be reasonable solution for short
lists. However I sometimes have to deal with lists with a few hundred
elements.

Assuming it's not possible to reverse the list before processing, are
there any alternatives?

Thanks,
Markus.

Jun 25 '06 #3

P: n/a
* Markus Svilans:
Alf P. Steinbach wrote:
* Markus Svilans:
Obviously an erase method is not defined for reverse iterators in
std::list.

Is there a nice solution to this problem? Reverse the list (call data.reverse()), then iterate in the forward
direction.


Thanks for your response.

If the list were to be reversed before processing, and then reversed
again afterwards, this would only be reasonable solution for short
lists.


Can't see why; you're traversing the complete list anyway.

However I sometimes have to deal with lists with a few hundred
elements.
That's extremely short (not that the length matters since you're
traversing the complete list).

Assuming it's not possible to reverse the list before processing,
It is.

are there any alternatives?


Yes. You can add a dummy item at the start. Then you can use
reverse_iterator::base(). But that is both complex and inefficient.

Disclaimer: there may a simpler way that I don't know about, I don't use
this stuff regularly.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Jun 25 '06 #4

P: n/a
> > If the list were to be reversed before processing, and then reversed
again afterwards, this would only be reasonable solution for short
lists.


Can't see why; you're traversing the complete list anyway.


Reversing the list before and after would approximately triple the time
it takes to process the items in the list. I think that's a correct
assumption, because the reversal would involve traversing the list at
least once. Because the list is traversed very often, I'm hoping to
find a solution that avoids the reversals, to keep the running time
O(n) instead of O(3n).
Assuming it's not possible to reverse the list before processing,


It is.


Yes, but can we pretend it's not for the sake of trying to find ways
around it? :)
are there any alternatives?


Yes. You can add a dummy item at the start. Then you can use
reverse_iterator::base(). But that is both complex and inefficient.


Thanks for the tip about reverse_iterator::base(). I should be able to
use that to convert the reverse iterator to a forward iterator that I
can then use to erase the list element.

Thanks,
Markus.

Jun 26 '06 #5

P: n/a
Markus Svilans wrote:
I'm hoping to
find a solution that avoids the reversals, to keep the running time
O(n) instead of O(3n).


O(n) and O(3n) are the same thing: linear in the number of elements in
the list. More important, though, is the assumption that the multiplier
for reversing a list is exactly the same as the multiplier for whatever
it is that you're doing with the list elements. Since the task involves
erasing elements, that's almost certainly not the case. My bet is that
the time involved in reversing the list is far less than the time
involved in the desired traversal. However, reversing it twice is a
brute force solution, and I agree with your feeling that there ought to
be a better way. I'd use base().

--

Pete Becker
Roundhouse Consulting, Ltd.
Jun 26 '06 #6

P: n/a
Pete Becker wrote:
Markus Svilans wrote:
I'm hoping to
find a solution that avoids the reversals, to keep the running time
O(n) instead of O(3n).

O(n) and O(3n) are the same thing: linear in the number of elements in
the list. More important, though, is the assumption that the multiplier
for reversing a list is exactly the same as the multiplier for whatever
it is that you're doing with the list elements.


For large lists, the difference between O(n) and O(3n) is not
insignificant. Spending 3 seconds to accomplish a task is silly when
it's possible in only 1 second. (Not that processing my list will take
3 seconds, but it will be processed consecutively hundreds or thousands
of times.)
Since the task involves
erasing elements, that's almost certainly not the case. My bet is that
the time involved in reversing the list is far less than the time
involved in the desired traversal.
Deleting elements from a linked list is a constant time operation.
However, reversing it twice is a
brute force solution, and I agree with your feeling that there ought to
be a better way. I'd use base().


Base() seems to be the solution for converting reverse iterators to
forward iterators, suitable for passing to std::list::erase(). I'm glad
you and Alf brought it to my attention. Thanks!

Regards,
Markus.

Jun 26 '06 #7

P: n/a
Hi

Markus Svilans wrote:
Pete Becker wrote:
O(n) and O(3n) are the same thing
[...] For large lists, the difference between O(n) and O(3n) is not
insignificant.


You're abusing notation.
Believe Pete, O(n) = O(3n) = O(1,000,000n).

Markus

Jun 26 '06 #8

P: n/a
Markus Svilans написав:
Hi,

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.

[...]

Three Guidelines for Effective Iterator Usage
http://www.ddj.com/dept/cpp/184401406

Jun 26 '06 #9

P: n/a
Markus Svilans wrote:
Pete Becker wrote:
Markus Svilans wrote:
I'm hoping to
find a solution that avoids the reversals, to keep the running time
O(n) instead of O(3n).

O(n) and O(3n) are the same thing: linear in the number of elements in
the list. More important, though, is the assumption that the multiplier
for reversing a list is exactly the same as the multiplier for whatever
it is that you're doing with the list elements.

For large lists, the difference between O(n) and O(3n) is not
insignificant.


Again: there is no difference. O(n) and O(3n) are BOTH LINEAR. That's
what the notation means. Complexity analysis is about how an algorithm
scales when you apply it to larger data sets.
Spending 3 seconds to accomplish a task is silly when
it's possible in only 1 second. (Not that processing my list will take
3 seconds, but it will be processed consecutively hundreds or thousands
of times.)
You're not talking about algorithmic complexity here, but about runtime.
That's not what O(n) refers to.

Since the task involves
erasing elements, that's almost certainly not the case. My bet is that
the time involved in reversing the list is far less than the time
involved in the desired traversal.

Deleting elements from a linked list is a constant time operation.


Deleting an element is a constant time operation. And I assumed that
destroying a contained element is also constant time. That doesn't mean
that walking through the list once to reverse it, once to do whatever
operations you're doing, and once to reverse it again requires exactly
three times as long as the primary operation.

Again: I have no problem with not wanting to go through the list three
times. It's at least inelegant, possibly inefficient. My objection is to
making up numbers to justify it.

--

Pete Becker
Roundhouse Consulting, Ltd.
Jun 26 '06 #10

P: n/a
In article <11**********************@m73g2000cwd.googlegroups .com>,
"Markus Svilans" <ms******@gmail.com> 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.

Is there a nice solution to this problem? Do I need to get a more
recent version of STLport?


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);
}
}

-Howard
Jun 26 '06 #11

P: n/a
On 26/06/06 00:07, Markus Svilans wrote:

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

Is there a nice solution to this problem? Do I need to get a more
recent version of STLport?


Can you use the entire list backwards (i.e. you insert at the beginning,
not the end, and then use a forward iterator)

If you need to do this with other classes you can't control, you might
be able to make some kind of a wrapper class?

Stuart
Jun 26 '06 #12

P: n/a
In article <11**********************@y41g2000cwy.googlegroups .com>,
ms******@gmail.com says...

[ ... ]
For large lists, the difference between O(n) and O(3n) is not
insignificant.
For any size of list (or anything else) the difference between O(n)
and O(3n) is nonexistent. What Pete was trying to point out
(correctly) was that big-O notation deliberately ignores any constant
differences. Its basic intent is to look ONLY at the shape of the
curve involved. To do that, it eliminates all constant factors -- the
result is that it can usually be summarized as something like
"linear", "quadratic" or "logarithmic".
Spending 3 seconds to accomplish a task is silly when
it's possible in only 1 second. (Not that processing my list will take
3 seconds, but it will be processed consecutively hundreds or thousands
of times.)


Nobody's trying to say that tripling the speed of an operation can't
mean anything -- they're only saying that big-O notation isn't suited
to such situations.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jun 26 '06 #13

P: n/a
"Howard Hinnant" <ho************@gmail.com> wrote in message
news:ho**********************************@syrcnyrd rs-01-ge0.nyroc.rr.com...
In article <11**********************@m73g2000cwd.googlegroups .com>,
"Markus Svilans" <ms******@gmail.com> 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.

Is there a nice solution to this problem? Do I need to get a more
recent version of STLport?


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);
}
}


In case it gets lost in all the discussion of complexity, this is
the proper solution. Don't try to use reverse_iterators where
they're inappropriate -- just solve the problem.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
Jun 26 '06 #14

P: n/a
Jerry Coffin wrote:
In article <11**********************@y41g2000cwy.googlegroups .com>,
ms******@gmail.com says...

[ ... ]
For large lists, the difference between O(n) and O(3n) is not
insignificant.


For any size of list (or anything else) the difference between O(n)
and O(3n) is nonexistent. What Pete was trying to point out
(correctly) was that big-O notation deliberately ignores any constant
differences. Its basic intent is to look ONLY at the shape of the
curve involved. To do that, it eliminates all constant factors -- the
result is that it can usually be summarized as something like
"linear", "quadratic" or "logarithmic".
Spending 3 seconds to accomplish a task is silly when
it's possible in only 1 second. (Not that processing my list will take
3 seconds, but it will be processed consecutively hundreds or thousands
of times.)


Nobody's trying to say that tripling the speed of an operation can't
mean anything -- they're only saying that big-O notation isn't suited
to such situations.


Thanks Jerry, Markus, Pete -- clearly I was misusing big-O notation. I
understand your point and I agree with you.

Regards,
Markus.

Jun 26 '06 #15

P: n/a
Howard Hinnant wrote:
In article <11**********************@m73g2000cwd.googlegroups .com>,
"Markus Svilans" <ms******@gmail.com> 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.

Is there a nice solution to this problem? Do I need to get a more
recent version of STLport?


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);
}
}

-Howard


Howard:

I feel like slapping my forehead. Thanks for reminding me that you can
iterate backwards using forward iterators. ;)

Regards,
Markus.

Jun 26 '06 #16

P: n/a

Pete Becker wrote:
Markus Svilans wrote:
I'm hoping to
find a solution that avoids the reversals, to keep the running time
O(n) instead of O(3n).


O(n) and O(3n) are the same thing: linear in the number of elements in
the list. More important, though, is the assumption that the multiplier
for reversing a list is exactly the same as the multiplier for whatever
it is that you're doing with the list elements. Since the task involves
erasing elements, that's almost certainly not the case. My bet is that
the time involved in reversing the list is far less than the time
involved in the desired traversal. However, reversing it twice is a
brute force solution, and I agree with your feeling that there ought to
be a better way. I'd use base().

I understand your point, you're right. My mistake for forgetting proper
usage of big-O notation.

Thanks,
Markus.

Jun 26 '06 #17

P: n/a

Dmytro wrote:
Markus Svilans написав:
Hi,

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.

[...]

Three Guidelines for Effective Iterator Usage
http://www.ddj.com/dept/cpp/184401406


Thanks for the link to the informative article. It answered my original
question, and many more I probably would have asked in the near future.

Regards,
Markus.

Jun 26 '06 #18

P: n/a
"Markus Svilans" <ms******@gmail.com> wrote in message
news:11**********************@y41g2000cwy.googlegr oups.com...
Pete Becker wrote:
Markus Svilans wrote:
> I'm hoping to
> find a solution that avoids the reversals, to keep the running time
> O(n) instead of O(3n).
>
O(n) and O(3n) are the same thing: linear in the number of elements in
the list. More important, though, is the assumption that the multiplier
for reversing a list is exactly the same as the multiplier for whatever
it is that you're doing with the list elements.


For large lists, the difference between O(n) and O(3n) is not
insignificant. Spending 3 seconds to accomplish a task is silly when
it's possible in only 1 second. (Not that processing my list will take
3 seconds, but it will be processed consecutively hundreds or thousands
of times.)


FWIW:

f(n) = O(g(n)) iff there exist c, n0 > 0 s.t. for all n >= n0, f(n) <=
c.g(n)

So O(n) = O(3n) for the following reason:

Suppose f(n) = O(n). Then there exist c, n0 > 0 s.t. for all n >= n0, f(n)
<= c.n. Or equivalently, there exist c, n0 s.t. for all n >= n0, f(n) <=
(c/3).(3n). But then there exist c' = c/3, n0' = n0 s.t. for all n >= n0',
f(n) <= c'.(3n), i.e. f(n) = O(3n). Similarly for the converse, i.e. f(n) =
O(n) if f(n) = O(3n).

HTH,
Stu

<snip> Regards,
Markus.

Jun 26 '06 #19

P: n/a
"Markus Svilans" <ms******@gmail.com> wrote in message
news:11**********************@c74g2000cwc.googlegr oups.com...
I feel like slapping my forehead. Thanks for reminding me that you can
iterate backwards using forward iterators. ;)


Well, no. But you can iterate backwards using bidirectional iterators,
which list supports.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
Jun 26 '06 #20

P: n/a
Howard Hinnant wrote:
In article <11**********************@m73g2000cwd.googlegroups .com>,
"Markus Svilans" <ms******@gmail.com> 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);
}
}


Jun 26 '06 #21

P: n/a
"Markus Schoder" <a3*************@yahoo.de> wrote in message
news:44***********************@newsread4.arcor-online.net...
Howard Hinnant wrote:
In article <11**********************@m73g2000cwd.googlegroups .com>,
"Markus Svilans" <ms******@gmail.com> 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.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
Jun 26 '06 #22

P: n/a
P.J. Plauger wrote:
"Markus Schoder" <a3*************@yahoo.de> wrote in message
news:44***********************@newsread4.arcor-online.net...
Howard Hinnant wrote:
In article <11**********************@m73g2000cwd.googlegroups .com>,
"Markus Svilans" <ms******@gmail.com> 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.

Jun 27 '06 #23

P: n/a
"Markus Schoder" <a3*************@yahoo.de> wrote in message
news:44***********************@newsread4.arcor-online.net...
P.J. Plauger wrote:
"Markus Schoder" <a3*************@yahoo.de> wrote in message
news:44***********************@newsread4.arcor-online.net...
Howard Hinnant wrote:
In article <11**********************@m73g2000cwd.googlegroups .com>,
"Markus Svilans" <ms******@gmail.com> 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
Jun 28 '06 #24

P: n/a
P.J. Plauger wrote:
"Markus Schoder" <a3*************@yahoo.de> wrote in message
news:44***********************@newsread4.arcor-online.net...
P.J. Plauger wrote:
"Markus Schoder" <a3*************@yahoo.de> wrote in message
news:44***********************@newsread4.arcor-online.net...

Howard Hinnant wrote:
> In article <11**********************@m73g2000cwd.googlegroups .com>,
> "Markus Svilans" <ms******@gmail.com> 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.

Jun 28 '06 #25

P: n/a
"Markus Svilans" wrote:
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
Jun 28 '06 #26

This discussion thread is closed

Replies have been disabled for this discussion.