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

[David Abrahams]

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

-- 
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com