CODEWITHSUNDEEP
c++stlcontainers
ultifinitus
ultifinitus

Reputation: 1893

STL Container, Speed of Creation/Destruction

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 =]

Upvotes: 0

Views: 557

Answers (2)

James McNellis
James McNellis

Reputation: 355069

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

Upvotes: 2

Nicol Bolas
Nicol Bolas

Reputation: 473447

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.

Upvotes: 1

Related Questions