2

I am doing a game where I create objects and kill them frequently. I must be able to loop the list of objects linearly, in a way that the next object is always newer than previous, so the rendering of the objects will be correct (they will overlap). I also need to be able to store the pointers of each object into a quadtree, to quickly find nearby objects.

My first thought was to use std::list, but I have never done anything like this before, so I am looking for experts thoughts about this.

What container should I use?

Edit: I am not just deleting from the front: the objects can be killed at any order, but they are always added in the end of the list, so last item is newest.

Rookie
  • 4,064
  • 6
  • 54
  • 86
  • 3
    *loop the list of objects linearly* -- this is a tautology, I believe? How about a `queue`? Also, what order do you follow when killing off objects? Is it LIFO/FIFO/Maximum element or some such thing? – dirkgently Jun 19 '12 at 12:37
  • 2
    you can check out this STL [flowchart](http://i.stack.imgur.com/kQnCS.png). Just to get a reference its useful. ![enter image description here](http://i.stack.imgur.com/HHW3Z.png) – WeaselFox Jun 19 '12 at 12:43
  • It's outdated and there was a question on a newer version for C++11, unfortunately I cannot find it any longer... If anyone could find the question back, it would be great. – Matthieu M. Jun 19 '12 at 12:54
  • @dirkgently, i kill objects at random order. – Rookie Jun 19 '12 at 13:26
  • IMO, there is too little information at hand. How would you put the constraints on your individual operations? If it's okay, what amortized cost are you okay with? Do you think a `deque` may suit your needs? – dirkgently Jun 19 '12 at 13:34
  • Not directly related to your question, but you may want to recycle your objects instead of constantly creating and deleting them. Using some kind of object pool may help improve performance. http://en.wikipedia.org/wiki/Object_pool_pattern – Emile Cormier Jun 19 '12 at 13:36
  • @EmileCormier, i cant recycle because the order of the objects must be time-sorted, so the rendering will be correct. – Rookie Jun 19 '12 at 13:38
  • @dirkgently, im not sure what else i can tell...i dont think deque fits since i delete at random places, and the order must be time-sorted for correct rendering. – Rookie Jun 19 '12 at 13:39
  • @Rookie : I'm not talking about marking the object as deleted in your container. I'm talking about objects going back to a free list (pool) instead of being deleted. When you need to create a new object, it gets one from the free list instead of allocating it from the heap. Once you've retrieved an object from the free list, you re-initialize it to a usable state (e.g. set the proper time stamp). Dynamically allocating objects from the heap can be a surprisingly slow operation. – Emile Cormier Jun 19 '12 at 13:47
  • @MatthieuM. Are you thinking of [this question](http://stackoverflow.com/questions/10699265/how-can-i-efficiently-select-a-standard-library-container-in-c11)? – Blastfurnace Jun 19 '12 at 15:07

3 Answers3

2

std::vector is the recommended container to start with when you're not sure what you're doing. Only when you know that's not going to work for you should you choose something else.

That said, if you're regularly adding to the back of the container and deleting from the front, you probably want std::deque. [Edit] But it appears that's not what you're doing.

I'm thinking you might want two containers, one to maintain the insert order and one for your quadtree. There are lots of quadtree implementations on the Internet, so I'll focus on the other one. Using std::list as you suggest will make the delete operation itself faster than vector or deque. It also has the advantage of letting you store iterators, because list won't invalidate the other iterators when an element is removed. Your objects in the quadtree could maintain an iterator into the insert order list. When you remove an element from the quadtree, you can remove it from the list too in O(1) time.

As always, the decision about which container to use is all about tradeoffs. A list comes with increased memory footprint over vector and the loss of contiguous memory layout. You might be surprised how much cache locality matters when your data set is large. The only way to know for sure is to try various containers and see which one runs the best for your application.

Michael Kristofik
  • 34,290
  • 15
  • 75
  • 125
  • I do use vector already, but it will waste a lot of memory because the render order must follow the time the object was added in it. And not just memory, it will get a lot slower when i am looping through million items in that list which are set to `dead`. I am not just deleting from the front, in what kind of game that would happen...? – Rookie Jun 19 '12 at 13:09
  • "Only when you know that's not going to work for you" - which we do know, because we need pointers to elements to remain valid when elements are added/removed from the container. – Steve Jessop Jun 19 '12 at 13:22
  • I've updated my answer with some comments on `std::list`. The choice of container is all about tradeoffs. A good standard library reference will cover those. Without knowing exactly what your program is doing, we can only guess at what might perform better. I think your best bet is it try it out and see what happens. And then let us know what you learned. :-) – Michael Kristofik Jun 19 '12 at 13:22
  • @SteveJessop, what's wrong with a vector (or *any* container) of `std::shared_ptr`? – Michael Kristofik Jun 19 '12 at 13:23
  • @MichaelKristofik, Imagine a game where objects appear at random times, and you shoot them at random positions by random times. In addition to that, i should be able to use quadtree to optimize the search for nearest object. AND the objects will overlap at some times, but that overlapping must be time-sorted, so two objects created in sequence next to each other, must overlap each other in that correct order too. – Rookie Jun 19 '12 at 13:24
  • @Michael: should be OK, but I (mistakenly) thought you were ruling it out by talking about the importance of contiguity. – Steve Jessop Jun 19 '12 at 13:26
  • @SteveJessop, I was imagining a "cull step" at the end of the OP's game loop, i.e., spinning through the container and removing all `dead` elements. The contiguous memory layout of vector is going to help that operation be fast, even though we'll be removing from the middle. All I'm saying is don't knock vector until you've tried it. :-) – Michael Kristofik Jun 19 '12 at 13:34
  • Updated my answer again with more ideas, trying to fold in what everyone has said so far. – Michael Kristofik Jun 19 '12 at 13:44
1

I think boost::stable_vector fits your needs for deletion\iteration.

Viktor Sehr
  • 12,825
  • 5
  • 58
  • 90
0

So, you want to be able to iterate through through your container in the order in which the items have been added, but you want to be able to remove items from any point in the container. A simple queue obviously isn't going to hack it.

Happily, there are 4 containers that will do this job easily enough, std::vector, std::list and std::deque and std::set. If you use standard container idioms (eg. begin, end, erase, insert, and to a lesser extent, push_front, pop_back, front, back) you can use whichever container you felt like. With those 8 operations, you could switch between std::vector, std::list and std::deque, and with just the first 4 you could use std::set, too. Write your code, and then you can easily chop and change between the different container types and do a little profiling to compare performance and memory overheads or whatever.

Intuitively, std::list is probably a good bet, and perhaps std::set would work too. But rather than making assumptions, just use the general tools the template library gives you, and profile and optimise things later when you have some meaningful performance data to work with.

Rook
  • 5,734
  • 3
  • 34
  • 43
  • I have added more information to my edit, im not sure what else I need to tell. Imagine a game where appears objects at random intervals, then you shoot them at random positions, but the render order of the objects must follow the time when they were added, so i cant render it in random order or the rendering will look too random when the very frequently added and nearby objects will overlap. And these objects should be accessible via quadtree. – Rookie Jun 19 '12 at 13:15
  • The quadtree requirement is secondary because it has nothing to do with the workings of your render-order container. You just need to make sure that when you add or remove an item from one of the containers, you do the same to the other container too. – Rook Jun 19 '12 at 13:37