Re: Cache-coherent hashing for broad-phase collision detection

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

------------------------------------------------------------------------------
Download Intel&#174; Parallel Studio Eval
Try the new software tools for yourself. Speed compiling, find bugs
proactively, and fine-tune applications for parallel performance.
See why Intel Parallel Studio got high marks during beta.
http://p.sf.net/sfu/intel-sw-dev
_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list