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

> 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).

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.

> 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.