Improve insert/emplace robustness to self insertion

Jonathan Wakely jwakely@redhat.com
Wed Jul 6 22:13:00 GMT 2016


On 06/07/16 21:46 +0200, François Dumont wrote:
>On 05/07/2016 12:47, Jonathan Wakely wrote:
>>On 04/07/16 15:55 +0100, Jonathan Wakely wrote:
>>>I'm getting nervous about the smart insertion trick to avoid making a
>>>copy, I have a devious testcase in mind which will break with that
>>>change. I'll share the testcase later today.
>>
>>Here's a testcase which passes with libstdc++ but fails with libc++
>>because libc++ doesn't make a copy when inserting a T lvalue into
>>std::vector<T>:
>>
>>#include <vector>
>>#include <memory>
>>#include <cassert>
>>
>>struct T
>>{
>> T(int v = 0) : value(v) { }
>> T(const T& t);
>> T& operator=(const T& t);
>> void make_child() { child = std::make_unique<T>(value + 10); }
>> std::unique_ptr<T> child;
>> int value;
>>};
>>
>>T::T(const T& t) : value(t.value)
>>{
>> if (t.child)
>>   child.reset(new T(*t.child));
>>}
>>
>>T& T::operator=(const T& t)
>>{
>> value = t.value;
>> if (t.child)
>> {
>>   if (child)
>>     *child = *t.child;
>>   else
>>     child.reset(new T(*t.child));
>> }
>> else
>>   child.reset();
>> return *this;
>>}
>>
>>int main()
>>{
>> std::vector<T> v;
>> v.reserve(3);
>> v.push_back(T(1));
>> v.back().make_child();
>> v.push_back(T(2));
>> v.back().make_child();
>>
>> assert(v[1].child->value == 12);
>> assert(v[1].child->child == nullptr);
>>
>> v.insert(v.begin(), *v[1].child);
>>
>> assert(v[0].value == 12);
>> assert(v[0].child == nullptr);
>>}
>>
>>The problem is that the object being inserted (*v[1].child) is not an
>>element of the vector, so the optimization assumes it is unchanged by
>>shuffling the existing elements. That assumption is wrong.
>>
>>As far as I can see, this program is perfectly valid. It's slightly
>>contrived to prove a point, but it's not entirely unrealistic code.
>>
>>
>Don't you plan to add it to the testsuite ?

Yes, I'm just very busy with other things, I've only been doing
anything on std::vector so you're not waiting too long for responses
:-)

>On my side I rebase part of my patch to reorganize a little bit code. 
>I reintroduced _M_realloc_insert which isolates the code of 
>_M_insert_aux used when we need to reallocate memory. So _M_insert_aux 
>is used only when insertion can be done in place. It is a nice 
>replacement for _M_emplace_back_aux that have been removed. In most of 
>vector modifiers we start checking if we need to reallocate or not. 

Great, I was thinking of doing that kind of refactoring.

I'll review it ASAP.



More information about the Gcc-patches mailing list