Is std::list better than std::vector if one is storing pointers?

Question

I generally avoid std::list, but in a case where I'm storing pointers, would it be more advantageous to use a std::list since I could then randomly insert pointers without having to move all my other pointers? What advantages and disadvantages would this present over a std::vector<Some*>

Thanks

Answer 1

Since copy construction of a pointer is trivial, the decision here is not about whether one or the other is better for storing pointers but which is better for your needs.

If you really need to do lots of random inserts (and deletes?) then list could work better though it's not a simple decision - perhaps a vector with reserved space would be preferable, even then. Do you want the per-node overhead of a list just to store a pointer? On 32-bit Windows, that's 12 bytes per entry in the list, plus heap management overhead for a total of 20+ bytes per entry. This does not help data locality over time either. Meanwhile, vector uses four bytes per entry (again on 32-bit) and is guaranteed to store its elements in a contiguous block.

You have to deal with memory cleanup on erase/clear/destruction of the container either way, unless you wrap the pointer element as a smart pointer of some kind. An alternative to ease memory management of your Some*s would be one of the Boost pointer containers.

See also here for some analysis of list, vector and deque. Personally, I'm increasingly of the opinion that list is not that useful in the mainstream.