From the comments above, I understand that you want to avoid to copy the vector when you add more cells. The easiest approach is to reserve space for the maximum number of cells that you might want to have:
std::vector<YourCellType> myVectorOfCells;
vectorOfCells.reserve(maxNoCells);
Your vector has allocated space for creating maxNoCells cells but no cells have been created yet. You can now add maxNoCells to your vector, each operation in O(1)
time, without the vector copying itself. However, the C++ Standard requires the push_back operation to be amortized O(1)
time. If you add more than maxNoCells, the vector will copy itself, reserving space for k-times as many cells as it previously had (typical implementations choose a k between 1.4 and 2), so that you can keep adding cells to the vector in O(1)
time. This resizing operation is not O(1)
.
An AMR strategy begs for a dynamic data structure, like a linked-list of cells that supports insertion/deletion in O(1)
. A linked-list is, however, much slower than a vector because traversing it requires to randomly jump in memory from cell to cell, generating a lot of cache misses: in modern processors it is faster to swap $n/2$ elements of a vector in order to insert an element than traverse $n/2$ elements of a linked list. So in practice, vectors are the way to go: they are customizable (you can supply them your own allocator), your cells are aligned in memory, you have random acces in O(1)
time... as far as you reserve memory first, you can add elements in O(1) time too! As Prof. Bangerth mentioned above, hierarchical data structures like trees also use vectors internally for storing their data.
However, I think it is better practice to allocate memory at the beginning of the simulation. You have to know how many cells you can possibly need in order to check if you have enough memory available. You do not want your simulation in 200.000 processors having to reallocate your data structure or running out of memory and having to swap to disk. In case that happens my opinion is that your program should fail loudly because of an user input error.