Deleting items from std::list

Discussion in 'C++' started by Markus Svilans, Jun 26, 2006.

  1. 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.
    Markus Svilans, Jun 26, 2006
    #1
    1. Advertising

  2. * 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?
    Alf P. Steinbach, Jun 26, 2006
    #2
    1. Advertising

  3. 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.
    Markus Svilans, Jun 26, 2006
    #3
  4. * 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?
    Alf P. Steinbach, Jun 26, 2006
    #4
  5. > > 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.
    Markus Svilans, Jun 26, 2006
    #5
  6. Markus Svilans

    Pete Becker Guest

    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.
    Pete Becker, Jun 26, 2006
    #6
  7. 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.
    Markus Svilans, Jun 26, 2006
    #7
  8. Markus Svilans

    Markus Moll Guest

    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
    Markus Moll, Jun 26, 2006
    #8
  9. Markus Svilans

    Dmytro Guest

    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
    Dmytro, Jun 26, 2006
    #9
  10. Markus Svilans

    Pete Becker Guest

    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.
    Pete Becker, Jun 26, 2006
    #10
  11. In article <>,
    "Markus Svilans" <> 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 Hinnant, Jun 26, 2006
    #11
  12. Markus Svilans

    Stuart Moore Guest

    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
    Stuart Moore, Jun 26, 2006
    #12
  13. Markus Svilans

    Jerry Coffin Guest

    In article <>,
    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.
    Jerry Coffin, Jun 26, 2006
    #13
  14. Markus Svilans

    P.J. Plauger Guest

    "Howard Hinnant" <> wrote in message
    news:...

    > In article <>,
    > "Markus Svilans" <> 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
    P.J. Plauger, Jun 26, 2006
    #14
  15. Jerry Coffin wrote:
    > In article <>,
    > 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.
    Markus Svilans, Jun 26, 2006
    #15
  16. Howard Hinnant wrote:
    > In article <>,
    > "Markus Svilans" <> 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.
    Markus Svilans, Jun 26, 2006
    #16
  17. 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.
    Markus Svilans, Jun 26, 2006
    #17
  18. 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.
    Markus Svilans, Jun 26, 2006
    #18
  19. "Markus Svilans" <> wrote in message
    news:...
    > 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.
    Stuart Golodetz, Jun 26, 2006
    #19
  20. Markus Svilans

    P.J. Plauger Guest

    "Markus Svilans" <> wrote in message
    news:...

    > 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
    P.J. Plauger, Jun 26, 2006
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. NFish
    Replies:
    6
    Views:
    15,278
    Andrey Tarasevich
    Nov 7, 2003
  2. Replies:
    6
    Views:
    643
    Jim Langston
    Oct 30, 2005
  3. Andy
    Replies:
    3
    Views:
    483
    James Kanze
    Jun 8, 2007
  4. Juha Nieminen
    Replies:
    22
    Views:
    1,024
    Kai-Uwe Bux
    Oct 12, 2007
  5. lallous
    Replies:
    5
    Views:
    373
    lallous
    Apr 24, 2008
Loading...

Share This Page