I have a game which could have a million "boxes". For convenience, I use std::vector<shared_ptr<Boxes>> to save them. But today, I want to break some "box" if the box is subjected to a certain impact, so I have to split the box into "two small boxes".
Here is the question - in the game, there are so many "boxes" that would break which involves the std::vector insert (new small boxes generated) and delete (old boxes split). And each "box" contains many information like mass, shape, volume, and so on. So, I have no idea about enhancing performance of the std::vector for frequent inserts and deletes. And it is difficult for me to change to another data structure that I have to keep using std::vector.
I had read some efficient trick to use std::vector like: use reserve() before inserting elements to avoid reallocating memory, or maybe move semantic can be used here?
Starting from an empty data structure:
std::vector<std::shared_ptr<Box>> boxes;
We can reserve capacity for 2 million boxes. This is probably too much, but allows for each box to be split once:
boxes.reserve(2_000_000);
Now, at the start of the game you can use push_back to fill up this vector.
At some later point, you decide you want to break a box in two. You can replace the original box with one of the fragments, and push_back the other one:
void breakBox(int i) {
std::shared_ptr<Box> fragment1 = ...; // something that reads from boxes[i]
std::shared_ptr<Box> fragment2 = ...; // something that reads from boxes[i]
boxes[i] = fragment1;
boxes.push_back(fragment2);
}
Simply adding boxes is still O(1) as long as you stay under the 2M boundary. Otherwise you incur a copy of the full boxes vector and then you are good for quite a while again.
Finally, should you ever want to remove a box, you can use a trick mentioned in the comments: swap it with the last box and then free the last box. This is O(1).
void deleteBox(int i) {
std::swap(boxes[i], boxes.back());
boxes.pop_back();
}