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

[Duncan P. N. Exon Smith]

> On 2014-Jul-15, at 09:38, David Blaikie <dblaikie at gmail.com> wrote:
> 
> On Tue, Jul 15, 2014 at 9:31 AM, Duncan P. N. Exon Smith
> <dexonsmith at apple.com> wrote:
>> 
>>> 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).
> 
> Yeah, at a glance it doesn't seem especially painful to design out -
> maybe 10 lines of code.

Great.  The `remove_if()` would probably be about the same (excluding tests), so
if this is ever the "right" approach, it might still be worth it.