CODEWITHSUNDEEP
c++containers
Barış Uşaklı
Barış Uşaklı

Reputation: 13532

Is storing pointers in std::vector ruining it's advantage of continuous memory storage

std::vector stores it's elements continuously in memory as opposed to std::list. This gives the std::vector better performance when iterating over the elements as everything is neatly packed vs jumping all around the memory when iterating a std::list.

Problem is most of the time I store smart pointers in vectors for polymorphism or for sharing these objects with other parts of the code. Since each object is now allocated dynamically I assume they end up in different memory locations. Is this defeating the purpose of using a std::vector and essentially turning it into something like a std::list? Is there anything that can be done to fix this?

Upvotes: 5

Views: 769

Answers (3)

yngccc
yngccc

Reputation: 5684

std::vector would still have locality advantage compare to std::list as you iterate through it and call some virtual methods on each polymorphic object.

now since you are potentially calling different functions each time, it is a good idea to sort the objects by their actual type, to avoid instruction cache miss.

Upvotes: 0

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275385

No, it isn't pointless.

When iterating over a std::list of possibly smart pointers, you jump to nearly random points in memory on each iterator increment. When accessing, you again jump to a nearly random point in memory.

If you did the same iteration-access in a std::vector of possibly smart pointers, you would only jump to a nearly random point in memory once.

How can you make this less painful?

If you are using a std::shared_ptr, remember to do std::make_shared so the ref counter and the data are in the same allocation, reducing cache misses.

If you are just using it for polymorphism, in theory you could instead store something like a boost::variant (or a union of the various types together with something that says what the type is), which permits multiple types of variables to exist at the same address (one at a time, naturally).

Upvotes: 1

CrazyCasta
CrazyCasta

Reputation: 28302

I would argue that the biggest advantage of std::vector over std::list is that indexing is an O(1) instead of O(n) operation. What you're talking about is a more second order optimization. Also, you're always free to store your own objects all in one big array and then you wouldn't be jumping around as much (if cache purposes is what you're thinking about).

Upvotes: 4

Related Questions