Dynamic item allocation to a unit

Started by
12 comments, last by 1863 13 years, 7 months ago
The standard way of doing this is to just pass your iterator to std::vector::erase(). Take note that doing so invalidates active iterators. So, if you are doing this in a loop, you need something like
std::vector< foo > myvec;for( std::vector< foo >::iterator i = myvec.begin(); i != myvec.end(); ){  if( !i->active() )    i = myvec.erase(i);  else    ++i;}

erase removes the element, and for a vector will preserve order and copy all the other elements up one. A list on the other hand would just pop the element out of the list without having to copy anything.

Your other option is to make a predicate function for std::remove_if along with std::erase
bool isInActive( const foo &f ){  return !f.Active();}myvec.erase( std::remove_if( myvec.begin(), myvec.end(), isInActive ), myvec.end() );

remove_if does your swap-to-end trick for all values that isInActive returns true. Then it gives you an iterator to the begining of the segment to erase.
Advertisement
If you are using std::vector, swapping the last entry with the removed entry is definitely the fastest way to go.

You should also take a look at http://www.cplusplus.com/reference/stl/list (std::list). It has the property of constant time removal of elements at any position, which may be useful if your list of items is large.

Take a look at the remove method in particular.
That's somewhat contradictory advice. std::list<>::remove() is an O(n) function; it iterates over the entire list to find the elements to remove. It would defeat the purpose of moving to a list in the first place.

Keep in mind that a std::list<>, or any linked list, tends to have poor performance characteristics for common operations such as iteration, as the node based structure tends to not play nicely with memory and cache. In many cases, even with functions with worse big-O characteristics, a std::vector<> will outperform a std::list<>.
Quote:Original post by SiCrane
That's somewhat contradictory advice. std::list<>::remove() is an O(n) function; it iterates over the entire list to find the elements to remove. It would defeat the purpose of moving to a list in the first place.


I has assumed that he would already be iterating over the elements in order to determine the index which he is passing to this function. Just trying to put some different options out there =)

Having said that, depending on what you want to do with your list of items, YMMV. std::vector is definitely hard to beat in terms of speed, especially if you don't care about the order of your items.

[Edited by - 1863 on August 28, 2010 9:31:41 PM]

This topic is closed to new replies.

Advertisement