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

Neal D. Becker ndbecker2 at verizon.net
Tue Aug 10 17:37:38 CEST 2004

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.

More information about the Cplusplus-sig mailing list