std::vector efficiency question

std::vector::iterator != std::vector::iterator, anyways is there a particular reason you wont create the vector of some type on the heap? or was you trying to make a vector of pointers to some type? you can use the STL algorithm remove_if in-conguction with vector::erase to conditionally remove elements.

This is less a problem with vector and more a problem of choosing the right tool for the job. I would think you would want to use a list for this and not a vector. A vector is going to be very inefficient for arbitrary inserting and deleting.

I recommend not using vector::clear(), instead use vector::resize(0). It is much faster.

I learned this from one of the GDC slides called

Common C++ Performance Mistakes in Games

You can find it on this page
http://www.gdconf.com/archives/2004/index.htm

Very good performance tips in there.

Edit: regarding your original question, something you can try is instead of removing elements from the vector, swap the element you want to remove with the last element in the vector, and then you can pop_back() without suffering the cost of removing from a vector.

Quote:

Original post by snk_kid std::vector::iterator != std::vector::iterator, anyways is there a particular reason you wont create the vector of some type on the heap? or was you trying to make a vector of pointers to some type? you can use the STL algorithm remove_if in-conguction with vector::erase to conditionally remove elements.

Yes, I made an error (corrected now): it should be std::vector::iterator
Is vector::erase the fastest way to remove an element from an vector?

Quote:

Original post by CodeMunkie This is less a problem with vector and more a problem of choosing the right tool for the job. I would think you would want to use a list for this and not a vector. A vector is going to be very inefficient for arbitrary inserting and deleting.

I use a vector because I also need to sort later on. I think sorting a vector is much faster than sorting a list, or am I wrong?
So I need fast soring and fast arbitrary removing of elements.

If you need fast insertion and deletion of elements, then you don't get faster than a list, algorithmically.

For removing if a certain condition is true, check this out:



You can find out more about remove_if here. remove doesn't actually remove or destruct elements, rather it just reorders them so that all the elements that meet the condition are grouped at the end.

Quote:

Original post by crocomire I use a vector because I also need to sort later on. I think sorting a vector is much faster than sorting a list, or am I wrong? So I need fast soring and fast arbitrary removing of elements.

What is your usage pattner more exactly, you could use std::set to have O(log N) insertions and removal problem is you'll take the same (or actually slightly more) performance hit as a list when iterating.

So if you also does a lot of iterating a vector could be the best option anyhow even if you need to resort it.

But for that case I advice you to not use remove but instead swap the last element with whatever element needs to be deleted and then pop_back and when you're done with all removals and insertions just resort it.

oh, and if you have pointers in that vector that needs to be deleted don't use remove_if or similar algorithms since that will create memory leaks in that case the correct algorithm is partition .

Quote:

Original post by crocomire I think sorting a vector is much faster than sorting a list, or am I wrong?

it depend on which sort algorithm you use, list has it's own sort method.

Quote:

Original post by crocomire So I need fast soring and fast arbitrary removing of elements.

list is better than vectors for insertion & deletion in arbitarty places.

The other alternative is to use a container that is always sorted, std::set (as is std::map) is implemented with a red-black tree, there is also an STL extension for red-black tree container type but its not in the c++ standard currently.

Quote:

Original post by snk_kid Quote: Original post by crocomire I think sorting a vector is much faster than sorting a list, or am I wrong? it depend on which sort algorithm you use, list has it's own sort method. Quote: Original post by crocomire So I need fast soring and fast arbitrary removing of elements. list is better than vectors for insertion & deletion in arbitarty places. The other alternative is to use a container that is always sorted, std::set (as is std::map) is implemented with a red-black tree, there is also an STL extension for red-black tree container type but its not in the c++ standard currently.

So sorting a list can be as fast as sorting a vector?
I only need to delete arbitrary elements. New elements can be inserted at the end.

I think I'll try remove_if, as has been suggested here. Does remove_if take O(n) time for n removals from a vector?

Btw, great forum

remove_if runs in linear time so yes it's O(n) but be sure that you've read and understood what I said about using partition.

Quote:

Original post by crocomire So sorting a list can be as fast as sorting a vector? I only need to delete arbitrary elements. New elements can be inserted at the end.

Sorting a list is often faster, especially if you have large types in the vector. In a vector, memory is in one chunk, so deleting the first object causes all the memory after it to be shifted one unit down.
Now, if you don't need your vector sorted, you can swap the element being removed with the last element, and remove it. That way theres no memory copying. But you need sorting, so that doesn't really help :P

Sorry, no idea about your other question.

The speed of vector versus list will depend on the stored type, and whether it has a swap function.

Quote:

Now, I'd like to test each element of this vector for a certain condition. If this condition fails I'd like to remove this element. After each element has been tested I will insert a number of new elements in the vector that is about the same as the removed elements. What is the most efficient way to do this?

Do you mean that after deleting some elments you will add some new elments to the vector? If order is not important you could replace the 'to be deleted' items with 'to be inserted' items as you walk through the vector.

One possibility/idea to make it faster is to use equal_range (a version of binary search so talking logarithmic time) instead of remove_if then use the returned pair of iterators to erase the range e.g.

#include <algorithm>#include <iterator>#include <list>#include <iostream>int main() {    typedef std::list<int> int_con;  typedef std::pair<int_con::iterator, int_con::iterator> pair_of_itrs;  int_con ints;  ints.push_back(10);  ints.push_back(3);  ints.push_back(3);  ints.push_back(3);  ints.push_back(5);  ints.sort();    pair_of_itrs result = std::equal_range(ints.begin(), ints.end(), 3);  ints.erase(result.first, result.second);  std::copy(ints.begin(), ints.end(),            std::ostream_iterator<int>(std::cout, ", "));}

but the container needs to be sorted first, or change it little and use a container thats always sorted:

#include <algorithm>#include <iterator>#include <set>#include <iostream>int main() {    typedef std::set<int> int_con;  typedef std::pair<int_con::iterator, int_con::iterator> pair_of_itrs;  int_con ints;  ints.insert(10);  ints.insert(3);  ints.insert(3);  ints.insert(3);  ints.insert(5);  pair_of_itrs result = std::equal_range(ints.begin(), ints.end(), 3);  ints.erase(result.first, result.second);  std::copy(ints.begin(), ints.end(),            std::ostream_iterator<int>(std::cout, ", "));}

weather this will work/fit in your context depends on what type your going to store and the conditional you where originally using (equal_range is also overload to take a comparator) probably means it wont so remove_if is the way to go.

Thanks for all the suggestions!
My current solution using swap: