
9 Nov
2009
9 Nov
'09
9:50 p.m.
So the rationale is to ensure that only add operations perform a resize and so that sequential pop() operations don't incur excessive resizing costs.
I agree that the use case of repeated .pop() operations is reasonable, and (IIUC) that case is also special-cased using a finger/index.
I think for regular removal, the same logic should not apply: if a series of removals is performed, then further (non-pop) removals see increasing costs, as do regular lookups. So I think that a removal should trigger shrinking (with appropriate thresholds) unless it's a .pop.
Regards, Martin