list remove and insert

[Arne Claus]

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

 

[Bob Hairgrove]

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.

 

[Rolf Magnus]

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.

 

[Kristo]

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

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

 

[Andrew Koenig]

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.

 

[Arne Claus]

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

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.

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

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.

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

 

[Kristo]

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