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

[Gino v. d. B. <gin...@gm...>]

On 23-3-2010 10:34, Fabian Giesen wrote:
> Jon Watte schrieb:
>    
>> <snip>
>> 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).

I totally agree. Even with a custom allocator an std::list breaks cache 
coherence and simply has too much overhead. I would not use std::swap 
though, since x is a goner so no need to save it to back(). Instead do

std::vector<Entry>::iterator it;

...

Entry&  x = *it; //  it points to the item that needs to be destroyed, e.g.

                         // it = std::find(container.begin(), container.end(), victim);

x = container.back();

container.pop_back();


This saves you two writes since std::swap needs to create a temporary to 
hold one of the swapped values. The extra writes are better avoided if 
the size of Entry is huge or if it holds shared pointers.


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

I think you mean

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


since the STL remove takes three parameters. Furthermore std::remove 
keeps the relative order intact. 
http://www.cplusplus.com/reference/algorithm/remove/
At least, that is what I see in Visual C++ 8.0 (Sometimes they do adhere 
to standards ;) Removing all values and leaving an unordered sequence 
can be done using

std::vector<Entry>::iterator it = container.begin(), last = container.end();

while (it != last)

{
     if (*it == value)

     {

         --last;
         *it = *last;
     }
     else
     {
         ++it;
     }
}

container.erase(last, container.end());


Gino