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.

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.

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*

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...

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);
				parent->addObject(o);
				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);
				parent->addObject(o);
                                // This line is no longer necessary, either
				//if ( it == objects.end() ) break;
			}
                        else
                        {
                                ++it;
                        }
		}
		return;
	}