Jump to content

  • Log In with Google      Sign In   
  • Create Account

#ActualSillyCow

Posted 29 June 2013 - 02:13 PM

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.


#2SillyCow

Posted 29 June 2013 - 02:11 PM

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.


#1SillyCow

Posted 29 June 2013 - 02:07 PM

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.


PARTNERS