STL Container, Speed of Creation/Destruction

Question

Background: I am creating an efficient(hopefully) collision detection system for my game engine- it's introduced a slight problem when I place large amounts of objects on the screen. My problem is this:

I will be adding and removing objects regularly and I have several manager classes that keep track of the objects at any given time which means a lot of adding and removing these objects from containers. I've been using vectors and deques for most of this, which is fine, however I would greatly like to upgrade the core speed of the system.

Thus the question: Which container ((STL or not) [preferably the former]) gives me the quickest (order doesn't matter) addition, removal, and random access of elements?

I have been thinking that I'll use a set, I will iterate through the elements, though not as often as I'll be utilizing the other three functions.

Additional Info: essentially I'm splitting my screen into a grid of undefined size, and when an object moves I'm going to find the square that the upper left corner is currently in, then the lower right corner (assuming object is squareish of course) thus I'll know all current grid positions the object occupies. When I do collision detection, I'll only run checks on the grid positions with more than one object, when I check for collisions it will hopefully be much faster than my previous system =]

What do you mean by 'undefined' size? Potentially infinite? Resizes while running, or just size chosen at runtime? The first two are harder to make fast... — Simon Buchan, Jun 23 '11 at 02:36
Undefined size of the particular square size, to be defined before utilizing the collision system (so before a game starts) and I'm currently thinking my plan will be the exploitation of the most common size. (for most of my games 32x32 px) The size of the map will *potentially* be infinite, however there will most certainly be a practical limit.. — ultifinitus, Jun 23 '11 at 02:41
You're more likely to see a performance improvement by using a faster memory allocator than by switching containers. — ildjarn, Jun 23 '11 at 02:58
Well I suppose I'll do a little more research on memory allocators then, thanks for the pointer. (no pun intended) — ultifinitus, Jun 23 '11 at 03:27
Read this: http://stackoverflow.com/questions/181693/what-are-the-complexity-guarantees-of-the-standard-containers — Martin York, Jun 23 '11 at 03:35

James McNellis · Accepted Answer · 2011-06-23T02:58:47.833

2

std::set is unlikely to offer better performance: it is a node-based container, so each element requires a dynamic allocation, which can prove expensive.

Consider sticking with std::vector: it offers constant-time random access to all elements in the sequence and constant-time insertion and removal at the end of the sequence.

Since you say that order does not matter, you can also get constant-time removal of any element from the middle of the sequence by moving the element from the end of the sequence to have it replace the element being removed; something like this:

void remove_element(std::vector<Entity>& v, std::vector<Entity>::iterator it)
{
    std::vector<Entity>::iterator last_element_it = v.end() - 1;
    if (it != last_element_it) {
        using std::swap;
        swap(*it, *last_element_it);
    }
    v.erase(last_element_it);
}

edited Jun 23 '11 at 02:58

answered Jun 23 '11 at 02:33

James McNellis

348,265
75
913
977

That would most certainly work, I actually hadn't thought about that! Some time ago I read a post about the same process but I shoved it into the back of my head, is there a large speed increase to use a vector rather than a deque? – ultifinitus Jun 23 '11 at 02:38
I do have a question, when I remove elements, I would like to remove the element based on the pointer, rather than element number, would you propose an additional step, or perhaps a change in container? – ultifinitus Jun 23 '11 at 02:45
It depends: in theory, [`deque` may be more performant](http://www.gotw.ca/gotw/054.htm) for many use cases. In practice, some implementations of `deque` [have poor performance characteristics](http://stackoverflow.com/questions/5574699/profiling-deque-is-23-of-my-runtime) so you have to be careful. Ideally, you should be able to write your code using templates and have your functions just require "a random access sequence of Entities," then you can easily swap in `deque` or `vector` and see which one really performs better. – James McNellis Jun 23 '11 at 02:45
If you have a pointer to an element then it sounds like order does matter since reordering the elements will move them around. Or are you storing in the container pointers to entities instead of the entities themselves? – James McNellis Jun 23 '11 at 02:47
If you're adding objects one at a time and don't know the final size, then deque probably performs slightly better than vector due to the way deque allocates its memory. – Jun 23 '11 at 02:48
Also, to remove elements based on pointer, you can call the [`erase`](http://www.cplusplus.com/reference/stl/deque/erase/) method on deque (or vector, for that matter). Yes, it's technically an iterator, but you may as well store an iterator too because both a pointer and an iterator will likely be invalidated when reallocating due to adding elements beyond its capactiy. PS: Can someone tell me how to properly embed links in comments. It's completely unobvious to me. – Jun 23 '11 at 02:50
@darvids0n: Link text in square brackets followed immediately by the hyperlink in parentheses `[text](link)` – James McNellis Jun 23 '11 at 02:52
@ James: I'm storing pointers to entities. Definitely *not* entities themselves. I'm keeping the systems separate, for flexibility and (again hopefully) efficiency. ||| @darvids0n : That I did indeed know. I'm familiar with the containers, I'm just looking for speed... – ultifinitus Jun 23 '11 at 02:54
I think you should implement this as a swap. A swap is always cheap (or should be, if you're not a silly programmer), but you have no idea how costly assignment might be. So swap the two values, then pop back. – GManNickG Jun 23 '11 at 02:56
Iterating through the vector for the element number of the object just seems ... well I can think of several ways around that- the object storing it's position in the vector or something similar, blargh. – ultifinitus Jun 23 '11 at 02:57
@GMan: I agree: swap is better. @ultifinitus: Well, if you just have the pointer, then it really depends on how many elements there are. With a (relatively) small number of elements, scanning the sequence for the element to be removed or keeping the sequence in sorted order may be fast enough. With a (relatively) large number of elements, you may need to consider some other type of container; only profiling can tell you. I'd write your algorithm first, profile it, then figure out where you can most improve the performance of the algorithm as a whole. – James McNellis Jun 23 '11 at 03:03
Alright. I'll do so. I *could* dual up with another, perhaps a map, but that **also** seems ... well ... blarghy? – ultifinitus Jun 23 '11 at 03:25
Usually, in games, when you want to remove something from a container, you want to remove a bunch of things at the same time - all the things meeting some condition (e.g. that are "dead"). Do this with the standard library algorithms `std::remove` (or `std::remove_if`) and `std::erase`. – Karl Knechtel Jun 23 '11 at 04:02
The std::algorithms are definitely going to be faster than anything my limited time and skills could come up with, certainly... – ultifinitus Jun 23 '11 at 04:15

score 1 · Answer 2 · answered Jun 23 '11 at 02:45

Which container ((STL or not) [preferably the former]) gives me the quickest (order doesn't matter) addition, removal, and random access of elements?

None of them. You have to pick which things you want.

Addition to a std::vector at the end is fast, as is removal from the end. But insertion/removal anywhere else will hurt at least somewhat.

Insertion and removal from a std::list will be very fast no matter where, but there's no random access.

A std::deque has std::vector-like insertion and removal from the beginning as well as the end, and it does have random access.

My question is this: how often do you need random access for a list of collision objects? Won't most of your operations be iterating through the list (for each object do X)? If so, I'd go for a std::list.

Alternatively, you could use a std::map, where the map's key is some kind of unique entity ID. This will give you slower insertion/deletion than std::list (due to the needs of a balanced binary tree), but you will get the ability to access an entity by identifier reasonably quickly. Which can be important.

A std::map is probably halfway between a std::vector/deque and a std::list in this regard. Slower insertion/deletion than a list, slower random access than a vector/deque, but you do get some of both.

That being said, I highly doubt that this kind of optimization will be terribly useful to you. How many of these objects are you going to have, maybe a few thousand? How often are you touching them? Do you really think that the kind of container you use will be a significant factor in your collision system's performance?

Get your collision algorithms optimized before bothering with the container for them.

The random access will be used less (in all likelihood) than the iteration through the container. *Do you really think that the kind of container you use will be a significant factor in your collision system's performance?* ... well I **did** until I read that. — ultifinitus, Jun 23 '11 at 02:51
All of these answers are good *theory*, but STL implementations have bad real world performance for non `vector<>` - for example `list<>` requires a heap allocation for each node, which can easily swamp the cost of removing elements from `vector<>`. — Simon Buchan, Jun 23 '11 at 02:52
@Simon Buchan: std::list> may require a heap allocation for each node, but you may notice that I wrote out its full name this time. If you don't want it to require memory allocation for each node, there are ways to fix that. Allocators do have a purpose, and memory access performance is at the top of that list. — Nicol Bolas, Jun 23 '11 at 03:10
of course, to support the arbitrary create/delete patterns you probably want to use `list` for, your allocator will probably need to be as complicated, and therefore as slow, as `std::allocator<>` (since you can't assume the size you will be allocating: the default of `std::allocator` is misleading, it's actually rebound `std::list::_some_node_type_`). — Simon Buchan, Jun 23 '11 at 03:55

STL Container, Speed of Creation/Destruction

2 Answers2