STL prob

[bobby]

I have the following code

Code: Select all

typdef struct A
{
int a;
int b;
...
};

Then I have 2 deque's containing those stuctures ( deque<A> )

While iterating through one deque I want to pop an element off the one one deque and onto the other, but the following does not work

Code: Select all

deque<A>::iterator iterator;
deque<A>::iterator end;
for ( iterator = deque1.begin( ); iterator != end; ++iterator)
{
   if ( (*iterator).a == 1 )
     deque1.erase(iterator);
     deque2.push_back(*iterator);
  }
}

This doesnt work and screw's the deques up, even if I execute the two lines of code in the other order. Can someone help ?

[Banania]

your end iterator is not initialized.

and you might want to switch the lines.

[psyclonist]

Erasing "iterator" invalidates it. And dereferencing after it has been invalidated isn't supposed to work.

-psy

[leedgitar]

I'd recommend not removing the elements while iterating through them. Do the push_back in the for loop, then just call deque1.clear() after the loop ends.

[temas]

Code: Select all

std::copy(deq1.begin(), deq1.end(), std::back_inserter(deq2));
deq1.clear();

Off the top of my head. Use something like transform if you don't want an actual copy.

Edit: Moved to back to basics forum.

Edit2:Missed the if (*it).a == val check first read through, easy enough to make a handler for that though.

[PeterNewman]

Stuff mentioned (like end never being inited) is true, but also, once you delete(iterator), you cant ++iterator anymore!

Mabye have a list<deque<A>::iterator> toDelete, and instead of deleting the iterator in the loop, push the iterator onto the list ( toDelete.push_back(iterator) ) then after you've found everything you want to delete, do another loop going through the list, and delete the stored iterators ( deque1.erase( *listIterator ) )

Although if your deleting things out of the middle of a deque, I'm wondering if deque is the right structure for you.

[Slicky]

I thought that it was ok to erase but you should make the iterator equal the return from the erase call like:

Code: Select all

iterator = deque1.erase(iterator)

[monster]

Depends on the container.
See this section of the OgreOde thread, and check out the book suggested there;
http://www.ogre3d.org/phpBB2/viewtopic. ... &start=287

Code: Select all

iterator = my_deque.erase(iterator)

Is OK for contiguous memory containers (vector, deque, list, etc) but not for associative containers (like map). So it this case that's right, the erase returns an iterator to the next valid element.

[qsilver]

As others mentioned, erase() will invalidate the iterator that you give it (and possibly /all/ iterators, depending on the container). In general, it is best to avoid erasing unless you have to; use bulk clear()s instead. And you should only erase at the end of your processing, because all your iterators may become invalid.

std::copy() is very useful, and I suggest using it whenever possible. To move a whole container, use copy and then clear; to move a range, use copy and then erase(rangestart, rangeend).

Monster has the right idea in his reply, but "it = erase(it)" is non-standard behavior on many types of containers. It works for sequences (vector, list, deque) but not for associative containers (set, map). I think that Microsoft allows it for sets, but I'm pretty sure that other STL implementations do not. "erase(it++)" is the preferred notation for associative containers.

If you need to erase some elements but not others, you can use the following:

Code: Select all

containertype::iterator it;
for (it = container.begin(); it != container.end(); ) {
 do_something(*it);
 if (want_to_delete_it) {
  it = erase(it);   // use this for vectors, lists, deques
  //erase(it++);   // use this for maps, sets, multimaps
 } else {
  it++;
 }
}

(If you're wondering about why "erase(it++)" ever works, remember that the postfix++ is equivalent to {old = it; ++it; return old;} ... think about it!)

Also, FYI: vector, deque, and list are definately NOT all contiguous. Vector and deque are contiguous, so that insertions/deletions in the middle are slow but access is fast; list is not contiguous, so access is a little slower in the middle but deletions are very fast.

To find out more about what is allowed after an erase() and what isn't, read the STL documentation for each container class to see what actions invalidate iterators, and how many iterators are affected for each type of container. http://www.sgi.com/tech/stl/ is a fantastic reference; I suggest you bookmark it

[temas]

Also, FYI: vector, deque, set, and list are definately NOT the same class of containers. Vector and deque are contiguous, set and list are not.

vector, deque and list are all sequence containers which do define iterator erase(iterator). Set is part of the associative containers.

[qsilver]

Yes, I just meant to correct the word "contiguous" that monster used, since list is not contiguous. I edited my post to make things a little more clear, sorry for the confusion.

[monster]

I meant logically contiguous, if not physically.


But, yes, sequence containers is the correct term!