Re: [Algorithms] Cache-coherent hashing for broad-phase collision detection

[Fabian G. <f.g...@49...>]

Jon Watte schrieb:
> std::set<> is not the right solution. If there are only every a few 
> elements in each bucket, I suggest using a std::vector<> and just search 
> it linearly. Each element is 8 bytes, so 8 elements fit in a single 
> cache line.
> If you have buckets with zillions of items (a bad idea for other 
> reasons) and need to delete from the middle, try a std::list<> with a 
> custom allocator, or as others have said std::hash_map or similar.

Linked lists enforce a particular order. Whenever you have something 
that is just a "bucket of things" with no particular ordering 
requirements, a good option is to just use a std::vector<> (or, more 
generally, any array - this is not STL specific). To insert, you always 
use push_back. To remove a given item "x", you do:

   std::swap(x, container.back());
   container.pop_back();

This doesn't preserve order, but it's simple, short and fast: insertion 
is amortized O(1) with std::vector semantics, and removal is guaranteed 
O(1). STL also offers this as an algorithm: there's std::remove and 
std::remove_if. Their usage is somewhat nonobvious: you do

   container.erase(std::remove(start, end), container.end());

to remove everything in [start,end) in a "non-order-preserving" way, and 
similar with remove_if which uses a predicate.

-Fabian