[cfe-dev] [LLVMdev] Bug in MapVector::erase ?

Duncan P. N. Exon Smith dexonsmith at apple.com
Tue Jul 15 09:31:48 PDT 2014


> On 2014-Jul-15, at 08:29, David Blaikie <dblaikie at gmail.com> wrote:
> 
> Sounds pretty clearly buggy, and against the original design of the
> ADT (as pointed out by the documentation quotation). When was erase
> functionality added to MapVector? Can/should it be removed (and the
> use case changed to use some other container)
> 
> Making erase linear time sounds... not ideal, but possibly its
> sufficient for some/current use cases. Or we could consider other
> solutions to the use cases.

Heh -- it's already linear.  It erases from the middle of a vector.

At the least, if erasing is kept (and fixed), someone needs to update the
docs and add a unit test.

One way of speeding this up would be to erase a set of values in bulk.  I
think we could easily add a `remove_if()` function that deleted a set of
matching items in linear time, using a linear-size auxiliary array of
indices to keep state.

I'd be happy to implement this if there's a need (if you can easily design
it out, that's better).



More information about the cfe-dev mailing list