[poll] anyone else needs fast random element access off a dictionary?

[David Eppstein]

In article <Xns932069D1BE484duncanrcpcouk at 127.0.0.1>,
 Duncan Booth <duncan at NOSPAMrcp.co.uk> wrote:

> He was suggesting that instead of deleting an item from the end of the list 
> you replace it with the element at the end of the list and drop the element 
> off the end of the list. If you do it that way you do indeed get O(1) time 
> to drop an element from a list. You change the order of elements in the 
> list, but that isn't important here.

This will work even better than the lazy deletion I suggested when the 
order isn't important.

-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/