Memory management when using vector

Question

I am making a game engine and need to use the std::vector container for all of the components and entities in the game.

In a script the user might need to hold a pointer to an entity or component, perhaps to continuously check some kind of state. If something is added to the vector that the pointer points to and the capacity is exceeded, it is my understanding that the vector will allocate new memory and every pointer that points to any element in the vector will become invalid.

Considering this issue i have a couple of possible solutions. After each push_back to the vector, would it be a viable to check if a current capacity variable is exceeded by the actual capacity of the vector? And if so, fetch and overwrite the old pointers to the new ones? Would this guarantee to "catch" every case that invalidates pointers when performing a push_back?

Another solution that i've found is to instead save an index to the element and access it that way, but i suspect that is bad for performance when you need to continuously check the state of that element (every 1/60 second).

I am aware that other containers do not have this issue but i'd really like to make it work with a vector. Also it might be worth noting that i do not know in advance how many entities / components there will be.

Any input is greatly appreciated.

Answer 1

If something is added to the vector that the pointer points to and the capacity is exceeded, it is my understanding that the vector will allocate new memory and every pointer that points to any element in the vector will become invalid.

I once wrote some code to analyze what happens when a vector's capacity is exceeded. (Have you done this, yet?) What that code demonstrated on my Ubuntu with g++v5 system was that std::vector code simply a) doubles the capacity, b) moves all the elements from old to the new storage, then c) cleans up the old. Perhaps your implementation is similar. I think the details of capacity expansion is implementation dependent.

---

And yes, any pointer into the vector would be invalidated when push_back() causes capacity to be exceeded.

1) I simply don't use pointers-into-the-vector (and neither should you). In this way the issue is completely eliminated, as it simply can not occur. (see also, dangling pointers) The proper way to access a std::vector (or a std::array) element is to use an index (via the operator[]() method).

After any capacity-expansion, the index of all elements at indexes less than the previous capacity limit are still valid, as the push_back() installed the new element at the 'end' (I think highest memory addressed.) The elements memory location may have changed, but the element index is still the same.

2) It is my practice that I simply don't exceed the capacity. Yes, by that I mean that I have been able to formulate all my problems such that I know the required maximum-capacity. I have never found this approach to be a problem.

3) If the vector contents can not be contained in system memory (my system's best upper limit capacity is roughly 3.5 GBytes), then perhaps a vector container (or any ram based container) is inappropriate. You will have to accomplish your goal using disk storage, perhaps with vector containers acting as a cache.

---

update 2017-July-31

Some code to consider from my latest Game of Life.

Each Cell_t (on the 2-d gameboard) has 8 neighbors.

In my implementation, each Cell_t has a neighbor 'list,' (either std::array or std::vector, I've tried both), and after the gameboard has fully constructed, each Cell_t's init() method is run, filling it's neighbor 'list'.

// see Cell_t data attributes
std::array<int, 8> m_neighbors;
// ...

void Cell_t::void init()
  {
     int i = 0;
     m_neighbors[i]   = validCellIndx(m_row-1, m_col-1);  // 1 - up left
     m_neighbors[++i] = validCellIndx(m_row-1, m_col);    // 2 - up
     m_neighbors[++i] = validCellIndx(m_row-1, m_col+1);  // 3 - up right
     m_neighbors[++i] = validCellIndx(m_row,   m_col+1);  // 4 - right
     m_neighbors[++i] = validCellIndx(m_row+1, m_col+1);  // 5 - down right
     m_neighbors[++i] = validCellIndx(m_row+1, m_col);    // 6 - down
     m_neighbors[++i] = validCellIndx(m_row+1, m_col-1);  // 7 - down left
     m_neighbors[++i] = validCellIndx(m_row,   m_col-1);  // 8 - left
     //                 ^^^^^^^^^^^^^- returns info to quickly find cell
  }

The int value in m_neighbors[i] is the index into the gameboard vector. To determine the next state of the cell, the code 'counts the neighbor's states.'

Note - Some cells are at the edge of the gameboard ... in this implementation, validCellIndx() can return a value indicating 'no-neighbor', (above top row, left of left edge, etc.)

// multiplier: for 100x200 cells,20,000 * m_generation => ~20,000,000 ops

void countNeighbors(int& aliveNeighbors, int& totalNeighbors)
{
  { /* ... initialize m_count[]s to 0 */ }

  for(auto neighborIndx : m_neighbors ) { // each of 8 neighbors  // 123
     if(no_neighbor != neighborIndx)                              // 8-4
        m_count[ gBoard[neighborIndx].m_state ] += 1;             // 765
     } 

     aliveNeighbors = m_count[ CellALIVE ]; // CellDEAD = 1, CellALIVE
     totalNeighbors = aliveNeighbors + m_count [ CellDEAD ];
} // Cell_Arr_t::countNeighbors

init() pre-computes the index to this cells neighbors. The m_neighbors array holds index integers, not pointers. It is trivial to have NO pointers-into-the-gameboard vector.

Answer 2

If the user is going to store pointers to the objects, why even contain them in a vector?

I don't feel like it is a good idea to (poor wording)->store pointers to objects in a vector. (what I meant is to create pointers that point to vector elements, i.e. my_ptr = &my_vec[n];) The whole point of a container is to reference the contents in the normal ways that the container supports, not to create outside pointers to elements of the container.

To answer your question about whether you can detect the allocations, yes you could, but it is still probably a bad idea to reference the contents of a vector by pointers to elements.

You could also reserve space in the vector when you create it, if you have some idea of what the maximum size might grow to. Then it would never resize.

edit:

After reading other responses, and thinking about what you asked, another thought occurred. If your vector is a vector of pointers to objects, and you pass out the pointers to the objects to your clients, resizing the vector does not invalidate the pointers that the vector hold. The issue becomes keeping track of the life of the object (who owns it), which is why using shared_ptr would be useful.

For example:

vector<shared_ptr> my_vec;
my_vec.push_back(stuff);

if you pass out the pointers contained in the vector to clients...

client_ptr = my_vec[3];

There will be no problem when the vector resizes. The contents of the vector will be preserved, and whatever was at my_vec[3] will still be there. The object pointed to by my_vec[3] will still be at the same address, and my_vec[3] will still contain that address. Whomever got a copy of the pointer at my_vec[3] will still have a valid pointer.

However, if you did this:

client_ptr = &my_vec[3];

And the client is dereferencing like this:

*client_ptr->whatever();

You have a problem. Now when my_vec resized, &my_vec[3] is probably no longer valid, thus client_ptr points to nowhere.

Answer 3

You shouldn't worry about performance of std::vector when you access its element only 60 times per second. By the way, in Release compilation mode std::vector::operator[] is being converted to a single lea opcode. In Debug mode it is decorated by some runtime range checks though.