2

Background: I want to implement a 3-d collision detection algorithm and would like to fragment the search space into cubes so that I only check for collisions when objects are close enough.

Actual Question: I was thinking of using an array of vectors to store pointers to the objects I am going to iterate over. For example box[0][0][0] would be a vector holding pointers to the objects in one corner of the simulation space. Regardless of whether this is an optimal solution, I am wondering how c++ handles arrays of vectors. Would the array hold pointers to the vectors so that their subsequent re-allocation have no effect on the validity of the array, or would the vectors be created inside the array and then moved out, causing undefined behavior?

Similar questions did not have answers specific to this implementation detail. Sorry if this is actually answered elsewhere and I missed it.

patatahooligan
  • 3,111
  • 1
  • 18
  • 27
  • If you are using vectors then use a vector to hold the vectors. You could also use `std::array` if you know what the size will be at compile time. – NathanOliver Mar 20 '15 at 13:28
  • 1
    The question is more about how vectors are stored in memory and not how I will implement this specific project, but thanks for the suggestion. – patatahooligan Mar 20 '15 at 13:34
  • The only trouble with the 3d array idea is that it has a very poor worst case performance. Worst case is where everything in the simulation is in box[x][y][z] and all other boxes are empty. Depending on the number of entities in the domain and their relative sizes, you might consider just a single flat array rather than trying to partition space. – Robinson Mar 20 '15 at 13:39
  • The spheres I'm using tend to spread out evenly in the x and z axis, but not on the y axis (because they eventually and up on the floor) so I think a 2-d partitioning is the best solution. However, the question that arose is actually about how an array of vectors would behave and not the best way to solve this problem. That would warrant a question of its own. – patatahooligan Mar 20 '15 at 13:44

2 Answers2

1

An STL vector holds a pointer to a heap buffer that contains the actual data. This allows the vector to resize the buffer on demand without invalidating the vector object itself. (See documentation of vector)

So, to answer your question. An array of vectors will not become invalid if one of the vectors needs to be resized. An array of pointers to vectors would also not become invalid if one of the vectors needs to be resized.

Lemming
  • 4,085
  • 3
  • 23
  • 36
  • So the array would hold Vector objects which themselves hold pointers to the actual data? So then, I can expect the Vector object to never allocate, right? It doesn't seem to say so explicitly in the link you shared, though it makes sense. – patatahooligan Mar 20 '15 at 13:42
  • 1
    @patatahooligan: the vector might reallocate its internally used heap memory causing the iterators to get invalid but the vector itsef will be valid always. see [iterator invalidation rules](http://stackoverflow.com/questions/6438086/iterator-invalidation-rules) – stefan Mar 20 '15 at 14:38
1

In STL a vector is an implementation of a dynamic array ( an array that can be resided on the fly). This essentially means that the array is dynamically allocated, and the user gets a pointer to the array on the heap. When more space is needed, a new array is allocated (usually double of it's previous size), the contents of the old one is copied over and the old array freed. And that is how data consistency is handled.

Now, when you have a array of vectors, statically allocated like the question shows, you have in memory (stack, or .data section, depending where you declare this array) an or 3 vector objects, allocated one after the other in memory, each one will hold a pointer to the an array allocated on the heap.

I hope this answers your question.

Pandrei
  • 4,843
  • 3
  • 27
  • 44