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?

CodePudding user response：

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();
}