   fastest possible container for pushing, popping and iterating "game objects"
  Hi, I'm developing a simple wrapper for bullet and I was curious if there was a faster container for adding, looking and removing elements than say an std::list.I'll be adding and removing game objects to this list whether whether they begin or end a contact collision, so it quite intensive cause its per frame...I was just about to do it with a list but since this is very common in game programming I just wanted to know what you guys thought.Thanks.[Edited by - toglia on May 11, 2010 3:34:00 PM]
  Vector, array, Erase remove, fixed, pre-allocated, perhaps stack-allocated storage.   ;  std::list is terrible for this, almost everything is faster.  It has terrible cache access patterns, uses excess memory since you have to contain pointers to individual elements, and doesn't allow random access, which you might want.Use a simple array.  It's fast for everything.  Linked lists have the advantage that can hold arbitrarily many items whereas if you get too many items to hold in an array you have to re-allocate and copy the old items over.  You can achieve a similar effect by using a collection of arrays of a fixed size.  Let's say you decide one array holds 1024 items.  When you need to insert the 1025th item, you just create a *new* array of 1024 items and keep a list of arrays.   Later on, say you want to access the k'th item.  You use k / 1024 to determine which array you need to access, and k % 1024 to figure out which element of the resulting array you want to access.  ;Quote:Original post by cache_hitUse a simple array.  It's fast for everything.  Linked lists have the advantage that can hold arbitrarily many items whereas if you get too many items to hold in an array you have to re-allocate and copy the old items over.  You can achieve a similar effect by using a collection of arrays of a fixed size.  Let's say you decide one array holds 1024 items.  When you need to insert the 1025th item, you just create a *new* array of 1024 items and keep a list of arrays.   Later on, say you want to access the k'th item.  You use k / 1024 to determine which array you need to access, and k % 1024 to figure out which element of the resulting array you want to access.aka std::deque   ;  When the order doesn't matter, which it typically doesn't for bullets, then using a vector in conjuction with the "swap with back() and pop_back()" trick for removal, is usually the ideal solution.   ;Quote:Original post by iMalcWhen the order doesn't matter, which it typically doesn't for bullets, then using a vector in conjuction with the "swap with back() and pop_back()" trick for removal, is usually the ideal solution.The OP isn't storing bullets, but rather information about contacting pairs as generated by the Bullet physics library.(That said, the 'vector plus swap-and-pop' advice could easily still apply.)   ;  I'm not sure about a vector, cause from what I know, vectors are basically dynamic arrays, and every time objects are pushed or popped the array is resized and some memory management might occur to maintain the memory order, making the whole process very very slow for this.On the other hand, although linked lists are faster pushing/popping objects it might be very unfriendly to cache.If you where to push or pop some 2 to 6 object pointers per frame what would you use?   ;  But once it has allocated the memory, it doesn't have to do so again until it has destroyed. It also usually allocates a larger amount each time, so the average time it takes to add a new element is pretty constant. If I'm not mistaken, the technical way to say that is that adding new elements to the back is an amortized constant-time operation.   ;  With a vector, you can reserve memory to begin with. So if you know that unless in extreme circumstances you'll never go above 50 objects in the vector at once, you call myvec.reserve (50) and it will preallocate enough memory to hold 50 objects.You can then push, pop and erase to your hearts content without having to worry about vector allocating anymore memory until the moment you try to make it store 51 objects, at which point it will create a new batch of memory big enough to hold 51 objects (more on this in a moment), copy the old objects over and delete the old memory.Most vector implementations are smart - if you hit your limit and need to allocate more memory, it wouldn't just allocate enough memory to hold one more object. It might increase the maximum number of objects it can hold by 10%, 20%, 50%, 100%, whatever. The standard doesn't dictate the maximum it can grow to, only the minimum.So your vector with 50 objects in it might be resized to hold a maximum of 75 objects, meaning once you push object 51 onto it, you can push another 24 objects before it needs to reallocate (and then might reallocate to 112, i.e. 50% extra of 75).If your vector is unsorted, the quickest way to erase an object from anywhere but the end is:1) Overwrite the object you wish to erase with the one at the end of the vector2) call pop_back, which will destruct the old version of the object you just moved.anyway, to answer your question, for small amounts of objects or when you know roughly how many need to be stored, a properly managed std::vector is probably the best solution providing your copies are lightweight.[Edited by - MENTAL on May 11, 2010 4:10:18 PM];Quote:Original post by togliaI'm not sure about a vector, cause from what I know, vectors are basically dynamic arrays, and every time objects are pushed or popped the array is resized and some memory management might occur to maintain the memory order, making the whole process very very slow for this.std::vector only grows if it needs more space. If it has 1000 elements one frame and 800 the next, nothing should happen allocation-wise. If the capacity is 1000, it will not allocate more unless you happen to push_back the 1001th element.   