CODEWITHSUNDEEP
c++pointersvector
Kai
Kai

Reputation: 2832

What's the best way to tell if a std::vector has reseated its array?

I am using a std::vector to store an array of objects that are referenced from outside of the vector by other objects. I drew a diagram to explain more clearly:

std::vector with objects being referenced

I am storing objects rather than pointers for performance reasons. These objects are sorted every frame of my game, so I want the array to have good cache properties.

Of course, whenever objects are added to the vector, there is a chance that the array will be reseated. In that case my references are invalidated and need to be updated. Right now, to detect the reseating, I am using the following method:

size_t old_capacity = v.capacity();

// Do stuff that could change the vector's size
v.push_back(a);
v.push_back(b);
v.push_back(c);

if (old_capacity != v.capacity()) {
    update_references();
}

My questions are:

Upvotes: 1

Views: 89

Answers (2)

CygnusX1
CygnusX1

Reputation: 21808

As you correctly noted, each time you add something to a vector, all existing iterators (and element pointers) may get invalidated. While you can try to "detect" that, I would strongly suggest removing the problem in a different way. Depending on your requirements you can:

  • Use indices instead of direct pointers. Instead of Obj* ptr which you would dereference by *ptr, you would have size_t idx which would be dereferenced by vector[idx]. If you have already a lot of existing code using pointers, you can try creating a smart pointer which would do that under the hood.

  • If you add, but never remove items from your vector, and if you don't care about the continuity of the data, you might not want to use std::vector at all! I think something like a list of chunks, each being - for example - a fixed array of 256 objects can suffice. You will have cache locality (because the chunk is not smaller than the cache line) and relatively cheap dynamic extensibility. In fact, if your array gets long, it may perform faster that vector, because it never reallocates memory.

  • If you add and remove items, but ordering nor continuity of the data matters, you may still use the list of chunks, with some additional manager of the removed objects, which would try to reuse the empty space when new objects are added.

Upvotes: 1

Bill Lynch
Bill Lynch

Reputation: 81976

In my mind, the best method would be the following: Just use the pointer to the head of the vector. Not all reallocations will cause the vector to move.

However, I more or less agree with the comments about references into your vector. Also, you could use a std::list which wouldn't have the problems with reallocations.

std::vector<int> v;

void *old_location = (void *) &(v.front());

v.push_back(3);
v.push_back(3);
v.push_back(3);

if (old_location != &(v.front()))
    update_references();

Upvotes: 2

Related Questions