Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Deleting items from std::list

Reply
Thread Tools

Deleting items from std::list

 
 
Markus Svilans
Guest
Posts: n/a
 
      06-25-2006
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.

 
Reply With Quote
 
 
 
 
Alf P. Steinbach
Guest
Posts: n/a
 
      06-25-2006
* 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?
 
Reply With Quote
 
 
 
 
Markus Svilans
Guest
Posts: n/a
 
      06-25-2006

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.

 
Reply With Quote
 
Alf P. Steinbach
Guest
Posts: n/a
 
      06-25-2006
* 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?
 
Reply With Quote
 
Markus Svilans
Guest
Posts: n/a
 
      06-26-2006
> > 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.

 
Reply With Quote
 
Pete Becker
Guest
Posts: n/a
 
      06-26-2006
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.
 
Reply With Quote
 
Markus Svilans
Guest
Posts: n/a
 
      06-26-2006
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.

 
Reply With Quote
 
Markus Moll
Guest
Posts: n/a
 
      06-26-2006
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

 
Reply With Quote
 
Dmytro
Guest
Posts: n/a
 
      06-26-2006
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

 
Reply With Quote
 
Pete Becker
Guest
Posts: n/a
 
      06-26-2006
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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Deleting data from the file without deleting the file first crea C++ 2 12-28-2012 11:50 PM
Deleting items to deleted items folder. Geopelia NZ Computing 16 11-13-2012 05:49 AM
Deleting a File from Hardrive and Deleting a SubKey in Registry Harry Barker C++ 2 04-19-2006 09:34 AM
Deleting Items in the Registry MJW Computer Support 2 11-17-2003 07:44 PM
Deleting Items in the Registry MJW Computer Support 4 11-17-2003 11:57 AM



Advertisments