[C++-sig] Re: Optimize vector_indexing_suite set_slice

[Neal D. Becker]

David Abrahams wrote:

> Joel de Guzman <joel at boost-consulting.com> writes:
> 
>> David Abrahams wrote:
>>
>>> Joel de Guzman <joel at boost-consulting.com> writes:
>>> 
>>>>Neal D. Becker wrote:
>>>>
>>>>
>>>>>vector_indexing_suite set_slice does: 1) erase 2) insert
>>>>>Shouldn't this be optimized to simply do copy?
>>>>
>>>>You mean this:
>>>>
>>>>     container.erase(container.begin()+from, container.begin()+to);
>>>>     container.insert(container.begin()+from, v);
>>>>
>>>>Pardon me for being slow, but how? Could you spell it out for me?
>>> It's not as simple as "copy", but if you think hard about it you can
>>> see how to avoid any redundant moves or copies.  The pseudocode is
>>> complicated so I'm not writing it out in full here, but:
>>> if new_size <= old_size:
>>>    erase(old_finish + (new_size - old_size), old_finish)
>>>    if new_size < old_size:
>>>       copy(new_start, new_finish, old_start)
>>> else:
>>>    # fill in the details here
>>
>> I see. Yeah, same ol' buffer management. Ok, I'll optimize it.
>> But it'll have to be after 1.32. Ok?
> 
> Sure thing.
> 

Just to clarify a little:

1. wrapping std::vector is useful for c++ algorithms intended for efficient
processing of relatively large data vectors.

2. This doesn't inherently give any way to directly reference a slice of
data.  More code has to be written if you want to say from python "compute
function F on a slice of vector V".

3. This limitation (lack of optimization to operate directly on slices) may
not be very important in many cases, you could just do:
  Suppose we have a a vector v, and want to modify a slice of v using alg F:

  w = F (v[2:4]) # compute result from slice
  v[2:4] = w #splice in result

4. But it's even worse than it looks, because the "splice in result" will
actually call erase and insert, instead of just copy.