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::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.

 

[Alf P. Steinbach]

* 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.

 

[Markus Svilans]

* Markus Svilans:

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.

 

[Alf P. Steinbach]

* Markus Svilans:

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.

 

[Markus Svilans]

If the list were to be reversed before processing, and then reversed

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).

It is.

Yes, but can we pretend it's not for the sake of trying to find ways
around it?

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.

 

[Pete Becker]

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

 

[Markus Svilans]

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.

 

[Markus Moll]

Hi

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

 

[Dmytro]

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

 

[Pete Becker]

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.

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.

 

[Howard Hinnant]

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

 

[Stuart Moore]

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

 

[Jerry Coffin]

[ ... ]

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.

 

[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.

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

 

[Markus Svilans]

[ ... ]

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.

 

[Markus Svilans]

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.

 

[Markus Svilans]

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.

 

[Markus Svilans]

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.

 

[Stuart Golodetz]

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

 

[P.J. Plauger]

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