list remove and insert

Discussion in 'C++' started by Arne Claus, Oct 4, 2005.

  1. Arne Claus

    Arne Claus Guest

    Hi
    If've just read, that remove() on a list does not actually remove the
    elements, but places them at the end of the list (according to TC++STL
    by Josuttis). It also says, that remove returns a new, logical end
    pointer, so that the following

    myList::iterator end = myListObj.remove(myInt);
    myListObj.erase(end, myListObj.end());

    is possible and removes the "invalid" items at the end of the list.
    Now my question - is the following statement still vaild?

    myList::iterator end = myListObj.remove(myInt);
    myListObj.insert(anotherInt);
    myListObj.erase(end, myListObj.end());

    or does the iterator "end" not change?
    In my actual code I do some deleting and inserting after reusing the
    list (iterating over all elements). So I would like to do some kind of
    "lazy" correcting, which means doing the "erase-step" just before I
    start iterating over all elements again.

    Thanks
    Arne
     
    Arne Claus, Oct 4, 2005
    #1
    1. Advertising

  2. On Tue, 4 Oct 2005 14:19:06 +0200, Arne Claus <>
    wrote:

    >Hi
    >If've just read, that remove() on a list does not actually remove the
    >elements, but places them at the end of the list (according to TC++STL
    >by Josuttis). It also says, that remove returns a new, logical end
    >pointer, so that the following
    >
    >myList::iterator end = myListObj.remove(myInt);
    >myListObj.erase(end, myListObj.end());
    >
    >is possible and removes the "invalid" items at the end of the list.
    >Now my question - is the following statement still vaild?
    >
    >myList::iterator end = myListObj.remove(myInt);
    >myListObj.insert(anotherInt);
    >myListObj.erase(end, myListObj.end());
    >
    >or does the iterator "end" not change?
    >In my actual code I do some deleting and inserting after reusing the
    >list (iterating over all elements). So I would like to do some kind of
    >"lazy" correcting, which means doing the "erase-step" just before I
    >start iterating over all elements again.
    >
    >Thanks
    >Arne


    I don't believe that will work:

    - std::list<>::remove() returns void;
    - std::list<>::insert() has three overloads, all of which take an
    iterator as the first argument.

    I think you need to look at the way std::list works some more.

    --
    Bob Hairgrove
     
    Bob Hairgrove, Oct 4, 2005
    #2
    1. Advertising

  3. Arne Claus

    Rolf Magnus Guest

    Arne Claus wrote:

    > Hi
    > If've just read, that remove() on a list does not actually remove the
    > elements, but places them at the end of the list (according to TC++STL
    > by Josuttis). It also says, that remove returns a new, logical end
    > pointer, so that the following
    >
    > myList::iterator end = myListObj.remove(myInt);
    > myListObj.erase(end, myListObj.end());
    >
    > is possible and removes the "invalid" items at the end of the list.
    > Now my question - is the following statement still vaild?
    >
    > myList::iterator end = myListObj.remove(myInt);
    > myListObj.insert(anotherInt);


    std::list::insert needs an iterator that tells it where to insert the new
    value.

    > myListObj.erase(end, myListObj.end());
    >
    > or does the iterator "end" not change?


    Your code is valid. What it does depends on where you inserted the new
    value. If it was inserted before "end", it will stay in the list.
    Otherwise, it will be erased.
     
    Rolf Magnus, Oct 4, 2005
    #3
  4. Arne Claus

    Kristo Guest

    Arne Claus wrote:
    > Hi
    > If've just read, that remove() on a list does not actually remove the
    > elements, but places them at the end of the list (according to TC++STL
    > by Josuttis).


    I think you're referring to std::remove. The remove member function of
    the list class really does remove elements, and it doesn't return
    anything.

    > It also says, that remove returns a new, logical end pointer, so that
    > the following
    >
    > myList::iterator end = myListObj.remove(myInt);


    What the heck is a myList? If you've rolled your own list class, it
    doesn't matter what the Josuttis book says about lists. I'm going to
    give you the benefit of the doubt and assume you really want to use
    std::list. Next time, please post real, compilable code.

    > myListObj.erase(end, myListObj.end());


    This is commonly called the Erase-Remove Idiom, but it uses the remove
    function from the header <algorithm>.

    > is possible and removes the "invalid" items at the end of the list.
    > Now my question - is the following statement still vaild?
    >
    > myList::iterator end = myListObj.remove(myInt);


    Again, if you want that behavior, you need std::remove.

    > myListObj.insert(anotherInt);


    This is an error. All of the insert functions in std::list take at
    least two arguments. I suspect you're looking for a function like
    push_front.

    > myListObj.erase(end, myListObj.end());
    >
    > or does the iterator "end" not change?


    If you coded the preceeding lines properly, that line would be valid.
    insert, remove, and erase are all guaranteed not to invalidate
    iterators for a list.

    > In my actual code I do some deleting and inserting after reusing the
    > list (iterating over all elements). So I would like to do some kind of
    > "lazy" correcting, which means doing the "erase-step" just before I
    > start iterating over all elements again.


    But you've already looped over all the elements with the remove
    function, regardless of which one you use. Why not just use
    list::remove to search and erase all in one step?

    Kristo
     
    Kristo, Oct 4, 2005
    #4
  5. "Arne Claus" <> wrote in message
    news:dhts3b$e6g$-koblenz.de...

    > If've just read, that remove() on a list does not actually remove the
    > elements, but places them at the end of the list (according to TC++STL by
    > Josuttis). It also says, that remove returns a new, logical end pointer,
    > so that the following


    > myList::iterator end = myListObj.remove(myInt);
    > myListObj.erase(end, myListObj.end());


    > is possible and removes the "invalid" items at the end of the list.


    I think that perhaps you may have misunderstood. The behavior you describe
    applies to the remove algorithm (well, not quite, but close), not to the
    remove member of the list class.
     
    Andrew Koenig, Oct 4, 2005
    #5
  6. Arne Claus

    Arne Claus Guest

    Ok - there were some mistakes on my side (the code wasn't meant to be
    100% correct c++ - my bad :)

    > I think you're referring to std::remove. The remove member function of
    > the list class really does remove elements, and it doesn't return
    > anything.


    Ah - that's nice to know for a start. Josuttis says something about
    using the list-member functions because those are faster in terms of
    element access. If they do really remove the element (and thus
    producing a correct list) this is fine (but also a bit slower I guess).

    >> It also says, that remove returns a new, logical end pointer, so that
    >> the following
    >>
    >> myList::iterator end = myListObj.remove(myInt);

    >
    > What the heck is a myList? If you've rolled your own list class,


    typedef list<int> myList;

    I wanted to abbrief the template a bit here.

    >> myListObj.insert(anotherInt);

    >
    > This is an error. All of the insert functions in std::list take at
    > least two arguments. I suspect you're looking for a function like
    > push_front.


    Ok - that's my mistake now. I normally use push_back in my code and not insert.
    As I said - it was originally meant to be c++ alike pseudo code (and I
    should have said so in the first place - sorry).

    >> myListObj.erase(end, myListObj.end());
    >>
    >> or does the iterator "end" not change?

    >
    > If you coded the preceeding lines properly, that line would be valid.
    > insert, remove, and erase are all guaranteed not to invalidate
    > iterators for a list.


    Which means that end (retrieved by std::remove) would *not* change,
    even with a push_back - if I understand that correct.

    >> In my actual code I do some deleting and inserting after reusing the
    >> list (iterating over all elements). So I would like to do some kind of
    >> "lazy" correcting, which means doing the "erase-step" just before I
    >> start iterating over all elements again.

    >
    > But you've already looped over all the elements with the remove
    > function, regardless of which one you use. Why not just use
    > list::remove to search and erase all in one step?


    Well - If I've got a list of - let's say 500k Objects, and I want to
    remove 250k of them (random values) - what's faster std::remove with
    erase afterwards or list::remove?
    My guess whould be the first variant because here erase handles many
    items in a row, whereas in the second case the items are scattered
    around.

    I thought about a vector beeing a faster alternative here, too (random
    remove + adding at the end), but I'm not quite sure about this. Any
    suggestions would be helpfull there, too ^^

    Thank you
    Arne
     
    Arne Claus, Oct 4, 2005
    #6
  7. Arne Claus

    Kristo Guest

    Arne Claus wrote:
    > Well - If I've got a list of - let's say 500k Objects, and I want to
    > remove 250k of them (random values) - what's faster std::remove with
    > erase afterwards or list::remove?
    > My guess whould be the first variant because here erase handles many
    > items in a row, whereas in the second case the items are scattered
    > around.


    list::remove is faster in general, or else the standards people
    wouldn't have provided it as a member function. To delete an element
    from a list, all you have to do is reassign a couple of pointers. You
    need the erase-remove idiom for the cases (i.e., most of the time) when
    deleting elements is not so easy. std::remove also involves a lot of
    copying, whereas list::remove does not.

    In either case, you have to examine every element. It doesn't matter
    where they are in the list.

    > I thought about a vector beeing a faster alternative here, too (random
    > remove + adding at the end), but I'm not quite sure about this. Any
    > suggestions would be helpfull there, too ^^


    std::vector provides random *access*, not random removal of elements.
    You'd need the erase-remove idiom to do that on a vector. Also,
    std::list is usually implemented so that insertion at the beginning or
    the end takes O(1) time. In fact, IIRC, that's guaranteed by the
    standard. If you don't need the random access and you plan on doing a
    lot of deleting, I think std::list is the way to go.

    Kristo
     
    Kristo, Oct 4, 2005
    #7
    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. Simon-Pierre  Jarry
    Replies:
    2
    Views:
    2,412
    Henrik
    Aug 10, 2005
  2. tshad
    Replies:
    6
    Views:
    21,534
    tshad
    Aug 8, 2006
  3. Rares Vernica

    remove a list from a list

    Rares Vernica, Nov 17, 2006, in forum: Python
    Replies:
    1
    Views:
    265
    J. Clifford Dyer
    Nov 20, 2006
  4. Rares Vernica

    Re: remove a list from a list

    Rares Vernica, Nov 17, 2006, in forum: Python
    Replies:
    4
    Views:
    315
    John Henry
    Nov 17, 2006
  5. J. Muenchbourg
    Replies:
    3
    Views:
    259
    Aaron Bertrand - MVP
    Sep 30, 2003
Loading...

Share This Page