Quote:Original post by Damocles
But if I used list<Particle> then every time I added a particle to the list, it would be copying the entire contents of the particle class each time. The whole reason I used list in the first place is for fast insertion/removal. By using Particle* I am adding another layer of indirection, but I'm removing the copy time for insertion/deletion.
A list is intended just for that - it does not relocate elements, and removal/addition do not relocate anything. It is a linked list. A std::list is not what List interface is in Java or C#. It is (doubly) linked list.
A std::list of pointers is rarely if ever needed, unless list itself is merely a proxy to elements stored elsewhere, so that it is merely a temporary structure. But a std::list that owns the elements, should be holding values. Usual exceptions for polymorphic types apply.
A vector of pointers is more useful, but for particles in particular it many not be needed.
Quote:I'm not sure that swapping the vector positions so the particle is at the end then popping back would be faster than simply removing a node in an std::list. That is of course when the list is just pointers - it would be plenty faster if it was allocating all the data in the particle.
Due to purely hardware reasons (memory cache), this operation will outperform non-continous memory in many cases, even when particles are big (< 96 bytes). This is not a C++ issue, but a consequence of current CPU/memory designs.
Memcpy (which is what is often the case with particles) can copy 1-4 bytes per cycle (depends a lot) when memory is continuous. Dereferencing a pointer however can cause various cache misses and branch stalls (again, depends a lot), which can cost several hundred CPU cycles (yet again, depends).
So in extreme theoretical case, it may be cheaper to copy several hundred bytes than to move pointers. In practice, the difference will be smaller. For reasonably-size particles, in practice, it will be about factor of 2 for typical use of such structures.
Quote:And by the way, a container of pointers is *always* wrong, period.
Unless container needs to hold polymorphic classes, in which way it cannot reasonably be implemented in any other way.