# Problem with my Quadtree - converting from std::vector to std::set

## Recommended Posts

PureSnowX    275

I recently made a dynamic quadtree for moving objects for a game I'm creating. Initially i used the std::vector to contain all objects present in the current rectangle and after some optimization and fixing stack overflow it's now working perfectly with 1000+ moving objects.

However, a friend of mine told me ( or rather a chat ) that I should be using std::set rather than std::vector because it uses less alloc/moving/resizing-calls and has improved access time.

My naive approach was simply just change all std::vector operations to be std::set, change a few loops to use iterators instead of an integer and so forth. The code in it self is exactly "the same" as the one with vectors but for some reason it's crashing inside the "Quadtree::update()" method which simply updates the quadtree which contains moving objects.

The function looks like this:

void Quadtree::update() {
if ( status == QuadStatus::BRANCH && hasLeafChildren() )
merge();

for( auto it = objects.begin(); it != objects.end(); ++it) {
if(!inBounds((*it)->getX(), (*it)->getY()) ) {
GameObject* o = (*it);
it = objects.erase(it); // THIS IS WHAT IS CAUSING THE CRASH!!!
}
}
return;
}
else
for(int i = 0; i < 4; i++) {
if(nodes[i] != nullptr)
nodes[i]->update();
}
}


Apparently it's the line "it = objects.erase(it)" that is making the program crash - here is the call stack:

0  0x00449a26  std::_Rb_tree_increment(std::_Rb_tree_node_base const*)

1  0x004ceed6  std::_Rb_tree_const_iterator<GameObject*>::operator++  c:\\mingw-4.7.1\\lib\\gcc\\mingw32\\4.7.1\\include\\c++\\bits\\stl_tree.h  269

I'm not entirely sure why ( I think it's an overflow ) but isn't std::set suppose to use LESS operations than an vector?

Kind regards, Moonkis

##### Share on other sites
SillyCow    1461

std:set does faster lookups for a specific object.

When you use a vector, which is basically an array, a lookup involves scanning the entire array. If you have 100 objects in the array, a lookup will take 100 operations (go over 100 objects until you find what you wanted).

Erasing is even worse, since in a vector, erasing something from the middle involves scanning the entire array to find it, and then copying the tail of the array over the "empty" space caused by deleting.

Sets implement either a "binary tree" or a "hash table" instead of an array (as vectors). They are able to do one item lookups and deletes very fast. The cost is that they take up more memory, and are slightly slower with other operations. But "erase a certain object" is much simpler than vectors.

If you want to understand exactly why, look up binary-trees and hash-tables on wikipedia. But your friend is basically right specifically regarding the "modeify/erase a specific item" operation. Which is exactly what you are doing here.

If you want to find out exactly what is causing the crash, run it in a debugger. I personally recommend Visual Studio, as it has excellent debug assertions on STL containers. You'll find your problem in 2 minutes.

also consider using an unordered set. If you don't need sorting, it should perform slightly better than an std::set.

Edited by SillyCow

##### Share on other sites
Cornstalks    7030

std:set does faster lookups for a specific object.

std::set is faster at determining if a specific object is in the set (because they're sorted, so a binary search can be done). However, for iterating over, std::vector is faster, because it's a contiguous block of memory that's more cache friendly. The thing is though, to lookup an object in a std::set doesn't make a lot of sense, because you have to pass it the object to look up (which means you already have the object to begin with...).

When you use a vector, which is basically an array, a lookup involves scanning the entire array. If you have 100 objects in the array, a lookup will take 100 operations (go over 100 objects until you find what you wanted).

It won't necessarily take 100. On average, it will take about 50 (assuming a randomly sorted array/vector and finding a random element (also assuming no duplicates)). Worst case is 100 comparisons. Best case is 1 comparison.

Erasing is even worse, since in a vector, erasing something from the middle involves scanning the entire array to find it, and then copying the tail of the array over the "empty" space caused by deleting.

Note that he's already iterating through the entire array, so the only extra cost of an erase() is the compacting of the data structure. In his case, there isn't really an added cost for finding the element to erase. Not necessarily. He has an iterator to the vector. Calling erase() is O(1). He's already iterating over the whole vector. The call to erase is not linear, though. It's constant time. [edit: that was embarrassing; thanks SiCrane]

Anyway, @Moonkis: unless I'm misreading/misunderstanding that stack trace, it's actually crashing on ++it. The problem is that erase() (for both vector and set) will return end() if you just erased the last element. Then the loop will try to ++it (before checking it != end()), which is undefined behavior. You need to check if it == end() (and NOT do ++it if it is).

Basically, this can be caused if your program follows this execution order:

1. auto it = objects.begin()
2. it != objects.end()
3. execute loop body
4. it = objects.erase(it); // Let's say you erased the last element and now erase() returns end()
5. ++it // It will crash here, because it == end()!
6. it != objects.end()
1. Go to #3 if true
2. Break out of the loop if false

The fact that it crashes with std::set and not std::vector is just dumb luck (or perhaps it's unlucky?). It's undefined behavior.

Also, for how your using objects, (assuming you aren't doing more with it), using std::vector will be faster. std::set is slower when it comes to iterating over, like you're doing in that loop. However, use the data structure that fits your needs best. If profiling reveals it to be too slow and problematic, then try to optimize.

##### Share on other sites
SiCrane    11839

Not necessarily. He has an iterator to the vector. Calling erase() is O(1). He's already iterating over the whole vector. The call to erase is not linear, though. It's constant time.

Only erase() at the end of a vector is O(1). The cost for erase() is proportional to how far from the end the iterator is, which means that repeated calls to erase() in a loop like this is quadratic. This is why the swap-and-pop idiom exists and why removing elements based on a condition from a vector is more efficiently done with remove_if().

##### Share on other sites
Cornstalks    7030

Not necessarily. He has an iterator to the vector. Calling erase() is O(1). He's already iterating over the whole vector. The call to erase is not linear, though. It's constant time.

Only erase() at the end of a vector is O(1). The cost for erase() is proportional to how far from the end the iterator is, which means that repeated calls to erase() in a loop like this is quadratic. This is why the swap-and-pop idiom exists and why removing elements based on a condition from a vector is more efficiently done with remove_if().

*facepalm*

##### Share on other sites
serumas    796

hi,

I am a littlebit out if space in this theme,but I can suggest you not to use quadtree for moving objects at all.

I want to suggest much simpler(smaller code, main code is about 50 lines) and faster (you dont need to update, remove and etc. operations for single object it goes automaticaly) aprouch that was created for game with lots of moving objects

testing app

http://serumas.gamedev.lt/temp/testing.zip

If you want I can share the code...

Edited by serumas

##### Share on other sites
BornToCode    1185

The thing i do not understand is that you will have to iterate through all your objects anyway withing an node, so using an std vector works better in that especially when you can pre allocated how many objects can initially be store in each node. Another option is to increase your number of objects in each node but never decrease it and reuse them. So the tree node object container only grows and does not shrink. Also another thing you can do is keep track of removing indices in the tree whenever an object moves to a different node into a stack that is part of that node that tells one which node index was moved. So the next time something moves in, you can just grab the index from the stack and use that index into your vector to insert the new object. With that you end up with 0(1) insertion for any object.

##### Share on other sites
PureSnowX    275

Anyway, @Moonkis: unless I'm misreading/misunderstanding that stack trace, it's actually crashing on ++it. The problem is that erase() (for both vector and set) will return end() if you just erased the last element. Then the loop will try to ++it (before checking it != end()), which is undefined behavior. You need to check if it == end() (and NOT do ++it if it is).

Basically, this can be caused if your program follows this execution order:

1. auto it = objects.begin()
2. it != objects.end()
3. execute loop body
4. it = objects.erase(it); // Let's say you erased the last element and now erase() returns end()
5. ++it // It will crash here, because it == end()!
6. it != objects.end()
1. Go to #3 if true
2. Break out of the loop if false

This did the trick, here is the altered code:

	if(status == QuadStatus::LEAF) {
for( auto it = objects.begin(); it != objects.end(); ++it) {
if(!inBounds((*it)->getX(), (*it)->getY()) ) {
GameObject* o = (*it);
it = objects.erase(it);
if ( it == objects.end() ) break;
}
}
return;
}


Problem is, I don't understand why "if ( it == objects.end() ) break;" is needed!

If the objects.erase() returns "end()" the for-loop should catch it before increasing the iterator, why doesn't it?

##### Share on other sites
SiCrane    11839
The condition for a for loop is checked after the increment. If you translate a for loop into a while loop:
for (a; b; c) {
body
}

becomes
{
a;
while (b) {
body
c
}
}


##### Share on other sites

Anyway, @Moonkis: unless I'm misreading/misunderstanding that stack trace, it's actually crashing on ++it. The problem is that erase() (for both vector and set) will return end() if you just erased the last element. Then the loop will try to ++it (before checking it != end()), which is undefined behavior. You need to check if it == end() (and NOT do ++it if it is).

Basically, this can be caused if your program follows this execution order:

1. auto it = objects.begin()
2. it != objects.end()
3. execute loop body
4. it = objects.erase(it); // Let's say you erased the last element and now erase() returns end()
5. ++it // It will crash here, because it == end()!
6. it != objects.end()
1. Go to #3 if true
2. Break out of the loop if false

This did the trick, here is the altered code:

	if(status == QuadStatus::LEAF) {
for( auto it = objects.begin(); it != objects.end(); ++it) {
if(!inBounds((*it)->getX(), (*it)->getY()) ) {
GameObject* o = (*it);
it = objects.erase(it);
if ( it == objects.end() ) break;
}
}
return;
}


Problem is, I don't understand why "if ( it == objects.end() ) break;" is needed!

If the objects.erase() returns "end()" the for-loop should catch it before increasing the iterator, why doesn't it?

That looks wrong to me, if you erase something the iterator is incremented twice. You want to get rid of ++it from the for(;;) line and add else ++it; if the if statement is not entered.

EDIT: Like so... (and the check for .end() isn't needed either now)

if(status == QuadStatus::LEAF) {
for( auto it = objects.begin(); it != objects.end(); /* no-op */) {
if(!inBounds((*it)->getX(), (*it)->getY()) ) {
GameObject* o = (*it);
it = objects.erase(it);
// This line is no longer necessary, either
//if ( it == objects.end() ) break;
}
else
{
++it;
}
}
return;
}


##### Share on other sites
Cornstalks    7030
Note that it might be simpler to do something like this:

// Disclaimer: there might be some minor syntactic errors in this
// First define this functor (could also be a function, if parent can be accessed globally, which I'd be concerned about)
struct CheckInBounds
{
Parent* parent; // Or whatever type "parent" really is

CheckInBounds(Parent* p) : parent(p) {
}

bool operator()(const GameObject* o) {
if (!inBounds(o->getX(), o->getY())) {
return true; // remove it
}
else {
return false; // don't remove it
}
}
};

// Then, you can do something simple like this:
auto newEnd = std::remove_if(objects.begin(), objects.end(), CheckInBounds(parent));
objects.erase(newEnd, objects.end());