Deleting items from std::list

[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::eras e() 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_iterat or ri = data.rbegin();

while (ri != data.rend())
{
// Get next iterator in case ri is erased.
std::list<int>: :reverse_iterat or 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.

[Alf P. Steinbach]

Re: Deleting items from std::list

* Markus Svilans:[color=blue]
>
> Obviously an erase method is not defined for reverse iterators in
> std::list.
>
> Is there a nice solution to this problem?[/color]

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?

[Markus Svilans]

Re: Deleting items from std::list


Alf P. Steinbach wrote:[color=blue]
> * Markus Svilans:[color=green]
> >
> > Obviously an erase method is not defined for reverse iterators in
> > std::list.
> >
> > Is there a nice solution to this problem?[/color]
>
> Reverse the list (call data.reverse()) , then iterate in the forward
> direction.[/color]

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.

[Alf P. Steinbach]

Re: Deleting items from std::list

* Markus Svilans:[color=blue]
> Alf P. Steinbach wrote:[color=green]
>> * Markus Svilans:[color=darkred]
>>> Obviously an erase method is not defined for reverse iterators in
>>> std::list.
>>>
>>> Is there a nice solution to this problem?[/color]
>> Reverse the list (call data.reverse()) , then iterate in the forward
>> direction.[/color]
>
> 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.[/color]

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

[color=blue]
> However I sometimes have to deal with lists with a few hundred
> elements.[/color]

That's extremely short (not that the length matters since you're
traversing the complete list).

[color=blue]
> Assuming it's not possible to reverse the list before processing,[/color]

It is.

[color=blue]
> are there any alternatives?[/color]

Yes. You can add a dummy item at the start. Then you can use
reverse_iterato r::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?

[Markus Svilans]

Re: Deleting items from std::list

> > If the list were to be reversed before processing, and then reversed[color=blue][color=green]
> > again afterwards, this would only be reasonable solution for short
> > lists.[/color]
>
> Can't see why; you're traversing the complete list anyway.[/color]

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).
[color=blue][color=green]
> > Assuming it's not possible to reverse the list before processing,[/color]
>
> It is.[/color]

Yes, but can we pretend it's not for the sake of trying to find ways
around it? :)
[color=blue][color=green]
> > are there any alternatives?[/color]
>
> Yes. You can add a dummy item at the start. Then you can use
> reverse_iterato r::base(). But that is both complex and inefficient.[/color]

Thanks for the tip about reverse_iterato r::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.

[Pete Becker]

Re: Deleting items from std::list

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

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.

[Markus Svilans]

Re: Deleting items from std::list

Pete Becker wrote:[color=blue]
> Markus Svilans wrote:[color=green]
> > I'm hoping to
> > find a solution that avoids the reversals, to keep the running time
> > O(n) instead of O(3n).
> >[/color]
>
> 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.[/color]

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.)
[color=blue]
>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.[/color]

Deleting elements from a linked list is a constant time operation.
[color=blue]
>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().[/color]

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

Regards,
Markus.

[Markus Moll]

Re: Deleting items from std::list

Hi

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

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

Markus

[Dmytro]

Re: Deleting items from std::list

Markus Svilans написав:[color=blue]
> 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::eras e() method defined for
> reverse iterators.[/color]
[...]

Three Guidelines for Effective Iterator Usage

http://www.ddj.com/dept/cpp/184401406

[Pete Becker]

Re: Deleting items from std::list

Markus Svilans wrote:[color=blue]
> Pete Becker wrote:
>[color=green]
>>Markus Svilans wrote:
>>[color=darkred]
>>>I'm hoping to
>>>find a solution that avoids the reversals, to keep the running time
>>>O(n) instead of O(3n).
>>>[/color]
>>
>>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.[/color]
>
>
> For large lists, the difference between O(n) and O(3n) is not
> insignificant.[/color]

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.
[color=blue]
> 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.)[/color]

You're not talking about algorithmic complexity here, but about runtime.
That's not what O(n) refers to.
[color=blue]
>
>[color=green]
>>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.[/color]
>
>
> Deleting elements from a linked list is a constant time operation.
>[/color]

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.

[Howard Hinnant]

Re: Deleting items from std::list

In article <1151276851.123 572.175280@m73g 2000cwd.googleg roups.com>,
"Markus Svilans" <msvilans@gmail .com> wrote:
[color=blue]
> std::list<int> data;
>
> // [ code here to load data with values ]
>
> std::list<int>: :reverse_iterat or ri = data.rbegin();
>
> while (ri != data.rend())
> {
> // Get next iterator in case ri is erased.
> std::list<int>: :reverse_iterat or 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?[/color]

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

[Stuart Moore]

Re: Deleting items from std::list

On 26/06/06 00:07, Markus Svilans wrote:
[color=blue]
>
> 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?
>[/color]

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

[Jerry Coffin]

Re: Deleting items from std::list

In article <1151304044.784 354.174500@y41g 2000cwy.googleg roups.com>,
msvilans@gmail. com says...

[ ... ]
[color=blue]
> For large lists, the difference between O(n) and O(3n) is not
> insignificant.[/color]

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 "logarithmi c".
[color=blue]
> 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.)[/color]

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.

[P.J. Plauger]

Re: Deleting items from std::list

"Howard Hinnant" <howard.hinnant @gmail.com> wrote in message
news:howard.hin nant-995E8D.08102226 062006@syrcnyrd rs-01-ge0.nyroc.rr.co m...
[color=blue]
> In article <1151276851.123 572.175280@m73g 2000cwd.googleg roups.com>,
> "Markus Svilans" <msvilans@gmail .com> wrote:
>[color=green]
>> std::list<int> data;
>>
>> // [ code here to load data with values ]
>>
>> std::list<int>: :reverse_iterat or ri = data.rbegin();
>>
>> while (ri != data.rend())
>> {
>> // Get next iterator in case ri is erased.
>> std::list<int>: :reverse_iterat or 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?[/color]
>
> 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);
> }
> }[/color]

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

P.J. Plauger
Dinkumware, Ltd.

http://www.dinkumware.com

[Markus Svilans]

Re: Deleting items from std::list

Jerry Coffin wrote:[color=blue]
> In article <1151304044.784 354.174500@y41g 2000cwy.googleg roups.com>,
> msvilans@gmail. com says...
>
> [ ... ]
>[color=green]
> > For large lists, the difference between O(n) and O(3n) is not
> > insignificant.[/color]
>
> 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 "logarithmi c".
>[color=green]
> > 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.)[/color]
>
> 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.[/color]

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

Regards,
Markus.