Is std::vector good for frequent resizing?

Question

I am creating a game where i have small "particles". Their number is changing very frequently (every few seconds) and i'm wondering what is the best way to store them. Is std::vector or std::deque better for this?

Is it okay to reserve space (in that container) that will never get used (I have upper limit)?

Answer 1

Instead of removing a particle you can just replace it with the other one in a vector if order does not matter (and I think it does not)

std::vector<Particle> particles;

when you remove a particle at index i - just fill the empty space with the last one:

particles[i] = particles.back();
particles.pop_back();

You can make it even faster if using vector of pointers.

Answer 2

If you reserve enough space for the vector, resize is not bad, because it doesn't need to copy the vector's content.

One the other hand, dequeue can grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocations are avoided.

Answer 3

It really comes down to usage. If your vector is unsorted, if you are actually removing that particle, it has complexity O(n) to find it within your vector and the whole vector will be copied so the data remains contiguous. With a deque, it still takes O(n) to find, but removal is trivial. However, if you are iterating like

foreach (particle in particles)
{
    if(particle.update() == END_OF_LIFE)
    {
        particle.alive = false;
    }
    else
    {
        particle.draw();
    }
}

you can do it with no significant overhead, but to insert new particles you will either need to iterate through each particle to find the first 'dead' one you can replace (O(n)), or keep track of that information in a separate std::list.

One thing we need to know to effectively answer - do you ever need to index to a particular particle ("give me the 1000th particle in the list")? Also, do you ever look up by some ID ("find the particle with id=421932")? If the former, vector performs that in constant time, whereas the latter would be performed in constant time by an std::unordered_set (c++ x11 version of hash_set, similar options in boost pre x11) and logn time by std::set.