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

[David Blaikie]

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.