[PATCH] Optimize inserting value_type into std::vector

[PATCH] Optimize inserting value_type into std::vector

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 1390 bytes --]

	* include/bits/stl_vector.h (vector::_S_insert_aux_assign): Define
	new overloaded functions.
	* include/bits/vector.tcc (vector::_M_insert_aux): Use new functions
	to avoid creating a redundant temporary.
	* testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc: New
	test.

Tested x86_64-linux.

This improves our performance on Howard Hinnant's "insert vs emplace"
experiment at
http://htmlpreview.github.io/?https://github.com/HowardHinnant/papers/blob/master/insert_vs_emplace.html

With this small change there is no difference between emplacing or
using the relevant insert / push_back function. That also means we
beat libc++ in some cases, making us the bestest, whoo!

I originally wrote _S_insert_aux_arg functions which returned their
argument (either _Tp or _Tp&& as appropriate), relying on RVO to elide
the extra constructions, but that caused 23_containers/vector/40192.cc
to FAIL, so this patch passes the iterator into the new functions and
the assignment is done there.

Does anyone see any problem with this optimisation? I'm pretty sure
there are no cases where we actually need to create a temporary from
an expression that is already an rvalue of the correct type.

Howard's test code is CC BY 4.0, so I didn't add our usual GPL header
to the test file. I think the comments I added to the file meet the
requirements for attribution and indicating changes.


[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 14575 bytes --]

commit 22b2f2460e5508f2c993b41e31add9b10fb2794c
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Jul 29 10:10:14 2014 +0100

    Optimize inserting value_type into std::vector
    
    	* include/bits/stl_vector.h (vector::_S_insert_aux_assign): Define
    	new overloaded functions.
    	* include/bits/vector.tcc (vector::_M_insert_aux): Use new functions
    	to avoid creating a redundant temporary.
    	* testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc: New
    	test.

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index 9b6d258..ec1e884 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -1407,6 +1407,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _M_insert_aux(iterator __position, const value_type& __x);
 #else
       template<typename... _Args>
+	static void
+	_S_insert_aux_assign(iterator __pos, _Args&&... __args)
+	{ *__pos =  _Tp(std::forward<_Args>(__args)...); }
+
+      static void
+      _S_insert_aux_assign(iterator __pos, _Tp&& __arg)
+      { *__pos = std::move(__arg); }
+
+      template<typename... _Args>
         void
         _M_insert_aux(iterator __position, _Args&&... __args);
 
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 715b83e..d621804 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -342,7 +342,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus < 201103L
 	  *__position = __x_copy;
 #else
-	  *__position = _Tp(std::forward<_Args>(__args)...);
+	  _S_insert_aux_assign(__position, std::forward<_Args>(__args)...);
 #endif
 	}
       else
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
new file mode 100644
index 0000000..39a3f03
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
@@ -0,0 +1,573 @@
+// { dg-options "-std=gnu++11" }
+
+// The class X and test code is by by Howard Hinnant and used under a
+// Creative Commons Attribution 4.0 International License.
+// http://creativecommons.org/licenses/by/4.0/
+// https://github.com/HowardHinnant/papers/blob/master/insert_vs_emplace.html
+//
+// The original code was reformatted and modified to use the VERIFY macro
+// instead of writing to standard output.
+
+#include <testsuite_hooks.h>
+#include <vector>
+#include <iostream>
+
+class X
+{
+  int i_;
+  int* p_;
+
+public:
+  struct special
+  {
+    unsigned c;
+    unsigned dt;
+    unsigned cc;
+    unsigned ca;
+    unsigned mc;
+    unsigned ma;
+  };
+  static special sp;
+
+  X(int i, int* p)
+    : i_(i)
+      , p_(p)
+  {
+    //         std::cout << "X(int i, int* p)\n";
+    sp.c++;
+  }
+
+  ~X()
+  {
+    //         std::cout << "~X()\n";
+    sp.dt++;
+  }
+
+  X(const X& x)
+    : i_(x.i_)
+      , p_(x.p_)
+  {
+    //         std::cout << "X(const X& x)\n";
+    sp.cc++;
+  }
+
+  X& operator=(const X& x)
+  {
+
+    i_ = x.i_;
+    p_ = x.p_;
+    //         std::cout << "X& operator=(const X& x)\n";
+    sp.ca++;
+    return *this;
+  }
+
+  X(X&& x) noexcept
+    : i_(x.i_)
+    , p_(x.p_)
+    {
+      //         std::cout << "X(X&& x)\n";
+      sp.mc++;
+    }
+
+  X& operator=(X&& x) noexcept
+  {
+
+    i_ = x.i_;
+    p_ = x.p_;
+    //         std::cout << "X& operator=(X&& x)\n";
+    sp.ma++;
+    return *this;
+  }
+
+};
+
+std::ostream&
+operator<<(std::ostream& os, X::special const& sp)
+{
+  os << sp.c << '\n';
+  os << sp.dt << '\n';
+  os << sp.cc << '\n';
+  os << sp.ca << '\n';
+  os << sp.mc << '\n';
+  os << sp.ma << '\n';
+  return os;
+}
+
+X::special X::sp{};
+
+bool
+operator==(const X::special& lhs, const X::special& rhs)
+{
+  return lhs.c == rhs.c && lhs.dt == rhs.dt
+    && lhs.cc == rhs.cc && lhs.ca == rhs.ca
+    && lhs.mc == rhs.mc && lhs.ma == rhs.ma;
+}
+
+// Verify that insert and emplace are equally efficient.
+// Also verify exact number of operations (which are specific to this
+// implementation) in order to catch any regressions.
+
+// insert vs emplace lvalue no reallocation
+void
+test01()
+{
+  const X::special expected{ 0, 1, 1, 0, 1, 3 };
+  X::special ins, emp;
+  {
+    std::vector<X> v;
+    v.reserve(4);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--insert lvalue no reallocation--\n";
+    X::sp = {};
+    v.insert(v.begin(), x);
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    ins = X::sp;
+  }
+  {
+    std::vector<X> v;
+    v.reserve(4);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--emplace lvalue no reallocation--\n";
+    X::sp = {};
+    v.emplace(v.begin(), x);
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    emp = X::sp;
+  }
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
+}
+
+// insert vs emplace xvalue no reallocation
+void
+test02()
+{
+  const X::special expected{ 0, 0, 0, 0, 1, 3 };
+  X::special ins, emp;
+  {
+    std::vector<X> v;
+    v.reserve(4);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--insert xvalue no reallocation--\n";
+    X::sp = {};
+    v.insert(v.begin(), std::move(x));
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    ins = X::sp;
+  }
+  {
+    std::vector<X> v;
+    v.reserve(4);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--emplace xvalue no reallocation--\n";
+    X::sp = {};
+    v.emplace(v.begin(), std::move(x));
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    emp = X::sp;
+  }
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
+}
+
+// insert vs emplace rvalue no reallocation
+void
+test03()
+{
+  const X::special expected{ 1, 1, 0, 0, 1, 3 };
+  X::special ins, emp;
+  {
+    std::vector<X> v;
+    v.reserve(4);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    // std::cout << "--insert rvalue no reallocation--\n";
+    X::sp = {};
+    v.insert(v.begin(), X{0,0});
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    ins = X::sp;
+  }
+  {
+    std::vector<X> v;
+    v.reserve(4);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    // std::cout << "--emplace rvalue no reallocation--\n";
+    X::sp = {};
+    v.emplace(v.begin(), X{0,0});
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    emp = X::sp;
+  }
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
+}
+
+// insert vs emplace lvalue reallocation
+void
+test04()
+{
+  const X::special expected{ 0, 3, 1, 0, 3, 0 };
+  X::special ins, emp;
+  {
+    std::vector<X> v;
+    v.reserve(3);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--insert lvalue reallocation--\n";
+    X::sp = {};
+    v.insert(v.begin(), x);
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    ins = X::sp;
+  }
+  {
+    std::vector<X> v;
+    v.reserve(3);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--emplace lvalue reallocation--\n";
+    X::sp = {};
+    v.emplace(v.begin(), x);
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    emp = X::sp;
+  }
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
+}
+
+// insert vs emplace xvalue reallocation
+void
+test05()
+{
+  const X::special expected{ 0, 3, 0, 0, 4, 0 };
+  X::special ins, emp;
+  {
+    std::vector<X> v;
+    v.reserve(3);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--insert xvalue reallocation--\n";
+    X::sp = {};
+    v.insert(v.begin(), std::move(x));
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    ins = X::sp;
+  }
+  {
+    std::vector<X> v;
+    v.reserve(3);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--emplace xvalue reallocation--\n";
+    X::sp = {};
+    v.emplace(v.begin(), std::move(x));
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    emp = X::sp;
+  }
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
+}
+
+// insert vs emplace rvalue reallocation
+void
+test06()
+{
+  const X::special expected{ 1, 4, 0, 0, 4, 0 };
+  X::special ins, emp;
+  {
+    std::vector<X> v;
+    v.reserve(3);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    // std::cout << "--insert rvalue reallocation--\n";
+    X::sp = {};
+    v.insert(v.begin(), X{0,0});
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    ins = X::sp;
+  }
+  {
+    std::vector<X> v;
+    v.reserve(3);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    // std::cout << "--emplace rvalue reallocation--\n";
+    X::sp = {};
+    v.emplace(v.begin(), X{0,0});
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    emp = X::sp;
+  }
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
+}
+
+// push_back vs emplace_back lvalue no reallocation
+void
+test07()
+{
+  const X::special expected{ 0, 0, 1, 0, 0, 0 };
+  X::special ins, emp;
+  {
+    std::vector<X> v;
+    v.reserve(4);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--push_back lvalue no reallocation--\n";
+    X::sp = {};
+    v.push_back(x);
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    ins = X::sp;
+  }
+  {
+    std::vector<X> v;
+    v.reserve(4);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--emplace_back lvalue no reallocation--\n";
+    X::sp = {};
+    v.emplace_back(x);
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    emp = X::sp;
+  }
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
+}
+
+// push_back vs emplace_back xvalue no reallocation
+void
+test08()
+{
+  const X::special expected{ 0, 0, 0, 0, 1, 0 };
+  X::special ins, emp;
+  {
+    std::vector<X> v;
+    v.reserve(4);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--push_back xvalue no reallocation--\n";
+    X::sp = {};
+    v.push_back(std::move(x));
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    ins = X::sp;
+  }
+  {
+    std::vector<X> v;
+    v.reserve(4);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--emplace_back xvalue no reallocation--\n";
+    X::sp = {};
+    v.emplace_back(std::move(x));
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    emp = X::sp;
+  }
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
+}
+
+// push_back vs emplace_back rvalue no reallocation
+void
+test09()
+{
+  const X::special expected{ 1, 1, 0, 0, 1, 0 };
+  X::special ins, emp;
+  {
+    std::vector<X> v;
+    v.reserve(4);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    // std::cout << "--push_back rvalue no reallocation--\n";
+    X::sp = {};
+    v.push_back(X{0,0});
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    ins = X::sp;
+  }
+  {
+    std::vector<X> v;
+    v.reserve(4);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    // std::cout << "--emplace_back rvalue no reallocation--\n";
+    X::sp = {};
+    v.emplace_back(X{0,0});
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    emp = X::sp;
+  }
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
+}
+
+// push_back vs emplace_back lvalue reallocation
+void
+test10()
+{
+  const X::special expected{ 0, 3, 1, 0, 3, 0 };
+  X::special ins, emp;
+  {
+    std::vector<X> v;
+    v.reserve(3);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--push_back lvalue reallocation--\n";
+    X::sp = {};
+    v.push_back(x);
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    ins = X::sp;
+  }
+  {
+    std::vector<X> v;
+    v.reserve(3);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--emplace_back lvalue reallocation--\n";
+    X::sp = {};
+    v.emplace_back(x);
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    emp = X::sp;
+  }
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
+}
+
+// push_back vs emplace_back xvalue reallocation
+void
+test11()
+{
+  const X::special expected{ 0, 3, 0, 0, 4, 0 };
+  X::special ins, emp;
+  {
+    std::vector<X> v;
+    v.reserve(3);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--push_back xvalue reallocation--\n";
+    X::sp = {};
+    v.push_back(std::move(x));
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    ins = X::sp;
+  }
+  {
+    std::vector<X> v;
+    v.reserve(3);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    X x{0,0};
+    // std::cout << "--emplace_back xvalue reallocation--\n";
+    X::sp = {};
+    v.emplace_back(std::move(x));
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    emp = X::sp;
+  }
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
+}
+
+// push_back vs emplace_back rvalue reallocation
+void
+test12()
+{
+  const X::special expected{ 1, 4, 0, 0, 4, 0 };
+  X::special ins, emp;
+  {
+    std::vector<X> v;
+    v.reserve(3);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    // std::cout << "--push_back rvalue reallocation--\n";
+    X::sp = {};
+    v.push_back(X{0,0});
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    ins = X::sp;
+  }
+  {
+    std::vector<X> v;
+    v.reserve(3);
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    v.push_back(X(0,0));
+    // std::cout << "--emplace_back rvalue reallocation--\n";
+    X::sp = {};
+    v.emplace_back(X{0,0});
+    // std::cout << X::sp;
+    // std::cout << "----\n";
+    emp = X::sp;
+  }
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+  test05();
+  test06();
+  test07();
+  test08();
+  test09();
+  test10();
+  test11();
+  test12();
+}

Re: [PATCH] Optimize inserting value_type into std::vector

[Jonathan Wakely]

On 15/06/16 11:15 +0100, Jonathan Wakely wrote:
>	* include/bits/stl_vector.h (vector::_S_insert_aux_assign): Define
>	new overloaded functions.
>	* include/bits/vector.tcc (vector::_M_insert_aux): Use new functions
>	to avoid creating a redundant temporary.
>	* testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc: New
>	test.
>
>Tested x86_64-linux.
>
>This improves our performance on Howard Hinnant's "insert vs emplace"
>experiment at
>http://htmlpreview.github.io/?https://github.com/HowardHinnant/papers/blob/master/insert_vs_emplace.html
>
>With this small change there is no difference between emplacing or
>using the relevant insert / push_back function. That also means we
>beat libc++ in some cases, making us the bestest, whoo!

We still lose to libc++ in one case. For the "lvalue no reallocation"
test our insert and emplace are equal to libc++'s emplace, but
libc++'s insert is even better.

For "xvalue no reallocation" and "rvalue no reallocation" our insert
and emplace are equal to libc++'s insert, but libc++'s emplace is
worse. So either my patch is wrong or we've got a new minimum for the
emplace operations.

In all other cases our results are unchanged by this patch.

So if this patch goes in we fix the case that made it difficult for
Howard to give consistent advice, where emplace was better than insert
for libstdc++ but not the other implementations. With this patch
insert is always at least as good as emplace, for all implementations.

Re: [PATCH] Optimize inserting value_type into std::vector

[Jonathan Wakely]

On 15/06/16 11:34 +0100, Jonathan Wakely wrote:
>On 15/06/16 11:15 +0100, Jonathan Wakely wrote:
>>	* include/bits/stl_vector.h (vector::_S_insert_aux_assign): Define
>>	new overloaded functions.
>>	* include/bits/vector.tcc (vector::_M_insert_aux): Use new functions
>>	to avoid creating a redundant temporary.
>>	* testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc: New
>>	test.
>>
>>Tested x86_64-linux.
>>
>>This improves our performance on Howard Hinnant's "insert vs emplace"
>>experiment at
>>http://htmlpreview.github.io/?https://github.com/HowardHinnant/papers/blob/master/insert_vs_emplace.html
>>
>>With this small change there is no difference between emplacing or
>>using the relevant insert / push_back function. That also means we
>>beat libc++ in some cases, making us the bestest, whoo!
>
>We still lose to libc++ in one case. For the "lvalue no reallocation"
>test our insert and emplace are equal to libc++'s emplace, but
>libc++'s insert is even better.

Libc++'s insert(const_iterator, const value_type&) is *really* clever.
It notices when the object to insert is an element of the vector, and
then works out where its updated position would be after shifting the
existing elements along, and then copies from the new position. That
avoids the copy we make upfront to handle that case safely. Our
approach is inefficient for the common case where the object *isn't*
in the vector.

I guess it's something like:

  void
  insert(const_iterator pos, const value_type& x)
  {
    if (cpacity() == size())
      {
        // reallocate and insert ...
        return;
      }
    auto it = end() - 1;
    *end() = std::move(*it);
    ++this->_M_impl._M_finish;
    const value_type* from = std::addressof(x);
    for (; it != pos; --it)
    {
      auto prev = it - 1;
      *it = std::move(*prev);
      if (std::addressof(*prev) == from)
        ++from;
    }
    *pos = *from;
  }

Clever.

Re: [PATCH] Optimize inserting value_type into std::vector

[Jonathan Wakely]

On 15/06/16 11:15 +0100, Jonathan Wakely wrote:
>	* include/bits/stl_vector.h (vector::_S_insert_aux_assign): Define
>	new overloaded functions.
>	* include/bits/vector.tcc (vector::_M_insert_aux): Use new functions
>	to avoid creating a redundant temporary.
>	* testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc: New
>	test.
>
>Tested x86_64-linux.

Committed to trunk.

Improve insert/emplace robustness to self insertion

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 2600 bytes --]

Hi

     Following below discussion here is a patch to make sure we 
correctly deal with insertion of instances stored into the vector itself.

     When we don't need reallocation I have implemented the libc++ trick 
to avoid an intermediate copy. I did my best to detect when a value_type 
instance is being inserted, whatever how it is inserted, lvalue/rvalue 
or xvalue reference. I was thinking that taking address of an rvalue 
would fail but it didn't. I also reuse _M_data_ptr method even if when 
vector is empty it doesn't work but vector is not empty when used so it 
should be fine. In the _M_insert_aux taking variadic number of 
parameters I always create a copy cause we can't know if one of those 
parameter has a link to vector values.

     We could also implement libc++ trick in _M_fill_insert but not sure 
it worth it, what do you think ?

     All vector tests run so far.

François

On 20/06/2016 09:42, Jonathan Wakely wrote:
> On 19/06/16 10:21 +0200, François Dumont wrote:
>> On 16/06/2016 22:21, Jonathan Wakely wrote:
>>> On 16/06/16 21:27 +0200, François Dumont wrote:
>>>> Very nice improvement. Could also benefit to other containers, 
>>>> especially std::deque. Do you plan to take care of it ?
>>>
>>> Good point - I'd only looked at it for std::vector, because that's
>>> what Howard's experiment tested. I haven't looked at the other
>>> containers at all, and wasn't planning to do so. If you have time to
>>> look at them that would be great, otherwise I'll add it to my TODO
>>> list for something to look at later.
>>>
>>>
>> I started considering it and so came to the question of 
>> insert/emplace of the container self values. Is the following program 
>> ill-formed ?
>>
>> int main()
>> {
>>  std::vector<std::vector<int>> vv =
>>    {
>>      { 2, 3 },
>>      { 4, 5 },
>>      { 0, 1 }
>>    };
>>
>>  vv.reserve(4);
>>  vv.emplace(vv.begin(), vv[0]);
>>
>>  assert( vv[0].size() == 2 );
>> }
>>
>> The assert fails because we end-up assigning a moved vector instance 
>> to vv first entry. This is not a regression of this patch, we were 
>> already not creating any copy before moving all vector values. If 
>> this program is ill-formed why does libc++ consider this kind of 
>> situation in its insert implementation ?
>
> I think this should work correctly, for both insert and emplace.
>
>> Note that it gave me the idear of adding a DEBUG check detecting when 
>> a moved instance is being used. A moved instance shall only be 
>> destroyed or assigned, no ?
>
> That's not true in general, but is true for these members of vector.
>
>
>


[-- Attachment #2: vector_self_insert.patch --]
[-- Type: text/x-patch, Size: 16375 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index eaafa22..d7435cc 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -949,7 +949,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus >= 201103L
 	  _M_emplace_back_aux(__x);
 #else
-	  _M_insert_aux(end(), __x);
+	  _M_realloc_insert_aux(end(), __x);
 #endif
       }
 
@@ -1432,23 +1432,37 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
 
       // Called by insert(p,x)
+      void
+      _M_insert_aux(iterator __position, const value_type& __x)
+      { _M_insert_value_aux(__position, __x); }
+
 #if __cplusplus < 201103L
       void
-      _M_insert_aux(iterator __position, const value_type& __x);
-#else
-      template<typename... _Args>
-	static void
-	_S_insert_aux_assign(iterator __pos, _Args&&... __args)
-	{ *__pos =  _Tp(std::forward<_Args>(__args)...); }
+      _M_insert_value_aux(iterator __position, const value_type& __x);
 
-      static void
-      _S_insert_aux_assign(iterator __pos, _Tp&& __arg)
-      { *__pos = std::move(__arg); }
+      void
+      _M_realloc_insert_aux(iterator __position, const value_type& __x);
+#else
+      template<typename _Val>
+        void
+        _M_insert_value_aux(iterator __position, _Val&& __x);
 
       template<typename... _Args>
 	void
 	_M_insert_aux(iterator __position, _Args&&... __args);
 
+      void
+      _M_insert_aux(iterator __position, value_type& __x)
+      { _M_insert_value_aux(__position, __x); }
+
+      void
+      _M_insert_aux(iterator __position, value_type&& __x)
+      { _M_insert_value_aux(__position, std::move(__x)); }
+
+      template<typename... _Args>
+        void
+        _M_realloc_insert_aux(iterator __position, _Args&&... __args);
+
       template<typename... _Args>
 	void
 	_M_emplace_back_aux(_Args&&... __args);
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 604be7b..dab578e 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -112,27 +112,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
     {
       const size_type __n = __position - begin();
-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	  && __position == end())
-	{
-	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
-	  ++this->_M_impl._M_finish;
-	}
+      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	if (__position == end())
+	  {
+	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
+	    ++this->_M_impl._M_finish;
+	  }
+	else
+#if __cplusplus >= 201103L
+	  _M_insert_value_aux(begin() + (__position - cbegin()), __x);
+#else
+	  _M_insert_value_aux(__position, __x);
+#endif
       else
-	{
 #if __cplusplus >= 201103L
-	  const auto __pos = begin() + (__position - cbegin());
-	  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
-	    {
-	      _Tp __x_copy = __x;
-	      _M_insert_aux(__pos, std::move(__x_copy));
-	    }
-	  else
-	    _M_insert_aux(__pos, __x);
+	_M_realloc_insert_aux(begin() + (__position - cbegin()), __x);
 #else
-	    _M_insert_aux(__position, __x);
+	_M_realloc_insert_aux(__position, __x);
 #endif
-	}
+
       return iterator(this->_M_impl._M_start + __n);
     }
 
@@ -303,16 +301,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       emplace(const_iterator __position, _Args&&... __args)
       {
 	const size_type __n = __position - begin();
-	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	    && __position == end())
-	  {
-	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-				     std::forward<_Args>(__args)...);
-	    ++this->_M_impl._M_finish;
-	  }
+	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	  if (__position == end())
+	    {
+	      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				       std::forward<_Args>(__args)...);
+	      ++this->_M_impl._M_finish;
+	    }
+	  else
+	    _M_insert_aux(begin() + (__position - cbegin()),
+			  std::forward<_Args>(__args)...);
 	else
-	  _M_insert_aux(begin() + (__position - cbegin()),
-			std::forward<_Args>(__args)...);
+	  _M_realloc_insert_aux(begin() + (__position - cbegin()),
+				std::forward<_Args>(__args)...);
+
 	return iterator(this->_M_impl._M_start + __n);
       }
 
@@ -321,84 +323,115 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       void
       vector<_Tp, _Alloc>::
       _M_insert_aux(iterator __position, _Args&&... __args)
+      {
+	_Tp __x(std::forward<_Args>(__args)...);
+	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				 std::move(*(this->_M_impl._M_finish - 1)));
+	++this->_M_impl._M_finish;
+
+	std::move_backward(__position.base(),
+			   this->_M_impl._M_finish - 2,
+			   this->_M_impl._M_finish - 1);
+	*__position = std::move(__x);
+      }
+#endif
+
+#if __cplusplus >= 201103L
+  template<typename _Tp, typename _Alloc>
+    template<typename _Val>
+      void
+      vector<_Tp, _Alloc>::
+      _M_insert_value_aux(iterator __position, _Val&& __x)
 #else
   template<typename _Tp, typename _Alloc>
     void
     vector<_Tp, _Alloc>::
-    _M_insert_aux(iterator __position, const _Tp& __x)
+    _M_insert_value_aux(iterator __position, const _Tp& __x)
 #endif
     {
-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+      const _Tp* __ptr = std::__addressof(__x);
+
+      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+			       _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
+      ++this->_M_impl._M_finish;
+
+      _GLIBCXX_MOVE_BACKWARD3(__position.base(),
+			      this->_M_impl._M_finish - 2,
+			      this->_M_impl._M_finish - 1);
+
+      if (_M_data_ptr(__position.base()) <= __ptr
+	  && __ptr < _M_data_ptr(this->_M_impl._M_finish - 1))
 	{
-	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-			           _GLIBCXX_MOVE(*(this->_M_impl._M_finish
-				                   - 1)));
-	  ++this->_M_impl._M_finish;
-#if __cplusplus < 201103L
-	  _Tp __x_copy = __x;
-#endif
-	  _GLIBCXX_MOVE_BACKWARD3(__position.base(),
-				  this->_M_impl._M_finish - 2,
-				  this->_M_impl._M_finish - 1);
-#if __cplusplus < 201103L
-	  *__position = __x_copy;
-#else
-	  _S_insert_aux_assign(__position, std::forward<_Args>(__args)...);
-#endif
+	  ++__ptr;
+	  *__position = *__ptr;
 	}
       else
+	*__position = _GLIBCXX_FORWARD(_Val, __x);
+    }
+
+#if __cplusplus >= 201103L
+  template<typename _Tp, typename _Alloc>
+    template<typename... _Args>
+      void
+      vector<_Tp, _Alloc>::
+      _M_realloc_insert_aux(iterator __position, _Args&&... __args)
+#else
+  template<typename _Tp, typename _Alloc>
+    void
+    vector<_Tp, _Alloc>::
+    _M_realloc_insert_aux(iterator __position, const _Tp& __x)
+#endif
+    {
+      const size_type __len =
+	_M_check_len(size_type(1), "vector::_M_realloc_insert_aux");
+      const size_type __elems_before = __position - begin();
+      pointer __new_start(this->_M_allocate(__len));
+      pointer __new_finish(__new_start);
+      __try
 	{
-	  const size_type __len =
-	    _M_check_len(size_type(1), "vector::_M_insert_aux");
-	  const size_type __elems_before = __position - begin();
-	  pointer __new_start(this->_M_allocate(__len));
-	  pointer __new_finish(__new_start);
-	  __try
-	    {
-	      // The order of the three operations is dictated by the C++0x
-	      // case, where the moves could alter a new element belonging
-	      // to the existing vector.  This is an issue only for callers
-	      // taking the element by const lvalue ref (see 23.1/13).
-	      _Alloc_traits::construct(this->_M_impl,
-		                       __new_start + __elems_before,
+	  // The order of the three operations is dictated by the C++0x
+	  // case, where the moves could alter a new element belonging
+	  // to the existing vector.  This is an issue only for callers
+	  // taking the element by const lvalue ref (see 23.1/13).
+	  _Alloc_traits::construct(this->_M_impl,
+				   __new_start + __elems_before,
 #if __cplusplus >= 201103L
-				       std::forward<_Args>(__args)...);
+				   std::forward<_Args>(__args)...);
 #else
-	                               __x);
+				   __x);
 #endif
-	      __new_finish = pointer();
+	  __new_finish = pointer();
 
-	      __new_finish
-		= std::__uninitialized_move_if_noexcept_a
-		(this->_M_impl._M_start, __position.base(),
-		 __new_start, _M_get_Tp_allocator());
+	  __new_finish
+	    = std::__uninitialized_move_if_noexcept_a
+	    (this->_M_impl._M_start, __position.base(),
+	     __new_start, _M_get_Tp_allocator());
 
-	      ++__new_finish;
+	  ++__new_finish;
 
-	      __new_finish
-		= std::__uninitialized_move_if_noexcept_a
-		(__position.base(), this->_M_impl._M_finish,
-		 __new_finish, _M_get_Tp_allocator());
-	    }
-          __catch(...)
-	    {
-	      if (!__new_finish)
-		_Alloc_traits::destroy(this->_M_impl,
-		                       __new_start + __elems_before);
-	      else
-		std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
-	      _M_deallocate(__new_start, __len);
-	      __throw_exception_again;
-	    }
-	  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
-			_M_get_Tp_allocator());
-	  _M_deallocate(this->_M_impl._M_start,
-			this->_M_impl._M_end_of_storage
-			- this->_M_impl._M_start);
-	  this->_M_impl._M_start = __new_start;
-	  this->_M_impl._M_finish = __new_finish;
-	  this->_M_impl._M_end_of_storage = __new_start + __len;
+	  __new_finish
+	    = std::__uninitialized_move_if_noexcept_a
+	    (__position.base(), this->_M_impl._M_finish,
+	     __new_finish, _M_get_Tp_allocator());
+	}
+      __catch(...)
+	{
+	  if (!__new_finish)
+	    _Alloc_traits::destroy(this->_M_impl,
+				   __new_start + __elems_before);
+	  else
+	    std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
+	  _M_deallocate(__new_start, __len);
+	  __throw_exception_again;
 	}
+      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+		    _M_get_Tp_allocator());
+      _M_deallocate(this->_M_impl._M_start,
+		    this->_M_impl._M_end_of_storage
+		    - this->_M_impl._M_start);
+      this->_M_impl._M_start = __new_start;
+      this->_M_impl._M_finish = __new_finish;
+      this->_M_impl._M_end_of_storage = __new_start + __len;
     }
 
 #if __cplusplus >= 201103L
@@ -493,7 +526,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	      pointer __new_finish(__new_start);
 	      __try
 		{
-		  // See _M_insert_aux above.
+		  // See _M_realloc_insert_aux above.
 		  std::__uninitialized_fill_n_a(__new_start + __elems_before,
 						__n, __x,
 						_M_get_Tp_allocator());
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
new file mode 100644
index 0000000..d452b5b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
@@ -0,0 +1,144 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void
+test01()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void
+test02()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace won't reallocate.
+  vv.reserve(4);
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+struct A
+{
+  A(int i) : _i(i)
+  { }
+
+  A(const A& other) : _i(other._i)
+  {
+    VERIFY( other._i >= 0 );
+  }
+
+  A(A&& other) : _i(other._i)
+  {
+    VERIFY( other._i >= 0 );
+
+    other._i = -1;
+  }
+
+  A(std::vector<A>::iterator it) : _i(it->_i)
+  {
+    VERIFY( it->_i >= 0 );
+  }
+
+  A& operator=(const A&) = default;
+  A& operator=(A&& other)
+  {
+    VERIFY(other._i >= 0 );
+
+    _i = other._i;
+    other._i = -1;
+    return *this;
+  }
+
+  int _i;
+};
+
+void
+test03()
+{
+  std::vector<A> va =
+    {
+      { A(1) },
+      { A(2) },
+      { A(3) }
+    };
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( va.capacity() == 3 );
+
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+void
+test04()
+{
+  std::vector<A> va =
+    {
+      { A(1) },
+      { A(2) },
+      { A(3) }
+    };
+
+  // Make sure emplace won't reallocate.
+  va.reserve(4);
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
new file mode 100644
index 0000000..9944cbb
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
@@ -0,0 +1,70 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure it doesn't reallocate during insertion.
+  vv.reserve(4);
+
+  vv.insert(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void test02()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure we will reallocate for insertion.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.insert(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+int main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
index 39a3f03..4c9c57e 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
@@ -111,7 +111,7 @@ operator==(const X::special& lhs, const X::special& rhs)
 void
 test01()
 {
-  const X::special expected{ 0, 1, 1, 0, 1, 3 };
+  const X::special expected{ 0, 0, 0, 1, 1, 2 };
   X::special ins, emp;
   {
     std::vector<X> v;

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 28/06/16 21:59 +0200, François Dumont wrote:
>   template<typename _Tp, typename _Alloc>
>     void
>     vector<_Tp, _Alloc>::
>-    _M_insert_aux(iterator __position, const _Tp& __x)
>+    _M_insert_value_aux(iterator __position, const _Tp& __x)
> #endif
>     {
>-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
>+      const _Tp* __ptr = std::__addressof(__x);
>+
>+      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
>+			       _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
>+      ++this->_M_impl._M_finish;
>+
>+      _GLIBCXX_MOVE_BACKWARD3(__position.base(),
>+			      this->_M_impl._M_finish - 2,
>+			      this->_M_impl._M_finish - 1);
>+
>+      if (_M_data_ptr(__position.base()) <= __ptr
>+	  && __ptr < _M_data_ptr(this->_M_impl._M_finish - 1))

This is undefined behaviour. If the object is not contained in the
vector then you can't compare its address to addresses within the
vector.

I suggest forgetting about this optimisation unless we get a guarantee
from the compiler that we can do it safely. It's orthogonal to fixing
the correctness bug with emplacing an existing element of the vector.
We can fix the correctness bug now and worry about this optimisation
separately.

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 28/06/16 21:59 +0200, François Dumont wrote:
>@@ -303,16 +301,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>       emplace(const_iterator __position, _Args&&... __args)
>       {
> 	const size_type __n = __position - begin();

It looks like this should use __position - cbegin(), to avoid an
implicit conversion from iterator to const_iterator, and ...

>-	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
>-	    && __position == end())
>-	  {
>-	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
>-				     std::forward<_Args>(__args)...);
>-	    ++this->_M_impl._M_finish;
>-	  }
>+	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
>+	  if (__position == end())

This could be __position == cend(), and ...

>+	    {
>+	      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
>+				       std::forward<_Args>(__args)...);
>+	      ++this->_M_impl._M_finish;
>+	    }
>+	  else
>+	    _M_insert_aux(begin() + (__position - cbegin()),

This could use __n, and ...

>+			  std::forward<_Args>(__args)...);
> 	else
>-	  _M_insert_aux(begin() + (__position - cbegin()),
>-			std::forward<_Args>(__args)...);
>+	  _M_realloc_insert_aux(begin() + (__position - cbegin()),

This could also use __n.

>+				std::forward<_Args>(__args)...);
>+
> 	return iterator(this->_M_impl._M_start + __n);
>       }
> 

Re: Improve insert/emplace robustness to self insertion

[Paolo Carlini]

Hi,

On 29/06/2016 10:57, Jonathan Wakely wrote:
> On 28/06/16 21:59 +0200, François Dumont wrote:
>> +      if (_M_data_ptr(__position.base()) <= __ptr
>> +      && __ptr < _M_data_ptr(this->_M_impl._M_finish - 1))
>
> This is undefined behaviour. If the object is not contained in the
> vector then you can't compare its address to addresses within the
> vector.

Uhm, would that be true also if the code used std::less? Aren't we doing 
something like that in std::basic_string under the assumption (Nathan?) 
that it would not be the case? Or maybe I'm misreading the code 
(admittedly I didn't follow in detail the whole exchange)

Paolo.

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 29/06/16 11:35 +0200, Paolo Carlini wrote:
>Hi,
>
>On 29/06/2016 10:57, Jonathan Wakely wrote:
>>On 28/06/16 21:59 +0200, François Dumont wrote:
>>>+      if (_M_data_ptr(__position.base()) <= __ptr
>>>+      && __ptr < _M_data_ptr(this->_M_impl._M_finish - 1))
>>
>>This is undefined behaviour. If the object is not contained in the
>>vector then you can't compare its address to addresses within the
>>vector.
>
>Uhm, would that be true also if the code used std::less? Aren't we 
>doing something like that in std::basic_string under the assumption 
>(Nathan?) that it would not be the case? Or maybe I'm misreading the 
>code (admittedly I didn't follow in detail the whole exchange)

Yes, it's OK if you use std::less. In general there's no guarantee
that std::less<T*> defines the same order as operator<(T*, T*), but in
our implementation it does.

I'd still prefer to keep a correctness fix and a potentially risky
optimisation in separate commits.

Re: Improve insert/emplace robustness to self insertion

[Paolo Carlini]

Hi,

On 29/06/2016 12:07, Jonathan Wakely wrote:
> On 29/06/16 11:35 +0200, Paolo Carlini wrote:
>> Hi,
>>
>> On 29/06/2016 10:57, Jonathan Wakely wrote:
>>> On 28/06/16 21:59 +0200, François Dumont wrote:
>>>> +      if (_M_data_ptr(__position.base()) <= __ptr
>>>> +      && __ptr < _M_data_ptr(this->_M_impl._M_finish - 1))
>>>
>>> This is undefined behaviour. If the object is not contained in the
>>> vector then you can't compare its address to addresses within the
>>> vector.
>>
>> Uhm, would that be true also if the code used std::less? Aren't we 
>> doing something like that in std::basic_string under the assumption 
>> (Nathan?) that it would not be the case? Or maybe I'm misreading the 
>> code (admittedly I didn't follow in detail the whole exchange)
>
> Yes, it's OK if you use std::less. In general there's no guarantee
> that std::less<T*> defines the same order as operator<(T*, T*), but in
> our implementation it does.
Ah Ok, excellent.

> I'd still prefer to keep a correctness fix and a potentially risky
> optimisation in separate commits.

Definitely. Maybe with an additional comment too!

Paolo.

Re: Improve insert/emplace robustness to self insertion

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 2185 bytes --]

On 29/06/2016 11:10, Jonathan Wakely wrote:
> On 28/06/16 21:59 +0200, François Dumont wrote:
>> @@ -303,16 +301,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>       emplace(const_iterator __position, _Args&&... __args)
>>       {
>>     const size_type __n = __position - begin();
>
> It looks like this should use __position - cbegin(), to avoid an
> implicit conversion from iterator to const_iterator, and ...
>
>> -    if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
>> -        && __position == end())
>> -      {
>> -        _Alloc_traits::construct(this->_M_impl, 
>> this->_M_impl._M_finish,
>> -                     std::forward<_Args>(__args)...);
>> -        ++this->_M_impl._M_finish;
>> -      }
>> +    if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
>> +      if (__position == end())
>
> This could be __position == cend(), and ...
>
>> +        {
>> +          _Alloc_traits::construct(this->_M_impl, 
>> this->_M_impl._M_finish,
>> +                       std::forward<_Args>(__args)...);
>> +          ++this->_M_impl._M_finish;
>> +        }
>> +      else
>> +        _M_insert_aux(begin() + (__position - cbegin()),
>
> This could use __n, and ...
>
>> + std::forward<_Args>(__args)...);
>>     else
>> -      _M_insert_aux(begin() + (__position - cbegin()),
>> -            std::forward<_Args>(__args)...);
>> +      _M_realloc_insert_aux(begin() + (__position - cbegin()),
>
> This could also use __n.
>
>> + std::forward<_Args>(__args)...);
>> +
>>     return iterator(this->_M_impl._M_start + __n);
>>       }
>>
> .
>
I tried those changes too but started having failing tests in 
vector/ext_pointer so prefer to not touch that for the moment. I think 
the compilation error was coming from the change of begin() + 
(__position - cbegin()) into begin() + __n because of overloaded 
operator+. The 2 other changes should be fine for a future patch.

As asked here is now a patch to only fix the robustness issue. The 
consequence is that it is reverting the latest optimization as, without 
smart algo, we always need to do a copy to protect against insertion of 
values contained in the vector as shown by new tests.

François

[-- Attachment #2: vector_self_insert.patch --]
[-- Type: text/x-patch, Size: 14995 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index eaafa22..c37880a 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -949,7 +949,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus >= 201103L
 	  _M_emplace_back_aux(__x);
 #else
-	  _M_insert_aux(end(), __x);
+	  _M_realloc_insert_aux(end(), __x);
 #endif
       }
 
@@ -1435,21 +1435,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus < 201103L
       void
       _M_insert_aux(iterator __position, const value_type& __x);
-#else
-      template<typename... _Args>
-	static void
-	_S_insert_aux_assign(iterator __pos, _Args&&... __args)
-	{ *__pos =  _Tp(std::forward<_Args>(__args)...); }
-
-      static void
-      _S_insert_aux_assign(iterator __pos, _Tp&& __arg)
-      { *__pos = std::move(__arg); }
 
+      void
+      _M_realloc_insert_aux(iterator __position, const value_type& __x);
+#else
       template<typename... _Args>
 	void
 	_M_insert_aux(iterator __position, _Args&&... __args);
 
       template<typename... _Args>
+        void
+        _M_realloc_insert_aux(iterator __position, _Args&&... __args);
+
+      template<typename... _Args>
 	void
 	_M_emplace_back_aux(_Args&&... __args);
 #endif
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 604be7b..9061593 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -112,27 +112,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
     {
       const size_type __n = __position - begin();
-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	  && __position == end())
-	{
-	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
-	  ++this->_M_impl._M_finish;
-	}
+      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	if (__position == end())
+	  {
+	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
+	    ++this->_M_impl._M_finish;
+	  }
+	else
+#if __cplusplus >= 201103L
+	  _M_insert_aux(begin() + (__position - cbegin()), __x);
+#else
+	  _M_insert_aux(__position, __x);
+#endif
       else
-	{
 #if __cplusplus >= 201103L
-	  const auto __pos = begin() + (__position - cbegin());
-	  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
-	    {
-	      _Tp __x_copy = __x;
-	      _M_insert_aux(__pos, std::move(__x_copy));
-	    }
-	  else
-	    _M_insert_aux(__pos, __x);
+	_M_realloc_insert_aux(begin() + (__position - cbegin()), __x);
 #else
-	    _M_insert_aux(__position, __x);
+	_M_realloc_insert_aux(__position, __x);
 #endif
-	}
+
       return iterator(this->_M_impl._M_start + __n);
     }
 
@@ -303,16 +301,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       emplace(const_iterator __position, _Args&&... __args)
       {
 	const size_type __n = __position - begin();
-	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	    && __position == end())
-	  {
-	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-				     std::forward<_Args>(__args)...);
-	    ++this->_M_impl._M_finish;
-	  }
+	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	  if (__position == end())
+	    {
+	      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				       std::forward<_Args>(__args)...);
+	      ++this->_M_impl._M_finish;
+	    }
+	  else
+	    _M_insert_aux(begin() + (__position - cbegin()),
+			  std::forward<_Args>(__args)...);
 	else
-	  _M_insert_aux(begin() + (__position - cbegin()),
-			std::forward<_Args>(__args)...);
+	  _M_realloc_insert_aux(begin() + (__position - cbegin()),
+				std::forward<_Args>(__args)...);
+
 	return iterator(this->_M_impl._M_start + __n);
       }
 
@@ -327,78 +329,86 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     vector<_Tp, _Alloc>::
     _M_insert_aux(iterator __position, const _Tp& __x)
 #endif
-    {
-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
-	{
-	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-			           _GLIBCXX_MOVE(*(this->_M_impl._M_finish
-				                   - 1)));
-	  ++this->_M_impl._M_finish;
-#if __cplusplus < 201103L
-	  _Tp __x_copy = __x;
+      {
+#if __cplusplus >= 201103L
+	_Tp __x_copy(std::forward<_Args>(__args)...);
+#else
+	_Tp __x_copy(__x);
 #endif
-	  _GLIBCXX_MOVE_BACKWARD3(__position.base(),
-				  this->_M_impl._M_finish - 2,
-				  this->_M_impl._M_finish - 1);
-#if __cplusplus < 201103L
-	  *__position = __x_copy;
+	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				 _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
+	++this->_M_impl._M_finish;
+
+	_GLIBCXX_MOVE_BACKWARD3(__position.base(),
+				this->_M_impl._M_finish - 2,
+				this->_M_impl._M_finish - 1);
+
+	*__position = _GLIBCXX_MOVE(__x_copy);
+      }
+
+#if __cplusplus >= 201103L
+  template<typename _Tp, typename _Alloc>
+    template<typename... _Args>
+      void
+      vector<_Tp, _Alloc>::
+      _M_realloc_insert_aux(iterator __position, _Args&&... __args)
 #else
-	  _S_insert_aux_assign(__position, std::forward<_Args>(__args)...);
+  template<typename _Tp, typename _Alloc>
+    void
+    vector<_Tp, _Alloc>::
+    _M_realloc_insert_aux(iterator __position, const _Tp& __x)
 #endif
-	}
-      else
+    {
+      const size_type __len =
+	_M_check_len(size_type(1), "vector::_M_realloc_insert_aux");
+      const size_type __elems_before = __position - begin();
+      pointer __new_start(this->_M_allocate(__len));
+      pointer __new_finish(__new_start);
+      __try
 	{
-	  const size_type __len =
-	    _M_check_len(size_type(1), "vector::_M_insert_aux");
-	  const size_type __elems_before = __position - begin();
-	  pointer __new_start(this->_M_allocate(__len));
-	  pointer __new_finish(__new_start);
-	  __try
-	    {
-	      // The order of the three operations is dictated by the C++0x
-	      // case, where the moves could alter a new element belonging
-	      // to the existing vector.  This is an issue only for callers
-	      // taking the element by const lvalue ref (see 23.1/13).
-	      _Alloc_traits::construct(this->_M_impl,
-		                       __new_start + __elems_before,
+	  // The order of the three operations is dictated by the C++0x
+	  // case, where the moves could alter a new element belonging
+	  // to the existing vector.  This is an issue only for callers
+	  // taking the element by const lvalue ref (see 23.1/13).
+	  _Alloc_traits::construct(this->_M_impl,
+				   __new_start + __elems_before,
 #if __cplusplus >= 201103L
-				       std::forward<_Args>(__args)...);
+				   std::forward<_Args>(__args)...);
 #else
-	                               __x);
+				   __x);
 #endif
-	      __new_finish = pointer();
+	  __new_finish = pointer();
 
-	      __new_finish
-		= std::__uninitialized_move_if_noexcept_a
-		(this->_M_impl._M_start, __position.base(),
-		 __new_start, _M_get_Tp_allocator());
+	  __new_finish
+	    = std::__uninitialized_move_if_noexcept_a
+	    (this->_M_impl._M_start, __position.base(),
+	     __new_start, _M_get_Tp_allocator());
 
-	      ++__new_finish;
+	  ++__new_finish;
 
-	      __new_finish
-		= std::__uninitialized_move_if_noexcept_a
-		(__position.base(), this->_M_impl._M_finish,
-		 __new_finish, _M_get_Tp_allocator());
-	    }
-          __catch(...)
-	    {
-	      if (!__new_finish)
-		_Alloc_traits::destroy(this->_M_impl,
-		                       __new_start + __elems_before);
-	      else
-		std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
-	      _M_deallocate(__new_start, __len);
-	      __throw_exception_again;
-	    }
-	  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
-			_M_get_Tp_allocator());
-	  _M_deallocate(this->_M_impl._M_start,
-			this->_M_impl._M_end_of_storage
-			- this->_M_impl._M_start);
-	  this->_M_impl._M_start = __new_start;
-	  this->_M_impl._M_finish = __new_finish;
-	  this->_M_impl._M_end_of_storage = __new_start + __len;
+	  __new_finish
+	    = std::__uninitialized_move_if_noexcept_a
+	    (__position.base(), this->_M_impl._M_finish,
+	     __new_finish, _M_get_Tp_allocator());
+	}
+      __catch(...)
+	{
+	  if (!__new_finish)
+	    _Alloc_traits::destroy(this->_M_impl,
+				   __new_start + __elems_before);
+	  else
+	    std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
+	  _M_deallocate(__new_start, __len);
+	  __throw_exception_again;
 	}
+      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+		    _M_get_Tp_allocator());
+      _M_deallocate(this->_M_impl._M_start,
+		    this->_M_impl._M_end_of_storage
+		    - this->_M_impl._M_start);
+      this->_M_impl._M_start = __new_start;
+      this->_M_impl._M_finish = __new_finish;
+      this->_M_impl._M_end_of_storage = __new_start + __len;
     }
 
 #if __cplusplus >= 201103L
@@ -493,7 +503,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	      pointer __new_finish(__new_start);
 	      __try
 		{
-		  // See _M_insert_aux above.
+		  // See _M_realloc_insert_aux above.
 		  std::__uninitialized_fill_n_a(__new_start + __elems_before,
 						__n, __x,
 						_M_get_Tp_allocator());
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
new file mode 100644
index 0000000..d452b5b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
@@ -0,0 +1,144 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void
+test01()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void
+test02()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace won't reallocate.
+  vv.reserve(4);
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+struct A
+{
+  A(int i) : _i(i)
+  { }
+
+  A(const A& other) : _i(other._i)
+  {
+    VERIFY( other._i >= 0 );
+  }
+
+  A(A&& other) : _i(other._i)
+  {
+    VERIFY( other._i >= 0 );
+
+    other._i = -1;
+  }
+
+  A(std::vector<A>::iterator it) : _i(it->_i)
+  {
+    VERIFY( it->_i >= 0 );
+  }
+
+  A& operator=(const A&) = default;
+  A& operator=(A&& other)
+  {
+    VERIFY(other._i >= 0 );
+
+    _i = other._i;
+    other._i = -1;
+    return *this;
+  }
+
+  int _i;
+};
+
+void
+test03()
+{
+  std::vector<A> va =
+    {
+      { A(1) },
+      { A(2) },
+      { A(3) }
+    };
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( va.capacity() == 3 );
+
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+void
+test04()
+{
+  std::vector<A> va =
+    {
+      { A(1) },
+      { A(2) },
+      { A(3) }
+    };
+
+  // Make sure emplace won't reallocate.
+  va.reserve(4);
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
new file mode 100644
index 0000000..9944cbb
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
@@ -0,0 +1,70 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure it doesn't reallocate during insertion.
+  vv.reserve(4);
+
+  vv.insert(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void test02()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure we will reallocate for insertion.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.insert(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+int main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
index 39a3f03..8bd72b7 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
@@ -149,7 +149,7 @@ test01()
 void
 test02()
 {
-  const X::special expected{ 0, 0, 0, 0, 1, 3 };
+  const X::special expected{ 0, 1, 0, 0, 2, 3 };
   X::special ins, emp;
   {
     std::vector<X> v;
@@ -187,7 +187,7 @@ test02()
 void
 test03()
 {
-  const X::special expected{ 1, 1, 0, 0, 1, 3 };
+  const X::special expected{ 1, 2, 0, 0, 2, 3 };
   X::special ins, emp;
   {
     std::vector<X> v;

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 29/06/16 21:43 +0200, François Dumont wrote:
>As asked here is now a patch to only fix the robustness issue. The 
>consequence is that it is reverting the latest optimization as, 
>without smart algo, we always need to do a copy to protect against 
>insertion of values contained in the vector as shown by new tests.

I don't understand. There is no problem with insert(), only with
emplace(), so why do both get worse?

Also, the problem is with emplacing from an lvalue, so why do the
number of operations change for test02 and test03, which are for
xvalues and rvalues?

I haven't analyzed your patch, but the results seem wrong. We should
not have to do any more work to insert rvalues.

What am I missing?


>diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
>index 39a3f03..8bd72b7 100644
>--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
>+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
>@@ -149,7 +149,7 @@ test01()
> void
> test02()
> {
>-  const X::special expected{ 0, 0, 0, 0, 1, 3 };
>+  const X::special expected{ 0, 1, 0, 0, 2, 3 };
>   X::special ins, emp;
>   {
>     std::vector<X> v;
>@@ -187,7 +187,7 @@ test02()
> void
> test03()
> {
>-  const X::special expected{ 1, 1, 0, 0, 1, 3 };
>+  const X::special expected{ 1, 2, 0, 0, 2, 3 };
>   X::special ins, emp;
>   {
>     std::vector<X> v;

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 1835 bytes --]

On 29/06/16 21:36 +0100, Jonathan Wakely wrote:
>On 29/06/16 21:43 +0200, François Dumont wrote:
>>As asked here is now a patch to only fix the robustness issue. The 
>>consequence is that it is reverting the latest optimization as, 
>>without smart algo, we always need to do a copy to protect against 
>>insertion of values contained in the vector as shown by new tests.
>
>I don't understand. There is no problem with insert(), only with
>emplace(), so why do both get worse?
>
>Also, the problem is with emplacing from an lvalue, so why do the
>number of operations change for test02 and test03, which are for
>xvalues and rvalues?
>
>I haven't analyzed your patch, but the results seem wrong. We should
>not have to do any more work to insert rvalues.
>
>What am I missing?

It seems to me that the minimal fix would be:

--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -312,7 +312,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
          }
        else
          _M_insert_aux(begin() + (__position - cbegin()),
-                       std::forward<_Args>(__args)...);
+                       _Tp(std::forward<_Args>(__args)...));
        return iterator(this->_M_impl._M_start + __n);
       }
 
This causes regressions in the insert_vs_emplace.cc test because we
insert rvalues using emplace:

      iterator
      insert(const_iterator __position, value_type&& __x)
      { return emplace(__position, std::move(__x)); }

That's suboptimal, since in the general case we need an extra
construction for emplacing, but we know that we don't need to do that
when inserting rvalues.

So the correct fix would be to implement inserting rvalues without
using emplace.

The attached patch is a smaller change, and doesn't change the number
of operations for insertions, only for emplacing lvalues.



[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 4019 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index eaafa22..4f43c8e 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -981,6 +981,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       }
 
 #if __cplusplus >= 201103L
+    private:
+      iterator
+      _M_emplace_aux(const_iterator __position, value_type&& __v)
+      { return insert(__position, std::move(__v)); }
+
+      template<typename... _Args>
+	iterator
+	_M_emplace_aux(const_iterator __position, _Args&&... __args)
+	{ return insert(__position, _Tp(std::forward<_Args>(__args)...)); }
+
+    public:
       /**
        *  @brief  Inserts an object in %vector before specified iterator.
        *  @param  __position  A const_iterator into the %vector.
@@ -995,7 +1006,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       template<typename... _Args>
 	iterator
-	emplace(const_iterator __position, _Args&&... __args);
+	emplace(const_iterator __position, _Args&&... __args)
+	{ return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }
 
       /**
        *  @brief  Inserts given value into %vector before specified iterator.
@@ -1039,8 +1051,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  used the user should consider using std::list.
        */
       iterator
-      insert(const_iterator __position, value_type&& __x)
-      { return emplace(__position, std::move(__x)); }
+      insert(const_iterator __position, value_type&& __x);
 
       /**
        *  @brief  Inserts an initializer_list into the %vector.
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 9cb5464..fbcab84 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -297,24 +297,22 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
 #if __cplusplus >= 201103L
   template<typename _Tp, typename _Alloc>
-    template<typename... _Args>
-      typename vector<_Tp, _Alloc>::iterator
-      vector<_Tp, _Alloc>::
-      emplace(const_iterator __position, _Args&&... __args)
-      {
-	const size_type __n = __position - begin();
-	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	    && __position == end())
-	  {
-	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-				     std::forward<_Args>(__args)...);
-	    ++this->_M_impl._M_finish;
-	  }
-	else
-	  _M_insert_aux(begin() + (__position - cbegin()),
-			std::forward<_Args>(__args)...);
-	return iterator(this->_M_impl._M_start + __n);
-      }
+    auto
+    vector<_Tp, _Alloc>::
+    insert(const_iterator __position, value_type&& __v) -> iterator
+    {
+      const auto __n = __position - cbegin();
+      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
+	  && __position == cend())
+	{
+	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				   std::move(__v));
+	  ++this->_M_impl._M_finish;
+	}
+      else
+	_M_insert_aux(begin() + __n, std::move(__v));
+      return iterator(this->_M_impl._M_start + __n);
+    }
 
   template<typename _Tp, typename _Alloc>
     template<typename... _Args>
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
index 39a3f03..1b46124 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
@@ -223,7 +223,8 @@ test03()
 void
 test04()
 {
-  const X::special expected{ 0, 3, 1, 0, 3, 0 };
+  const X::special expected_ins{ 0, 3, 1, 0, 3, 0 };
+  const X::special expected_emp{ 0, 4, 1, 0, 4, 0 };
   X::special ins, emp;
   {
     std::vector<X> v;
@@ -253,8 +254,8 @@ test04()
     // std::cout << "----\n";
     emp = X::sp;
   }
-  VERIFY( ins == emp );
-  VERIFY( ins == expected );
+  VERIFY( ins == expected_ins );
+  VERIFY( emp == expected_emp );
 }
 
 // insert vs emplace xvalue reallocation

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 29/06/16 21:43 +0200, François Dumont wrote:
>I tried those changes too but started having failing tests in 
>vector/ext_pointer so prefer to not touch that for the moment. I think 
>the compilation error was coming from the change of begin() + 
>(__position - cbegin()) into begin() + __n because of overloaded 
>operator+. The 2 other changes should be fine for a future patch.

By the way, I fixed that in my patch too. The problem was that __n had
type size_type, but for adding to iterators it should really be
difference_type. Simply using auto makes it work :-)

Unless you see any problems in my patch I'll finish testing it
tomorrow and commit it with your new testcases.

Thanks for inspiring me to investigate what we were doing wrong! :-)

Re: Improve insert/emplace robustness to self insertion

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 2681 bytes --]

On 29/06/2016 23:30, Jonathan Wakely wrote:
> On 29/06/16 21:36 +0100, Jonathan Wakely wrote:
>> On 29/06/16 21:43 +0200, François Dumont wrote:
>>> As asked here is now a patch to only fix the robustness issue. The 
>>> consequence is that it is reverting the latest optimization as, 
>>> without smart algo, we always need to do a copy to protect against 
>>> insertion of values contained in the vector as shown by new tests.
>>
>> I don't understand. There is no problem with insert(), only with
>> emplace(), so why do both get worse?
>>
>> Also, the problem is with emplacing from an lvalue, so why do the
>> number of operations change for test02 and test03, which are for
>> xvalues and rvalues?
>>
>> I haven't analyzed your patch, but the results seem wrong. We should
>> not have to do any more work to insert rvalues.
>>
>> What am I missing?
>
> It seems to me that the minimal fix would be:
>
> --- a/libstdc++-v3/include/bits/vector.tcc
> +++ b/libstdc++-v3/include/bits/vector.tcc
> @@ -312,7 +312,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>          }
>        else
>          _M_insert_aux(begin() + (__position - cbegin()),
> -                       std::forward<_Args>(__args)...);
> + _Tp(std::forward<_Args>(__args)...));
>        return iterator(this->_M_impl._M_start + __n);
>       }
>
> This causes regressions in the insert_vs_emplace.cc test because we
> insert rvalues using emplace:

This is also why my patch is impacting insert from xvalue or rvalue.

>
>      iterator
>      insert(const_iterator __position, value_type&& __x)
>      { return emplace(__position, std::move(__x)); }
>
> That's suboptimal, since in the general case we need an extra
> construction for emplacing, but we know that we don't need to do that
> when inserting rvalues.

     Why not ? I realized with your remarks that I was missing some 
tests in the new self_insert.cc. The ones to insert an rvalue coming 
from the vector itself. In the attached patch there is those 2 tests, do 
you agree with expected behavior ? For the moment it doesn't check that 
the source value has been indeed moved cause it doesn't, I will update 
it once it does.

     My patch also reorganize a little bit code to avoid redundant 
checks to find out if reallocation is necessary or not. I was also 
thinking about reusing _M_realloc_insert_aux within _M_fill_insert when 
reallocation is needed.

>
> So the correct fix would be to implement inserting rvalues without
> using emplace.
>
> The attached patch is a smaller change, and doesn't change the number
> of operations for insertions, only for emplacing lvalues.
>
>
Ok, go ahead, I will try to rebase mine from yours.

François


[-- Attachment #2: vector_self_insert.patch --]
[-- Type: text/x-patch, Size: 15767 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index eaafa22..c37880a 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -949,7 +949,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus >= 201103L
 	  _M_emplace_back_aux(__x);
 #else
-	  _M_insert_aux(end(), __x);
+	  _M_realloc_insert_aux(end(), __x);
 #endif
       }
 
@@ -1435,21 +1435,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus < 201103L
       void
       _M_insert_aux(iterator __position, const value_type& __x);
-#else
-      template<typename... _Args>
-	static void
-	_S_insert_aux_assign(iterator __pos, _Args&&... __args)
-	{ *__pos =  _Tp(std::forward<_Args>(__args)...); }
-
-      static void
-      _S_insert_aux_assign(iterator __pos, _Tp&& __arg)
-      { *__pos = std::move(__arg); }
 
+      void
+      _M_realloc_insert_aux(iterator __position, const value_type& __x);
+#else
       template<typename... _Args>
 	void
 	_M_insert_aux(iterator __position, _Args&&... __args);
 
       template<typename... _Args>
+        void
+        _M_realloc_insert_aux(iterator __position, _Args&&... __args);
+
+      template<typename... _Args>
 	void
 	_M_emplace_back_aux(_Args&&... __args);
 #endif
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 604be7b..9061593 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -112,27 +112,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
     {
       const size_type __n = __position - begin();
-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	  && __position == end())
-	{
-	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
-	  ++this->_M_impl._M_finish;
-	}
+      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	if (__position == end())
+	  {
+	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
+	    ++this->_M_impl._M_finish;
+	  }
+	else
+#if __cplusplus >= 201103L
+	  _M_insert_aux(begin() + (__position - cbegin()), __x);
+#else
+	  _M_insert_aux(__position, __x);
+#endif
       else
-	{
 #if __cplusplus >= 201103L
-	  const auto __pos = begin() + (__position - cbegin());
-	  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
-	    {
-	      _Tp __x_copy = __x;
-	      _M_insert_aux(__pos, std::move(__x_copy));
-	    }
-	  else
-	    _M_insert_aux(__pos, __x);
+	_M_realloc_insert_aux(begin() + (__position - cbegin()), __x);
 #else
-	    _M_insert_aux(__position, __x);
+	_M_realloc_insert_aux(__position, __x);
 #endif
-	}
+
       return iterator(this->_M_impl._M_start + __n);
     }
 
@@ -303,16 +301,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       emplace(const_iterator __position, _Args&&... __args)
       {
 	const size_type __n = __position - begin();
-	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	    && __position == end())
-	  {
-	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-				     std::forward<_Args>(__args)...);
-	    ++this->_M_impl._M_finish;
-	  }
+	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	  if (__position == end())
+	    {
+	      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				       std::forward<_Args>(__args)...);
+	      ++this->_M_impl._M_finish;
+	    }
+	  else
+	    _M_insert_aux(begin() + (__position - cbegin()),
+			  std::forward<_Args>(__args)...);
 	else
-	  _M_insert_aux(begin() + (__position - cbegin()),
-			std::forward<_Args>(__args)...);
+	  _M_realloc_insert_aux(begin() + (__position - cbegin()),
+				std::forward<_Args>(__args)...);
+
 	return iterator(this->_M_impl._M_start + __n);
       }
 
@@ -327,78 +329,86 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     vector<_Tp, _Alloc>::
     _M_insert_aux(iterator __position, const _Tp& __x)
 #endif
-    {
-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
-	{
-	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-			           _GLIBCXX_MOVE(*(this->_M_impl._M_finish
-				                   - 1)));
-	  ++this->_M_impl._M_finish;
-#if __cplusplus < 201103L
-	  _Tp __x_copy = __x;
+      {
+#if __cplusplus >= 201103L
+	_Tp __x_copy(std::forward<_Args>(__args)...);
+#else
+	_Tp __x_copy(__x);
 #endif
-	  _GLIBCXX_MOVE_BACKWARD3(__position.base(),
-				  this->_M_impl._M_finish - 2,
-				  this->_M_impl._M_finish - 1);
-#if __cplusplus < 201103L
-	  *__position = __x_copy;
+	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				 _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
+	++this->_M_impl._M_finish;
+
+	_GLIBCXX_MOVE_BACKWARD3(__position.base(),
+				this->_M_impl._M_finish - 2,
+				this->_M_impl._M_finish - 1);
+
+	*__position = _GLIBCXX_MOVE(__x_copy);
+      }
+
+#if __cplusplus >= 201103L
+  template<typename _Tp, typename _Alloc>
+    template<typename... _Args>
+      void
+      vector<_Tp, _Alloc>::
+      _M_realloc_insert_aux(iterator __position, _Args&&... __args)
 #else
-	  _S_insert_aux_assign(__position, std::forward<_Args>(__args)...);
+  template<typename _Tp, typename _Alloc>
+    void
+    vector<_Tp, _Alloc>::
+    _M_realloc_insert_aux(iterator __position, const _Tp& __x)
 #endif
-	}
-      else
+    {
+      const size_type __len =
+	_M_check_len(size_type(1), "vector::_M_realloc_insert_aux");
+      const size_type __elems_before = __position - begin();
+      pointer __new_start(this->_M_allocate(__len));
+      pointer __new_finish(__new_start);
+      __try
 	{
-	  const size_type __len =
-	    _M_check_len(size_type(1), "vector::_M_insert_aux");
-	  const size_type __elems_before = __position - begin();
-	  pointer __new_start(this->_M_allocate(__len));
-	  pointer __new_finish(__new_start);
-	  __try
-	    {
-	      // The order of the three operations is dictated by the C++0x
-	      // case, where the moves could alter a new element belonging
-	      // to the existing vector.  This is an issue only for callers
-	      // taking the element by const lvalue ref (see 23.1/13).
-	      _Alloc_traits::construct(this->_M_impl,
-		                       __new_start + __elems_before,
+	  // The order of the three operations is dictated by the C++0x
+	  // case, where the moves could alter a new element belonging
+	  // to the existing vector.  This is an issue only for callers
+	  // taking the element by const lvalue ref (see 23.1/13).
+	  _Alloc_traits::construct(this->_M_impl,
+				   __new_start + __elems_before,
 #if __cplusplus >= 201103L
-				       std::forward<_Args>(__args)...);
+				   std::forward<_Args>(__args)...);
 #else
-	                               __x);
+				   __x);
 #endif
-	      __new_finish = pointer();
+	  __new_finish = pointer();
 
-	      __new_finish
-		= std::__uninitialized_move_if_noexcept_a
-		(this->_M_impl._M_start, __position.base(),
-		 __new_start, _M_get_Tp_allocator());
+	  __new_finish
+	    = std::__uninitialized_move_if_noexcept_a
+	    (this->_M_impl._M_start, __position.base(),
+	     __new_start, _M_get_Tp_allocator());
 
-	      ++__new_finish;
+	  ++__new_finish;
 
-	      __new_finish
-		= std::__uninitialized_move_if_noexcept_a
-		(__position.base(), this->_M_impl._M_finish,
-		 __new_finish, _M_get_Tp_allocator());
-	    }
-          __catch(...)
-	    {
-	      if (!__new_finish)
-		_Alloc_traits::destroy(this->_M_impl,
-		                       __new_start + __elems_before);
-	      else
-		std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
-	      _M_deallocate(__new_start, __len);
-	      __throw_exception_again;
-	    }
-	  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
-			_M_get_Tp_allocator());
-	  _M_deallocate(this->_M_impl._M_start,
-			this->_M_impl._M_end_of_storage
-			- this->_M_impl._M_start);
-	  this->_M_impl._M_start = __new_start;
-	  this->_M_impl._M_finish = __new_finish;
-	  this->_M_impl._M_end_of_storage = __new_start + __len;
+	  __new_finish
+	    = std::__uninitialized_move_if_noexcept_a
+	    (__position.base(), this->_M_impl._M_finish,
+	     __new_finish, _M_get_Tp_allocator());
+	}
+      __catch(...)
+	{
+	  if (!__new_finish)
+	    _Alloc_traits::destroy(this->_M_impl,
+				   __new_start + __elems_before);
+	  else
+	    std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
+	  _M_deallocate(__new_start, __len);
+	  __throw_exception_again;
 	}
+      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+		    _M_get_Tp_allocator());
+      _M_deallocate(this->_M_impl._M_start,
+		    this->_M_impl._M_end_of_storage
+		    - this->_M_impl._M_start);
+      this->_M_impl._M_start = __new_start;
+      this->_M_impl._M_finish = __new_finish;
+      this->_M_impl._M_end_of_storage = __new_start + __len;
     }
 
 #if __cplusplus >= 201103L
@@ -493,7 +503,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	      pointer __new_finish(__new_start);
 	      __try
 		{
-		  // See _M_insert_aux above.
+		  // See _M_realloc_insert_aux above.
 		  std::__uninitialized_fill_n_a(__new_start + __elems_before,
 						__n, __x,
 						_M_get_Tp_allocator());
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
new file mode 100644
index 0000000..d452b5b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
@@ -0,0 +1,144 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void
+test01()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void
+test02()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace won't reallocate.
+  vv.reserve(4);
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+struct A
+{
+  A(int i) : _i(i)
+  { }
+
+  A(const A& other) : _i(other._i)
+  {
+    VERIFY( other._i >= 0 );
+  }
+
+  A(A&& other) : _i(other._i)
+  {
+    VERIFY( other._i >= 0 );
+
+    other._i = -1;
+  }
+
+  A(std::vector<A>::iterator it) : _i(it->_i)
+  {
+    VERIFY( it->_i >= 0 );
+  }
+
+  A& operator=(const A&) = default;
+  A& operator=(A&& other)
+  {
+    VERIFY(other._i >= 0 );
+
+    _i = other._i;
+    other._i = -1;
+    return *this;
+  }
+
+  int _i;
+};
+
+void
+test03()
+{
+  std::vector<A> va =
+    {
+      { A(1) },
+      { A(2) },
+      { A(3) }
+    };
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( va.capacity() == 3 );
+
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+void
+test04()
+{
+  std::vector<A> va =
+    {
+      { A(1) },
+      { A(2) },
+      { A(3) }
+    };
+
+  // Make sure emplace won't reallocate.
+  va.reserve(4);
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
new file mode 100644
index 0000000..7e2f9e2
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
@@ -0,0 +1,113 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure it doesn't reallocate during insertion.
+  vv.reserve(4);
+
+  vv.insert(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void test02()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure we will reallocate for insertion.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.insert(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+
+void test03()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure it doesn't reallocate during insertion.
+  vv.reserve(4);
+
+  vv.insert(vv.begin(), std::move(vv[0]));
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void test04()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure we will reallocate for insertion.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.insert(vv.begin(), std::move(vv[0]));
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
index 39a3f03..8bd72b7 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
@@ -149,7 +149,7 @@ test01()
 void
 test02()
 {
-  const X::special expected{ 0, 0, 0, 0, 1, 3 };
+  const X::special expected{ 0, 1, 0, 0, 2, 3 };
   X::special ins, emp;
   {
     std::vector<X> v;
@@ -187,7 +187,7 @@ test02()
 void
 test03()
 {
-  const X::special expected{ 1, 1, 0, 0, 1, 3 };
+  const X::special expected{ 1, 2, 0, 0, 2, 3 };
   X::special ins, emp;
   {
     std::vector<X> v;

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 30/06/16 21:51 +0200, François Dumont wrote:
>On 29/06/2016 23:30, Jonathan Wakely wrote:
>>
>>     iterator
>>     insert(const_iterator __position, value_type&& __x)
>>     { return emplace(__position, std::move(__x)); }
>>
>>That's suboptimal, since in the general case we need an extra
>>construction for emplacing, but we know that we don't need to do that
>>when inserting rvalues.
>
>    Why not ? I realized with your remarks that I was missing some 
>tests in the new self_insert.cc. The ones to insert an rvalue coming 
>from the vector itself. In the attached patch there is those 2 tests, 
>do you agree with expected behavior ? For the moment it doesn't check 
>that the source value has been indeed moved cause it doesn't, I will 
>update it once it does.

No, I don't agree, because this is undefined behaviour:

   vv.insert(vv.begin(), std::move(vv[0]));

We don't need to support that case.

17.6.4.9 [res.on.arguments] says:

— If a function argument binds to an rvalue reference parameter, the
  implementation may assume that this parameter is a unique reference
  to this argument.

i.e. when passed an rvalue we can assume it is not a reference to
something in the container.

That's why we should not perform any more operations when inserting
rvalues than we do now. Any increase in copies/moves for inserting
rvalues is a regression, and should be avoided.

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 1644 bytes --]

On 01/07/16 10:54 +0100, Jonathan Wakely wrote:
>On 30/06/16 21:51 +0200, François Dumont wrote:
>>On 29/06/2016 23:30, Jonathan Wakely wrote:
>>>
>>>    iterator
>>>    insert(const_iterator __position, value_type&& __x)
>>>    { return emplace(__position, std::move(__x)); }
>>>
>>>That's suboptimal, since in the general case we need an extra
>>>construction for emplacing, but we know that we don't need to do that
>>>when inserting rvalues.
>>
>>   Why not ? I realized with your remarks that I was missing some 
>>tests in the new self_insert.cc. The ones to insert an rvalue coming 
>>from the vector itself. In the attached patch there is those 2 
>>tests, do you agree with expected behavior ? For the moment it 
>>doesn't check that the source value has been indeed moved cause it 
>>doesn't, I will update it once it does.
>
>No, I don't agree, because this is undefined behaviour:
>
>  vv.insert(vv.begin(), std::move(vv[0]));
>
>We don't need to support that case.
>
>17.6.4.9 [res.on.arguments] says:
>
>— If a function argument binds to an rvalue reference parameter, the
> implementation may assume that this parameter is a unique reference
> to this argument.
>
>i.e. when passed an rvalue we can assume it is not a reference to
>something in the container.
>
>That's why we should not perform any more operations when inserting
>rvalues than we do now. Any increase in copies/moves for inserting
>rvalues is a regression, and should be avoided.


Here's what I'm planning to commit soon. This also fixes a problem
where the temporaries we create are not constructed+destroyed with the
allocator, which they must be.



[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 22329 bytes --]

commit 6012a80b33eab6501cd620fb710f9805d21cc4b3
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Fri Jul 1 16:49:15 2016 +0100

    Add tests for inserting aliased objects into std::vector
    
    2016-07-01  Fran??ois Dumont  <fdumont@gcc.gnu.org>
    
    	* testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc:
    	New test.
    	* testsuite/23_containers/vector/modifiers/insert/self_insert.cc: New
    	test.

diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
new file mode 100644
index 0000000..d452b5b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
@@ -0,0 +1,144 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void
+test01()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void
+test02()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace won't reallocate.
+  vv.reserve(4);
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+struct A
+{
+  A(int i) : _i(i)
+  { }
+
+  A(const A& other) : _i(other._i)
+  {
+    VERIFY( other._i >= 0 );
+  }
+
+  A(A&& other) : _i(other._i)
+  {
+    VERIFY( other._i >= 0 );
+
+    other._i = -1;
+  }
+
+  A(std::vector<A>::iterator it) : _i(it->_i)
+  {
+    VERIFY( it->_i >= 0 );
+  }
+
+  A& operator=(const A&) = default;
+  A& operator=(A&& other)
+  {
+    VERIFY(other._i >= 0 );
+
+    _i = other._i;
+    other._i = -1;
+    return *this;
+  }
+
+  int _i;
+};
+
+void
+test03()
+{
+  std::vector<A> va =
+    {
+      { A(1) },
+      { A(2) },
+      { A(3) }
+    };
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( va.capacity() == 3 );
+
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+void
+test04()
+{
+  std::vector<A> va =
+    {
+      { A(1) },
+      { A(2) },
+      { A(3) }
+    };
+
+  // Make sure emplace won't reallocate.
+  va.reserve(4);
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
new file mode 100644
index 0000000..9944cbb
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
@@ -0,0 +1,70 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure it doesn't reallocate during insertion.
+  vv.reserve(4);
+
+  vv.insert(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void test02()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure we will reallocate for insertion.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.insert(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+int main()
+{
+  test01();
+  test02();
+}

commit c38bd73249185319d04259623dd25fb0939569a3
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Fri Jul 1 15:42:49 2016 +0100

    Fix std::vector's use of temporary objects
    
    	* include/bits/stl_vector.h (emplace(const_iterator, _Args&&...)):
    	Define inline. Forward to _M_emplace_aux.
    	(insert(const_iterator, value_type&&)): Forward to _M_insert_rval.
    	(_M_insert_rval, _M_emplace_aux): Declare new functions.
    	(_Temporary_value): New RAII type using allocator to construct/destroy.
    	(_S_insert_aux_assign): Remove.
    	(_M_insert_aux): Make non-variadic.
    	* include/bits/vector.tcc (insert(const_iterator, const value_type&)):
    	Use _Temporary_value.
    	(emplace(const_iterator, _Args&&...)): Remove definition.
    	(_M_insert_rval, _M_emplace_aux): Define.
    	(_M_insert_aux): Make non-variadic, stop using _S_insert_aux_assign.
    	(_M_fill_insert): Use _Temporary_value.
    	* testsuite/23_containers/vector/allocator/construction.cc: New test.
    	* testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc:
    	Adjust expected results for emplacing an lvalue with reallocation.
    	* testsuite/23_containers/vector/check_construct_destroy.cc: Adjust
    	expected results to account for construction/destruction of temporary
    	using allocator.

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index eaafa22..8e8aa7c 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -995,7 +995,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       template<typename... _Args>
 	iterator
-	emplace(const_iterator __position, _Args&&... __args);
+	emplace(const_iterator __position, _Args&&... __args)
+	{ return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }
 
       /**
        *  @brief  Inserts given value into %vector before specified iterator.
@@ -1040,7 +1041,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       iterator
       insert(const_iterator __position, value_type&& __x)
-      { return emplace(__position, std::move(__x)); }
+      { return _M_insert_rval(__position, std::move(__x)); }
 
       /**
        *  @brief  Inserts an initializer_list into the %vector.
@@ -1431,30 +1432,65 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _M_shrink_to_fit();
 #endif
 
-      // Called by insert(p,x)
 #if __cplusplus < 201103L
+      // Called by insert(p,x)
       void
       _M_insert_aux(iterator __position, const value_type& __x);
 #else
-      template<typename... _Args>
-	static void
-	_S_insert_aux_assign(iterator __pos, _Args&&... __args)
-	{ *__pos =  _Tp(std::forward<_Args>(__args)...); }
+      // A value_type object constructed with _Alloc_traits::construct()
+      // and destroyed with _Alloc_traits::destroy().
+      struct _Temporary_value
+      {
+	template<typename... _Args>
+	  explicit
+	  _Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec)
+	  {
+	    _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(),
+				     std::forward<_Args>(__args)...);
+	  }
 
-      static void
-      _S_insert_aux_assign(iterator __pos, _Tp&& __arg)
-      { *__pos = std::move(__arg); }
+	~_Temporary_value()
+	{ _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); }
 
-      template<typename... _Args>
+	value_type&
+	_M_val() { return *reinterpret_cast<_Tp*>(&__buf); }
+
+      private:
+	pointer
+	_M_ptr() { return pointer_traits<pointer>::pointer_to(_M_val()); }
+
+	vector* _M_this;
+	typename aligned_storage<sizeof(_Tp), alignof(_Tp)>::type __buf;
+      };
+
+      // Called by insert(p,x) and other functions when insertion needs to
+      // reallocate or move existing elements. _Arg is either _Tp& or _Tp.
+      template<typename _Arg>
 	void
-	_M_insert_aux(iterator __position, _Args&&... __args);
+	_M_insert_aux(iterator __position, _Arg&& __arg);
 
+      // Either move-construct at the end, or forward to _M_insert_aux.
+      iterator
+      _M_insert_rval(const_iterator __position, value_type&& __v);
+
+      // Called by push_back(x) and emplace_back(args) when they need to
+      // reallocate.
       template<typename... _Args>
 	void
 	_M_emplace_back_aux(_Args&&... __args);
+
+      // Try to emplace at the end, otherwise forward to _M_insert_aux.
+      template<typename... _Args>
+	iterator
+	_M_emplace_aux(const_iterator __position, _Args&&... __args);
+
+      // Emplacing an rvalue of the correct type can use _M_insert_rval.
+      iterator
+      _M_emplace_aux(const_iterator __position, value_type&& __v)
+      { return _M_insert_rval(__position, std::move(__v)); }
 #endif
 
-      // Called by the latter.
+      // Called by _M_fill_insert, _M_insert_aux etc.
       size_type
       _M_check_len(size_type __n, const char* __s) const
       {
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 9cb5464..dce583b 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -124,8 +124,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  const auto __pos = begin() + (__position - cbegin());
 	  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 	    {
-	      _Tp __x_copy = __x;
-	      _M_insert_aux(__pos, std::move(__x_copy));
+	      // __x could be an existing element of this vector, so make a
+	      // copy of it before _M_insert_aux moves elements around.
+	      _Temporary_value __x_copy(this, __x);
+	      _M_insert_aux(__pos, std::move(__x_copy._M_val()));
 	    }
 	  else
 	    _M_insert_aux(__pos, __x);
@@ -297,30 +299,49 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
 #if __cplusplus >= 201103L
   template<typename _Tp, typename _Alloc>
+    auto
+    vector<_Tp, _Alloc>::
+    _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
+    {
+      const auto __n = __position - cbegin();
+      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
+	  && __position == cend())
+	{
+	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				   std::move(__v));
+	  ++this->_M_impl._M_finish;
+	}
+      else
+	_M_insert_aux(begin() + __n, std::move(__v));
+      return iterator(this->_M_impl._M_start + __n);
+    }
+
+  template<typename _Tp, typename _Alloc>
     template<typename... _Args>
-      typename vector<_Tp, _Alloc>::iterator
+      auto
       vector<_Tp, _Alloc>::
-      emplace(const_iterator __position, _Args&&... __args)
+      _M_emplace_aux(const_iterator __position, _Args&&... __args)
+      -> iterator
       {
-	const size_type __n = __position - begin();
-	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	    && __position == end())
-	  {
-	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-				     std::forward<_Args>(__args)...);
-	    ++this->_M_impl._M_finish;
-	  }
+	const auto __n = __position - cbegin();
+	if (__position == cend())
+	  emplace_back(std::forward<_Args>(__args)...);
 	else
-	  _M_insert_aux(begin() + (__position - cbegin()),
-			std::forward<_Args>(__args)...);
+	  {
+	    // We need to construct a temporary because something in __args...
+	    // could alias one of the elements of the container and so we
+	    // need to use it before _M_insert_aux moves elements around.
+	    _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
+	    _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
+	  }
 	return iterator(this->_M_impl._M_start + __n);
       }
 
   template<typename _Tp, typename _Alloc>
-    template<typename... _Args>
+    template<typename _Arg>
       void
       vector<_Tp, _Alloc>::
-      _M_insert_aux(iterator __position, _Args&&... __args)
+      _M_insert_aux(iterator __position, _Arg&& __arg)
 #else
   template<typename _Tp, typename _Alloc>
     void
@@ -343,7 +364,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus < 201103L
 	  *__position = __x_copy;
 #else
-	  _S_insert_aux_assign(__position, std::forward<_Args>(__args)...);
+	  *__position = std::forward<_Arg>(__arg);
 #endif
 	}
       else
@@ -355,14 +376,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  pointer __new_finish(__new_start);
 	  __try
 	    {
-	      // The order of the three operations is dictated by the C++0x
+	      // The order of the three operations is dictated by the C++11
 	      // case, where the moves could alter a new element belonging
 	      // to the existing vector.  This is an issue only for callers
 	      // taking the element by const lvalue ref (see 23.1/13).
+	      // TODO fix reference to standard.
 	      _Alloc_traits::construct(this->_M_impl,
 		                       __new_start + __elems_before,
 #if __cplusplus >= 201103L
-				       std::forward<_Args>(__args)...);
+				       std::forward<_Arg>(__arg));
 #else
 	                               __x);
 #endif
@@ -455,7 +477,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  if (size_type(this->_M_impl._M_end_of_storage
 			- this->_M_impl._M_finish) >= __n)
 	    {
+#if __cplusplus < 201103L
 	      value_type __x_copy = __x;
+#else
+	      _Temporary_value __tmp(this, __x);
+	      value_type& __x_copy = __tmp._M_val();
+#endif
 	      const size_type __elems_after = end() - __position;
 	      pointer __old_finish(this->_M_impl._M_finish);
 	      if (__elems_after > __n)
diff --git a/libstdc++-v3/testsuite/23_containers/vector/allocator/construction.cc b/libstdc++-v3/testsuite/23_containers/vector/allocator/construction.cc
new file mode 100644
index 0000000..8040949
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/allocator/construction.cc
@@ -0,0 +1,105 @@
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+// { dg-do compile }
+
+#include <vector>
+
+struct Tag { };
+
+template<typename T>
+  struct TaggingAllocator
+  {
+    using value_type = T;
+
+    TaggingAllocator() = default;
+
+    template<typename U>
+      TaggingAllocator(const TaggingAllocator<U>&) { }
+
+    T*
+    allocate(std::size_t n) { return std::allocator<T>{}.allocate(n); }
+
+    void
+    deallocate(T* p, std::size_t n) { std::allocator<T>{}.deallocate(p, n); }
+
+    template<typename U, typename... Args>
+      void
+      construct(U* p, Args&&... args)
+      { ::new((void*)p) U(Tag{}, std::forward<Args>(args)...); }
+
+    template<typename U, typename... Args>
+      void
+      destroy(U* p)
+      { p->~U(); }
+  };
+
+template<typename T, typename U>
+  bool
+  operator==(const TaggingAllocator<T>&, const TaggingAllocator<U>&)
+  { return true; }
+
+template<typename T, typename U>
+  bool
+  operator!=(const TaggingAllocator<T>&, const TaggingAllocator<U>&)
+  { return false; }
+
+struct X
+{
+  // All constructors must be passed the Tag type.
+
+  // DefaultInsertable into vector<X, TaggingAllocator<X>>,
+  X(Tag) { }
+  // CopyInsertable into vector<X, TaggingAllocator<X>>,
+  X(Tag, const X&) { }
+  // MoveInsertable into vector<X, TaggingAllocator<X>>, and
+  X(Tag, X&&) { }
+
+  // EmplaceConstructible into vector<X, TaggingAllocator<X>> from args.
+  template<typename... Args>
+    X(Tag, Args&&...) { }
+
+  // not DefaultConstructible, CopyConstructible or MoveConstructible.
+  X() = delete;
+  X(const X&) = delete;
+  X(X&&) = delete;
+
+  // CopyAssignable.
+  X& operator=(const X&) { return *this; }
+
+  // MoveAssignable.
+  X& operator=(X&&) { return *this; }
+
+private:
+  // Not Destructible.
+  ~X() { }
+
+  // Erasable from vector<X, TaggingAllocator<X>>.
+  friend class TaggingAllocator<X>;
+};
+
+template class std::vector<X, TaggingAllocator<X>>;
+
+void test01()
+{
+  std::vector<X, TaggingAllocator<X>> v;
+  v.reserve(3);
+  v.emplace_back();
+  v.emplace(v.begin());
+  v.emplace(v.begin(), 1, 2, 3);
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/check_construct_destroy.cc b/libstdc++-v3/testsuite/23_containers/vector/check_construct_destroy.cc
index cf2f7c7..b92a152 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/check_construct_destroy.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/check_construct_destroy.cc
@@ -49,9 +49,9 @@ int main()
     c.reserve(100);
     tracker_allocator_counter::reset();
     c.insert(c.begin(), arr10[0]);
-    ok = check_construct_destroy("Insert element", 1, 0) && ok;
+    ok = check_construct_destroy("Insert element", 2, 1) && ok;
   }
-  ok = check_construct_destroy("Insert element", 1, 11) && ok;
+  ok = check_construct_destroy("Insert element", 2, 12) && ok;
 
   {
     Container c(arr10, arr10 + 10);
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
index 39a3f03..1b46124 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
@@ -223,7 +223,8 @@ test03()
 void
 test04()
 {
-  const X::special expected{ 0, 3, 1, 0, 3, 0 };
+  const X::special expected_ins{ 0, 3, 1, 0, 3, 0 };
+  const X::special expected_emp{ 0, 4, 1, 0, 4, 0 };
   X::special ins, emp;
   {
     std::vector<X> v;
@@ -253,8 +254,8 @@ test04()
     // std::cout << "----\n";
     emp = X::sp;
   }
-  VERIFY( ins == emp );
-  VERIFY( ins == expected );
+  VERIFY( ins == expected_ins );
+  VERIFY( emp == expected_emp );
 }
 
 // insert vs emplace xvalue reallocation
diff --git a/libstdc++-v3/testsuite/backward/hash_set/check_construct_destroy.cc b/libstdc++-v3/testsuite/backward/hash_set/check_construct_destroy.cc
index 5693c76..5740fe1 100644
--- a/libstdc++-v3/testsuite/backward/hash_set/check_construct_destroy.cc
+++ b/libstdc++-v3/testsuite/backward/hash_set/check_construct_destroy.cc
@@ -39,45 +39,48 @@ int main()
 
   int buckets;
 
+  // Add 1 to all counts, because the std::vector used internally by the
+  // hashtable creates and destroys a temporary object using the allocator.
+
   tracker_allocator_counter::reset();
   {
     Container c;
     buckets = c.bucket_count();
-    ok = check_construct_destroy("empty container", buckets, 0) && ok;
+    ok = check_construct_destroy("empty container", buckets+1, 1) && ok;
   }
-  ok = check_construct_destroy("empty container", buckets, buckets) && ok;
+  ok = check_construct_destroy("empty container", buckets+1, buckets+1) && ok;
 
 
   tracker_allocator_counter::reset();
   {
     Container c(arr10, arr10 + 10);
-    ok = check_construct_destroy("Construct from range", buckets+10, 0) && ok;
+    ok = check_construct_destroy("Construct from range", buckets+10+1, 1) && ok;
   }
-  ok = check_construct_destroy("Construct from range", buckets+10, buckets+10) && ok;
+  ok = check_construct_destroy("Construct from range", buckets+10+1, buckets+10+1) && ok;
 
   tracker_allocator_counter::reset();
   {
     Container c(arr10, arr10 + 10);
     c.insert(arr10a[0]);
-    ok = check_construct_destroy("Insert element", buckets+11, 0) && ok;
+    ok = check_construct_destroy("Insert element", buckets+11+1, 1) && ok;
   }
-  ok = check_construct_destroy("Insert element", buckets+11, buckets+11) && ok;
+  ok = check_construct_destroy("Insert element", buckets+11+1, buckets+11+1) && ok;
 
   tracker_allocator_counter::reset();
   {
     Container c(arr10, arr10 + 10);
     c.insert(arr10a, arr10a+3);
-    ok = check_construct_destroy("Insert short range", buckets+13, 0) && ok;
+    ok = check_construct_destroy("Insert short range", buckets+13+1, 1) && ok;
   }
-  ok = check_construct_destroy("Insert short range", buckets+13, buckets+13) && ok;
+  ok = check_construct_destroy("Insert short range", buckets+13+1, buckets+13+1) && ok;
 
   tracker_allocator_counter::reset();
   {
     Container c(arr10, arr10 + 10);
     c.insert(arr10a, arr10a+10);
-    ok = check_construct_destroy("Insert long range", buckets+20, 0) && ok;
+    ok = check_construct_destroy("Insert long range", buckets+20+1, 1) && ok;
   }
-  ok = check_construct_destroy("Insert long range", buckets+20, buckets+20) && ok;
+  ok = check_construct_destroy("Insert long range", buckets+20+1, buckets+20+1) && ok;
 
   return ok ? 0 : 1;
 }

Re: Improve insert/emplace robustness to self insertion

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 1975 bytes --]

On 01/07/2016 11:54, Jonathan Wakely wrote:
> On 30/06/16 21:51 +0200, François Dumont wrote:
>> On 29/06/2016 23:30, Jonathan Wakely wrote:
>>>
>>>     iterator
>>>     insert(const_iterator __position, value_type&& __x)
>>>     { return emplace(__position, std::move(__x)); }
>>>
>>> That's suboptimal, since in the general case we need an extra
>>> construction for emplacing, but we know that we don't need to do that
>>> when inserting rvalues.
>>
>>    Why not ? I realized with your remarks that I was missing some 
>> tests in the new self_insert.cc. The ones to insert an rvalue coming 
>> from the vector itself. In the attached patch there is those 2 tests, 
>> do you agree with expected behavior ? For the moment it doesn't check 
>> that the source value has been indeed moved cause it doesn't, I will 
>> update it once it does.
>
> No, I don't agree, because this is undefined behaviour:
>
>   vv.insert(vv.begin(), std::move(vv[0]));
>
> We don't need to support that case.

Ok but management of this kind of code is a nice consequence of using 
the smart insertion trick.

>
> 17.6.4.9 [res.on.arguments] says:
>
> — If a function argument binds to an rvalue reference parameter, the
>  implementation may assume that this parameter is a unique reference
>  to this argument.
>
> i.e. when passed an rvalue we can assume it is not a reference to
> something in the container.
>
> That's why we should not perform any more operations when inserting
> rvalues than we do now. Any increase in copies/moves for inserting
> rvalues is a regression, and should be avoided

Agree so in attached patch I have implemented the smart insertion trick 
to come back to optimal copies/moves. We don't need to do much to do 
better than Standard requirement and especially not additional copies/moves.

I haven't consider in this patch your remark about using allocator to 
build instance so don't hesitate to commit what you want and I will rebase.

François


[-- Attachment #2: vector_optim.patch --]
[-- Type: text/x-patch, Size: 7687 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index c37880a..d7435cc 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -1432,17 +1432,33 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
 
       // Called by insert(p,x)
+      void
+      _M_insert_aux(iterator __position, const value_type& __x)
+      { _M_insert_value_aux(__position, __x); }
+
 #if __cplusplus < 201103L
       void
-      _M_insert_aux(iterator __position, const value_type& __x);
+      _M_insert_value_aux(iterator __position, const value_type& __x);
 
       void
       _M_realloc_insert_aux(iterator __position, const value_type& __x);
 #else
+      template<typename _Val>
+        void
+        _M_insert_value_aux(iterator __position, _Val&& __x);
+
       template<typename... _Args>
 	void
 	_M_insert_aux(iterator __position, _Args&&... __args);
 
+      void
+      _M_insert_aux(iterator __position, value_type& __x)
+      { _M_insert_value_aux(__position, __x); }
+
+      void
+      _M_insert_aux(iterator __position, value_type&& __x)
+      { _M_insert_value_aux(__position, std::move(__x)); }
+
       template<typename... _Args>
         void
         _M_realloc_insert_aux(iterator __position, _Args&&... __args);
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 9061593..fe57db2 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -56,6 +56,8 @@
 #ifndef _VECTOR_TCC
 #define _VECTOR_TCC 1
 
+#include <bits/stl_function.h> // For std::less.
+
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
@@ -120,9 +122,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  }
 	else
 #if __cplusplus >= 201103L
-	  _M_insert_aux(begin() + (__position - cbegin()), __x);
+	  _M_insert_value_aux(begin() + (__position - cbegin()), __x);
 #else
-	  _M_insert_aux(__position, __x);
+	  _M_insert_value_aux(__position, __x);
 #endif
       else
 #if __cplusplus >= 201103L
@@ -323,28 +325,46 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       void
       vector<_Tp, _Alloc>::
       _M_insert_aux(iterator __position, _Args&&... __args)
+      {
+	_Tp __x_copy(std::forward<_Args>(__args)...);
+	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				 std::move(*(this->_M_impl._M_finish - 1)));
+	std::move_backward(__position.base(), this->_M_impl._M_finish - 1,
+			   this->_M_impl._M_finish);
+
+	++this->_M_impl._M_finish;
+
+	*__position = std::move(__x_copy);
+      }
+
+  template<typename _Tp, typename _Alloc>
+    template<typename _Val>
+      void
+      vector<_Tp, _Alloc>::
+      _M_insert_value_aux(iterator __position, _Val&& __x)
 #else
   template<typename _Tp, typename _Alloc>
     void
     vector<_Tp, _Alloc>::
-    _M_insert_aux(iterator __position, const _Tp& __x)
+    _M_insert_value_aux(iterator __position, const _Tp& __x)
 #endif
-      {
-#if __cplusplus >= 201103L
-	_Tp __x_copy(std::forward<_Args>(__args)...);
-#else
-	_Tp __x_copy(__x);
-#endif
-	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-				 _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
-	++this->_M_impl._M_finish;
+    {
+      __decltype(std::__addressof(__x)) __ptr = std::__addressof(__x);
+      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+			       _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
+      _GLIBCXX_MOVE_BACKWARD3(__position.base(), this->_M_impl._M_finish - 1,
+			      this->_M_impl._M_finish);
 
-	_GLIBCXX_MOVE_BACKWARD3(__position.base(),
-				this->_M_impl._M_finish - 2,
-				this->_M_impl._M_finish - 1);
+      ++this->_M_impl._M_finish;
 
-	*__position = _GLIBCXX_MOVE(__x_copy);
-      }
+      typedef std::less<const _Tp*> _Less;
+      _GLIBCXX_USE_CONSTEXPR _Less __l{};
+      if (!__l(__ptr, _M_data_ptr(__position.base()))
+	  && !__l(_M_data_ptr(this->_M_impl._M_finish - 1), __ptr))
+	++__ptr;
+
+      *__position = _GLIBCXX_FORWARD(_Val, *__ptr);
+    }
 
 #if __cplusplus >= 201103L
   template<typename _Tp, typename _Alloc>
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
index d452b5b..196d1c0 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
@@ -63,6 +63,51 @@ test02()
   VERIFY( vv[0][1] == 3 );
 }
 
+void
+test03()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.emplace(vv.begin(), std::move(vv[0]));
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+
+  VERIFY( vv[1].empty() );
+}
+
+void
+test04()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace won't reallocate.
+  vv.reserve(4);
+  vv.emplace(vv.begin(), std::move(vv[0]));
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+
+  VERIFY( vv[1].empty() );
+}
+
 struct A
 {
   A(int i) : _i(i)
@@ -99,7 +144,7 @@ struct A
 };
 
 void
-test03()
+test05()
 {
   std::vector<A> va =
     {
@@ -118,7 +163,7 @@ test03()
 }
 
 void
-test04()
+test06()
 {
   std::vector<A> va =
     {
@@ -141,4 +186,6 @@ int main()
   test02();
   test03();
   test04();
+  test05();
+  test06();
 }
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
index 7e2f9e2..a70d621 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
@@ -41,6 +41,8 @@ void test01()
   VERIFY( vv[0].size() == 2 );
   VERIFY( vv[0][0] == 2 );
   VERIFY( vv[0][1] == 3 );
+
+  VERIFY( vv[1].size() == 2 );
 }
 
 void test02()
@@ -61,6 +63,8 @@ void test02()
   VERIFY( vv[0].size() == 2 );
   VERIFY( vv[0][0] == 2 );
   VERIFY( vv[0][1] == 3 );
+
+  VERIFY( vv[1].size() == 2 );
 }
 
 
@@ -82,6 +86,8 @@ void test03()
   VERIFY( vv[0].size() == 2 );
   VERIFY( vv[0][0] == 2 );
   VERIFY( vv[0][1] == 3 );
+
+  VERIFY( vv[1].empty() );
 }
 
 void test04()
@@ -102,6 +108,8 @@ void test04()
   VERIFY( vv[0].size() == 2 );
   VERIFY( vv[0][0] == 2 );
   VERIFY( vv[0][1] == 3 );
+
+  VERIFY( vv[1].empty() );
 }
 
 int main()
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
index 8bd72b7..4c9c57e 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
@@ -111,7 +111,7 @@ operator==(const X::special& lhs, const X::special& rhs)
 void
 test01()
 {
-  const X::special expected{ 0, 1, 1, 0, 1, 3 };
+  const X::special expected{ 0, 0, 0, 1, 1, 2 };
   X::special ins, emp;
   {
     std::vector<X> v;
@@ -149,7 +149,7 @@ test01()
 void
 test02()
 {
-  const X::special expected{ 0, 1, 0, 0, 2, 3 };
+  const X::special expected{ 0, 0, 0, 0, 1, 3 };
   X::special ins, emp;
   {
     std::vector<X> v;
@@ -187,7 +187,7 @@ test02()
 void
 test03()
 {
-  const X::special expected{ 1, 2, 0, 0, 2, 3 };
+  const X::special expected{ 1, 1, 0, 0, 1, 3 };
   X::special ins, emp;
   {
     std::vector<X> v;

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 423 bytes --]

On 02/07/16 08:37 +0200, François Dumont wrote:
>I haven't consider in this patch your remark about using allocator to 
>build instance so don't hesitate to commit what you want and I will 
>rebase.

Here's what I've committed to trunk.

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.



[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 22614 bytes --]

commit 6aa6fa55a89c34c51366ed432bd942e09f691a0b
Author: redi <redi@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Mon Jul 4 14:52:54 2016 +0000

    Add tests for inserting aliased objects into std::vector
    
    2016-07-04  Fran??ois Dumont  <fdumont@gcc.gnu.org>
    
    	* testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc:
    	New test.
    	* testsuite/23_containers/vector/modifiers/insert/self_insert.cc: New
    	test.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@237986 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
new file mode 100644
index 0000000..d452b5b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
@@ -0,0 +1,144 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void
+test01()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void
+test02()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace won't reallocate.
+  vv.reserve(4);
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+struct A
+{
+  A(int i) : _i(i)
+  { }
+
+  A(const A& other) : _i(other._i)
+  {
+    VERIFY( other._i >= 0 );
+  }
+
+  A(A&& other) : _i(other._i)
+  {
+    VERIFY( other._i >= 0 );
+
+    other._i = -1;
+  }
+
+  A(std::vector<A>::iterator it) : _i(it->_i)
+  {
+    VERIFY( it->_i >= 0 );
+  }
+
+  A& operator=(const A&) = default;
+  A& operator=(A&& other)
+  {
+    VERIFY(other._i >= 0 );
+
+    _i = other._i;
+    other._i = -1;
+    return *this;
+  }
+
+  int _i;
+};
+
+void
+test03()
+{
+  std::vector<A> va =
+    {
+      { A(1) },
+      { A(2) },
+      { A(3) }
+    };
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( va.capacity() == 3 );
+
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+void
+test04()
+{
+  std::vector<A> va =
+    {
+      { A(1) },
+      { A(2) },
+      { A(3) }
+    };
+
+  // Make sure emplace won't reallocate.
+  va.reserve(4);
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
new file mode 100644
index 0000000..9944cbb
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
@@ -0,0 +1,70 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure it doesn't reallocate during insertion.
+  vv.reserve(4);
+
+  vv.insert(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void test02()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure we will reallocate for insertion.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.insert(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+int main()
+{
+  test01();
+  test02();
+}

commit c1e8e16c5c977ebc08d3a76e5ae9428b693d8a8c
Author: redi <redi@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Mon Jul 4 14:52:46 2016 +0000

    Fix std::vector's use of temporary objects
    
    	* include/bits/stl_vector.h (emplace(const_iterator, _Args&&...)):
    	Define inline. Forward to _M_emplace_aux.
    	(insert(const_iterator, value_type&&)): Forward to _M_insert_rval.
    	(_M_insert_rval, _M_emplace_aux): Declare new functions.
    	(_Temporary_value): New RAII type using allocator to construct/destroy.
    	(_S_insert_aux_assign): Remove.
    	(_M_insert_aux): Make non-variadic.
    	* include/bits/vector.tcc (insert(const_iterator, const value_type&)):
    	Use _Temporary_value.
    	(emplace(const_iterator, _Args&&...)): Remove definition.
    	(_M_insert_rval, _M_emplace_aux): Define.
    	(_M_insert_aux): Make non-variadic, stop using _S_insert_aux_assign.
    	(_M_fill_insert): Use _Temporary_value.
    	* testsuite/23_containers/vector/allocator/construction.cc: New test.
    	* testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc:
    	Adjust expected results for emplacing an lvalue with reallocation.
    	* testsuite/23_containers/vector/check_construct_destroy.cc: Adjust
    	expected results to account for construction/destruction of temporary
    	using allocator.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@237985 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index eaafa22..8e8aa7c 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -995,7 +995,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       template<typename... _Args>
 	iterator
-	emplace(const_iterator __position, _Args&&... __args);
+	emplace(const_iterator __position, _Args&&... __args)
+	{ return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }
 
       /**
        *  @brief  Inserts given value into %vector before specified iterator.
@@ -1040,7 +1041,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       iterator
       insert(const_iterator __position, value_type&& __x)
-      { return emplace(__position, std::move(__x)); }
+      { return _M_insert_rval(__position, std::move(__x)); }
 
       /**
        *  @brief  Inserts an initializer_list into the %vector.
@@ -1431,30 +1432,65 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _M_shrink_to_fit();
 #endif
 
-      // Called by insert(p,x)
 #if __cplusplus < 201103L
+      // Called by insert(p,x)
       void
       _M_insert_aux(iterator __position, const value_type& __x);
 #else
-      template<typename... _Args>
-	static void
-	_S_insert_aux_assign(iterator __pos, _Args&&... __args)
-	{ *__pos =  _Tp(std::forward<_Args>(__args)...); }
+      // A value_type object constructed with _Alloc_traits::construct()
+      // and destroyed with _Alloc_traits::destroy().
+      struct _Temporary_value
+      {
+	template<typename... _Args>
+	  explicit
+	  _Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec)
+	  {
+	    _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(),
+				     std::forward<_Args>(__args)...);
+	  }
 
-      static void
-      _S_insert_aux_assign(iterator __pos, _Tp&& __arg)
-      { *__pos = std::move(__arg); }
+	~_Temporary_value()
+	{ _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); }
 
-      template<typename... _Args>
+	value_type&
+	_M_val() { return *reinterpret_cast<_Tp*>(&__buf); }
+
+      private:
+	pointer
+	_M_ptr() { return pointer_traits<pointer>::pointer_to(_M_val()); }
+
+	vector* _M_this;
+	typename aligned_storage<sizeof(_Tp), alignof(_Tp)>::type __buf;
+      };
+
+      // Called by insert(p,x) and other functions when insertion needs to
+      // reallocate or move existing elements. _Arg is either _Tp& or _Tp.
+      template<typename _Arg>
 	void
-	_M_insert_aux(iterator __position, _Args&&... __args);
+	_M_insert_aux(iterator __position, _Arg&& __arg);
 
+      // Either move-construct at the end, or forward to _M_insert_aux.
+      iterator
+      _M_insert_rval(const_iterator __position, value_type&& __v);
+
+      // Called by push_back(x) and emplace_back(args) when they need to
+      // reallocate.
       template<typename... _Args>
 	void
 	_M_emplace_back_aux(_Args&&... __args);
+
+      // Try to emplace at the end, otherwise forward to _M_insert_aux.
+      template<typename... _Args>
+	iterator
+	_M_emplace_aux(const_iterator __position, _Args&&... __args);
+
+      // Emplacing an rvalue of the correct type can use _M_insert_rval.
+      iterator
+      _M_emplace_aux(const_iterator __position, value_type&& __v)
+      { return _M_insert_rval(__position, std::move(__v)); }
 #endif
 
-      // Called by the latter.
+      // Called by _M_fill_insert, _M_insert_aux etc.
       size_type
       _M_check_len(size_type __n, const char* __s) const
       {
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 9cb5464..dd0d288 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -124,8 +124,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  const auto __pos = begin() + (__position - cbegin());
 	  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 	    {
-	      _Tp __x_copy = __x;
-	      _M_insert_aux(__pos, std::move(__x_copy));
+	      // __x could be an existing element of this vector, so make a
+	      // copy of it before _M_insert_aux moves elements around.
+	      _Temporary_value __x_copy(this, __x);
+	      _M_insert_aux(__pos, std::move(__x_copy._M_val()));
 	    }
 	  else
 	    _M_insert_aux(__pos, __x);
@@ -297,30 +299,49 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
 #if __cplusplus >= 201103L
   template<typename _Tp, typename _Alloc>
+    auto
+    vector<_Tp, _Alloc>::
+    _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
+    {
+      const auto __n = __position - cbegin();
+      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
+	  && __position == cend())
+	{
+	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				   std::move(__v));
+	  ++this->_M_impl._M_finish;
+	}
+      else
+	_M_insert_aux(begin() + __n, std::move(__v));
+      return iterator(this->_M_impl._M_start + __n);
+    }
+
+  template<typename _Tp, typename _Alloc>
     template<typename... _Args>
-      typename vector<_Tp, _Alloc>::iterator
+      auto
       vector<_Tp, _Alloc>::
-      emplace(const_iterator __position, _Args&&... __args)
+      _M_emplace_aux(const_iterator __position, _Args&&... __args)
+      -> iterator
       {
-	const size_type __n = __position - begin();
-	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	    && __position == end())
-	  {
-	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-				     std::forward<_Args>(__args)...);
-	    ++this->_M_impl._M_finish;
-	  }
+	const auto __n = __position - cbegin();
+	if (__position == cend())
+	  emplace_back(std::forward<_Args>(__args)...);
 	else
-	  _M_insert_aux(begin() + (__position - cbegin()),
-			std::forward<_Args>(__args)...);
+	  {
+	    // We need to construct a temporary because something in __args...
+	    // could alias one of the elements of the container and so we
+	    // need to use it before _M_insert_aux moves elements around.
+	    _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
+	    _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
+	  }
 	return iterator(this->_M_impl._M_start + __n);
       }
 
   template<typename _Tp, typename _Alloc>
-    template<typename... _Args>
+    template<typename _Arg>
       void
       vector<_Tp, _Alloc>::
-      _M_insert_aux(iterator __position, _Args&&... __args)
+      _M_insert_aux(iterator __position, _Arg&& __arg)
 #else
   template<typename _Tp, typename _Alloc>
     void
@@ -343,7 +364,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus < 201103L
 	  *__position = __x_copy;
 #else
-	  _S_insert_aux_assign(__position, std::forward<_Args>(__args)...);
+	  *__position = std::forward<_Arg>(__arg);
 #endif
 	}
       else
@@ -355,14 +376,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  pointer __new_finish(__new_start);
 	  __try
 	    {
-	      // The order of the three operations is dictated by the C++0x
+	      // The order of the three operations is dictated by the C++11
 	      // case, where the moves could alter a new element belonging
 	      // to the existing vector.  This is an issue only for callers
-	      // taking the element by const lvalue ref (see 23.1/13).
+	      // taking the element by lvalue ref (see last bullet of C++11
+	      // [res.on.arguments]).
 	      _Alloc_traits::construct(this->_M_impl,
 		                       __new_start + __elems_before,
 #if __cplusplus >= 201103L
-				       std::forward<_Args>(__args)...);
+				       std::forward<_Arg>(__arg));
 #else
 	                               __x);
 #endif
@@ -455,7 +477,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  if (size_type(this->_M_impl._M_end_of_storage
 			- this->_M_impl._M_finish) >= __n)
 	    {
+#if __cplusplus < 201103L
 	      value_type __x_copy = __x;
+#else
+	      _Temporary_value __tmp(this, __x);
+	      value_type& __x_copy = __tmp._M_val();
+#endif
 	      const size_type __elems_after = end() - __position;
 	      pointer __old_finish(this->_M_impl._M_finish);
 	      if (__elems_after > __n)
diff --git a/libstdc++-v3/testsuite/23_containers/vector/allocator/construction.cc b/libstdc++-v3/testsuite/23_containers/vector/allocator/construction.cc
new file mode 100644
index 0000000..8040949
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/allocator/construction.cc
@@ -0,0 +1,105 @@
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+// { dg-do compile }
+
+#include <vector>
+
+struct Tag { };
+
+template<typename T>
+  struct TaggingAllocator
+  {
+    using value_type = T;
+
+    TaggingAllocator() = default;
+
+    template<typename U>
+      TaggingAllocator(const TaggingAllocator<U>&) { }
+
+    T*
+    allocate(std::size_t n) { return std::allocator<T>{}.allocate(n); }
+
+    void
+    deallocate(T* p, std::size_t n) { std::allocator<T>{}.deallocate(p, n); }
+
+    template<typename U, typename... Args>
+      void
+      construct(U* p, Args&&... args)
+      { ::new((void*)p) U(Tag{}, std::forward<Args>(args)...); }
+
+    template<typename U, typename... Args>
+      void
+      destroy(U* p)
+      { p->~U(); }
+  };
+
+template<typename T, typename U>
+  bool
+  operator==(const TaggingAllocator<T>&, const TaggingAllocator<U>&)
+  { return true; }
+
+template<typename T, typename U>
+  bool
+  operator!=(const TaggingAllocator<T>&, const TaggingAllocator<U>&)
+  { return false; }
+
+struct X
+{
+  // All constructors must be passed the Tag type.
+
+  // DefaultInsertable into vector<X, TaggingAllocator<X>>,
+  X(Tag) { }
+  // CopyInsertable into vector<X, TaggingAllocator<X>>,
+  X(Tag, const X&) { }
+  // MoveInsertable into vector<X, TaggingAllocator<X>>, and
+  X(Tag, X&&) { }
+
+  // EmplaceConstructible into vector<X, TaggingAllocator<X>> from args.
+  template<typename... Args>
+    X(Tag, Args&&...) { }
+
+  // not DefaultConstructible, CopyConstructible or MoveConstructible.
+  X() = delete;
+  X(const X&) = delete;
+  X(X&&) = delete;
+
+  // CopyAssignable.
+  X& operator=(const X&) { return *this; }
+
+  // MoveAssignable.
+  X& operator=(X&&) { return *this; }
+
+private:
+  // Not Destructible.
+  ~X() { }
+
+  // Erasable from vector<X, TaggingAllocator<X>>.
+  friend class TaggingAllocator<X>;
+};
+
+template class std::vector<X, TaggingAllocator<X>>;
+
+void test01()
+{
+  std::vector<X, TaggingAllocator<X>> v;
+  v.reserve(3);
+  v.emplace_back();
+  v.emplace(v.begin());
+  v.emplace(v.begin(), 1, 2, 3);
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/check_construct_destroy.cc b/libstdc++-v3/testsuite/23_containers/vector/check_construct_destroy.cc
index cf2f7c7..b92a152 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/check_construct_destroy.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/check_construct_destroy.cc
@@ -49,9 +49,9 @@ int main()
     c.reserve(100);
     tracker_allocator_counter::reset();
     c.insert(c.begin(), arr10[0]);
-    ok = check_construct_destroy("Insert element", 1, 0) && ok;
+    ok = check_construct_destroy("Insert element", 2, 1) && ok;
   }
-  ok = check_construct_destroy("Insert element", 1, 11) && ok;
+  ok = check_construct_destroy("Insert element", 2, 12) && ok;
 
   {
     Container c(arr10, arr10 + 10);
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
index 39a3f03..1b46124 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
@@ -223,7 +223,8 @@ test03()
 void
 test04()
 {
-  const X::special expected{ 0, 3, 1, 0, 3, 0 };
+  const X::special expected_ins{ 0, 3, 1, 0, 3, 0 };
+  const X::special expected_emp{ 0, 4, 1, 0, 4, 0 };
   X::special ins, emp;
   {
     std::vector<X> v;
@@ -253,8 +254,8 @@ test04()
     // std::cout << "----\n";
     emp = X::sp;
   }
-  VERIFY( ins == emp );
-  VERIFY( ins == expected );
+  VERIFY( ins == expected_ins );
+  VERIFY( emp == expected_emp );
 }
 
 // insert vs emplace xvalue reallocation
diff --git a/libstdc++-v3/testsuite/backward/hash_set/check_construct_destroy.cc b/libstdc++-v3/testsuite/backward/hash_set/check_construct_destroy.cc
index 5693c76..5740fe1 100644
--- a/libstdc++-v3/testsuite/backward/hash_set/check_construct_destroy.cc
+++ b/libstdc++-v3/testsuite/backward/hash_set/check_construct_destroy.cc
@@ -39,45 +39,48 @@ int main()
 
   int buckets;
 
+  // Add 1 to all counts, because the std::vector used internally by the
+  // hashtable creates and destroys a temporary object using the allocator.
+
   tracker_allocator_counter::reset();
   {
     Container c;
     buckets = c.bucket_count();
-    ok = check_construct_destroy("empty container", buckets, 0) && ok;
+    ok = check_construct_destroy("empty container", buckets+1, 1) && ok;
   }
-  ok = check_construct_destroy("empty container", buckets, buckets) && ok;
+  ok = check_construct_destroy("empty container", buckets+1, buckets+1) && ok;
 
 
   tracker_allocator_counter::reset();
   {
     Container c(arr10, arr10 + 10);
-    ok = check_construct_destroy("Construct from range", buckets+10, 0) && ok;
+    ok = check_construct_destroy("Construct from range", buckets+10+1, 1) && ok;
   }
-  ok = check_construct_destroy("Construct from range", buckets+10, buckets+10) && ok;
+  ok = check_construct_destroy("Construct from range", buckets+10+1, buckets+10+1) && ok;
 
   tracker_allocator_counter::reset();
   {
     Container c(arr10, arr10 + 10);
     c.insert(arr10a[0]);
-    ok = check_construct_destroy("Insert element", buckets+11, 0) && ok;
+    ok = check_construct_destroy("Insert element", buckets+11+1, 1) && ok;
   }
-  ok = check_construct_destroy("Insert element", buckets+11, buckets+11) && ok;
+  ok = check_construct_destroy("Insert element", buckets+11+1, buckets+11+1) && ok;
 
   tracker_allocator_counter::reset();
   {
     Container c(arr10, arr10 + 10);
     c.insert(arr10a, arr10a+3);
-    ok = check_construct_destroy("Insert short range", buckets+13, 0) && ok;
+    ok = check_construct_destroy("Insert short range", buckets+13+1, 1) && ok;
   }
-  ok = check_construct_destroy("Insert short range", buckets+13, buckets+13) && ok;
+  ok = check_construct_destroy("Insert short range", buckets+13+1, buckets+13+1) && ok;
 
   tracker_allocator_counter::reset();
   {
     Container c(arr10, arr10 + 10);
     c.insert(arr10a, arr10a+10);
-    ok = check_construct_destroy("Insert long range", buckets+20, 0) && ok;
+    ok = check_construct_destroy("Insert long range", buckets+20+1, 1) && ok;
   }
-  ok = check_construct_destroy("Insert long range", buckets+20, buckets+20) && ok;
+  ok = check_construct_destroy("Insert long range", buckets+20+1, buckets+20+1) && ok;
 
   return ok ? 0 : 1;
 }

Re: Improve insert/emplace robustness to self insertion

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 3190 bytes --]

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 ?

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. With this 
reorganization we don't check it several times. Moreover, as soon as we 
reallocate we know that we don't need to do any temporary copy so 
insert_vs_emplace.cc test04 has been adapted and we now have no 
situation where emplace and insert are not equivalent.

     * include/bits/stl_vector.h (push_back(const value_type&)): Forward
     to _M_realloc_insert.
     (insert(const_iterator, value_type&&)): Forward to _M_insert_rval.
     (_M_realloc_insert): Declare new function.
     (_M_emplace_back_aux): Remove definition.
     * include/bits/vector.tcc (emplace_back(_Args...)):
     Use _M_realloc_insert.
     (insert(const_iterator, const value_type&)): Likewise.
     (_M_insert_rval, _M_emplace_aux): Likewise.
     (_M_emplace_back_aux): Remove declaration.
     (_M_realloc_insert): Define.
     * testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc:
     Adjust expected results for emplacing an lvalue with reallocation.

Tested under Linux x86_64.

Ok to commit ?

François

[-- Attachment #2: vector_w.patch --]
[-- Type: text/x-patch, Size: 8799 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index 8e8aa7c..85abf4a 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -946,11 +946,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	    ++this->_M_impl._M_finish;
 	  }
 	else
-#if __cplusplus >= 201103L
-	  _M_emplace_back_aux(__x);
-#else
-	  _M_insert_aux(end(), __x);
-#endif
+	  _M_realloc_insert(end(), __x);
       }
 
 #if __cplusplus >= 201103L
@@ -1436,6 +1432,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       // Called by insert(p,x)
       void
       _M_insert_aux(iterator __position, const value_type& __x);
+
+      void
+      _M_realloc_insert(iterator __position, const value_type& __x);
 #else
       // A value_type object constructed with _Alloc_traits::construct()
       // and destroyed with _Alloc_traits::destroy().
@@ -1469,16 +1468,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	void
 	_M_insert_aux(iterator __position, _Arg&& __arg);
 
+      template<typename... _Args>
+	void
+	_M_realloc_insert(iterator __position, _Args&&... __args);
+
       // Either move-construct at the end, or forward to _M_insert_aux.
       iterator
       _M_insert_rval(const_iterator __position, value_type&& __v);
 
-      // Called by push_back(x) and emplace_back(args) when they need to
-      // reallocate.
-      template<typename... _Args>
-	void
-	_M_emplace_back_aux(_Args&&... __args);
-
       // Try to emplace at the end, otherwise forward to _M_insert_aux.
       template<typename... _Args>
 	iterator
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 6e9be7f..b291e95 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -98,7 +98,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	    ++this->_M_impl._M_finish;
 	  }
 	else
-	  _M_emplace_back_aux(std::forward<_Args>(__args)...);
+	  _M_realloc_insert(end(), std::forward<_Args>(__args)...);
       }
 #endif
 
@@ -112,29 +112,32 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
     {
       const size_type __n = __position - begin();
-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	  && __position == end())
+      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	if (__position == end())
 	  {
-	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
+	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				     __x);
 	    ++this->_M_impl._M_finish;
 	  }
 	else
 	  {
 #if __cplusplus >= 201103L
 	    const auto __pos = begin() + (__position - cbegin());
-	  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
-	    {
 	    // __x could be an existing element of this vector, so make a
 	    // copy of it before _M_insert_aux moves elements around.
 	    _Temporary_value __x_copy(this, __x);
 	    _M_insert_aux(__pos, std::move(__x_copy._M_val()));
-	    }
-	  else
-	    _M_insert_aux(__pos, __x);
 #else
 	    _M_insert_aux(__position, __x);
 #endif
 	  }
+      else
+#if __cplusplus >= 201103L
+	_M_realloc_insert(begin() + (__position - cbegin()), __x);
+#else
+	_M_realloc_insert(__position, __x);
+#endif
+
       return iterator(this->_M_impl._M_start + __n);
     }
 
@@ -304,8 +307,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
     {
       const auto __n = __position - cbegin();
-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	  && __position == cend())
+      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	if (__position == cend())
 	  {
 	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
 				     std::move(__v));
@@ -313,6 +316,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  }
 	else
 	  _M_insert_aux(begin() + __n, std::move(__v));
+      else
+	_M_realloc_insert(begin() + __n, std::move(__v));
+
       return iterator(this->_M_impl._M_start + __n);
     }
 
@@ -324,8 +330,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       -> iterator
       {
 	const auto __n = __position - cbegin();
+	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 	  if (__position == cend())
-	  emplace_back(std::forward<_Args>(__args)...);
+	    {
+	      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				       std::forward<_Args>(__args)...);
+	      ++this->_M_impl._M_finish;
+	    }
 	  else
 	    {
 	      // We need to construct a temporary because something in __args...
@@ -334,6 +345,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	      _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
 	      _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
 	    }
+	else
+	  _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...);
+
 	return iterator(this->_M_impl._M_start + __n);
       }
 
@@ -349,8 +363,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     _M_insert_aux(iterator __position, const _Tp& __x)
 #endif
     {
-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
-	{
       _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
 			       _GLIBCXX_MOVE(*(this->_M_impl._M_finish
 					       - 1)));
@@ -367,10 +379,22 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       *__position = std::forward<_Arg>(__arg);
 #endif
     }
-      else
+
+#if __cplusplus >= 201103L
+  template<typename _Tp, typename _Alloc>
+    template<typename... _Args>
+      void
+      vector<_Tp, _Alloc>::
+      _M_realloc_insert(iterator __position, _Args&&... __args)
+#else
+  template<typename _Tp, typename _Alloc>
+    void
+    vector<_Tp, _Alloc>::
+    _M_realloc_insert(iterator __position, const _Tp& __x)
+#endif
     {
       const size_type __len =
-	    _M_check_len(size_type(1), "vector::_M_insert_aux");
+	_M_check_len(size_type(1), "vector::_M_realloc_insert");
       const size_type __elems_before = __position - begin();
       pointer __new_start(this->_M_allocate(__len));
       pointer __new_finish(__new_start);
@@ -384,7 +408,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  _Alloc_traits::construct(this->_M_impl,
 				   __new_start + __elems_before,
 #if __cplusplus >= 201103L
-				       std::forward<_Arg>(__arg));
+				   std::forward<_Args>(__args)...);
 #else
 				   __x);
 #endif
@@ -421,51 +445,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       this->_M_impl._M_finish = __new_finish;
       this->_M_impl._M_end_of_storage = __new_start + __len;
     }
-    }
-
-#if __cplusplus >= 201103L
-  template<typename _Tp, typename _Alloc>
-    template<typename... _Args>
-      void
-      vector<_Tp, _Alloc>::
-      _M_emplace_back_aux(_Args&&... __args)
-      {
-	const size_type __len =
-	  _M_check_len(size_type(1), "vector::_M_emplace_back_aux");
-	pointer __new_start(this->_M_allocate(__len));
-	pointer __new_finish(__new_start);
-	__try
-	  {
-	    _Alloc_traits::construct(this->_M_impl, __new_start + size(),
-				     std::forward<_Args>(__args)...);
-	    __new_finish = pointer();
-
-	    __new_finish
-	      = std::__uninitialized_move_if_noexcept_a
-	      (this->_M_impl._M_start, this->_M_impl._M_finish,
-	       __new_start, _M_get_Tp_allocator());
-
-	    ++__new_finish;
-	  }
-	__catch(...)
-	  {
-	    if (!__new_finish)
-	      _Alloc_traits::destroy(this->_M_impl, __new_start + size());
-	    else
-	      std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
-	    _M_deallocate(__new_start, __len);
-	    __throw_exception_again;
-	  }
-	std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
-		      _M_get_Tp_allocator());
-	_M_deallocate(this->_M_impl._M_start,
-		      this->_M_impl._M_end_of_storage
-		      - this->_M_impl._M_start);
-	this->_M_impl._M_start = __new_start;
-	this->_M_impl._M_finish = __new_finish;
-	this->_M_impl._M_end_of_storage = __new_start + __len;
-      }
-#endif
 
   template<typename _Tp, typename _Alloc>
     void
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
index 1b46124..39a3f03 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
@@ -223,8 +223,7 @@ test03()
 void
 test04()
 {
-  const X::special expected_ins{ 0, 3, 1, 0, 3, 0 };
-  const X::special expected_emp{ 0, 4, 1, 0, 4, 0 };
+  const X::special expected{ 0, 3, 1, 0, 3, 0 };
   X::special ins, emp;
   {
     std::vector<X> v;
@@ -254,8 +253,8 @@ test04()
     // std::cout << "----\n";
     emp = X::sp;
   }
-  VERIFY( ins == expected_ins );
-  VERIFY( emp == expected_emp );
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
 }
 
 // insert vs emplace xvalue reallocation

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

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.

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 1613 bytes --]

On 06/07/16 21:46 +0200, François Dumont wrote:
>Don't you plan to add it to the testsuite ?

Done with the attached aptch.

>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. 
>With this reorganization we don't check it several times. Moreover, as 
>soon as we reallocate we know that we don't need to do any temporary 
>copy so insert_vs_emplace.cc test04 has been adapted and we now have 
>no situation where emplace and insert are not equivalent.
>
>    * include/bits/stl_vector.h (push_back(const value_type&)): Forward
>    to _M_realloc_insert.
>    (insert(const_iterator, value_type&&)): Forward to _M_insert_rval.
>    (_M_realloc_insert): Declare new function.
>    (_M_emplace_back_aux): Remove definition.
>    * include/bits/vector.tcc (emplace_back(_Args...)):
>    Use _M_realloc_insert.
>    (insert(const_iterator, const value_type&)): Likewise.
>    (_M_insert_rval, _M_emplace_aux): Likewise.
>    (_M_emplace_back_aux): Remove declaration.
>    (_M_realloc_insert): Define.
>    * testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc:
>    Adjust expected results for emplacing an lvalue with reallocation.
>
>Tested under Linux x86_64.
>
>Ok to commit ?

This is excellent work, thanks for doing it.

OK for trunk.



[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 2456 bytes --]

commit dd91c89f43bb79bc4e206824341536a234542c64
Author: redi <redi@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Fri Jul 8 16:35:10 2016 +0000

    	* testsuite/23_containers/vector/modifiers/insert/aliasing.cc: New.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@238169 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/aliasing.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/aliasing.cc
new file mode 100644
index 0000000..2ef13b4
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/aliasing.cc
@@ -0,0 +1,79 @@
+// Copyright (C) 2016 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++14" }
+
+#include <vector>
+#include <memory>
+#include <testsuite_hooks.h>
+
+// See https://gcc.gnu.org/ml/libstdc++/2016-07/msg00008.html for background.
+
+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;
+}
+
+void
+test01()
+{
+ 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();
+
+ VERIFY(v[1].child->value == 12);
+ VERIFY(v[1].child->child == nullptr);
+
+ v.insert(v.begin(), *v[1].child);
+
+ VERIFY(v[0].value == 12);
+ VERIFY(v[0].child == nullptr);
+}
+
+int main()
+{
+  test01();
+}

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 300 bytes --]

On 08/07/16 17:38 +0100, Jonathan Wakely wrote:
>On 06/07/16 21:46 +0200, François Dumont wrote:
>>Don't you plan to add it to the testsuite ?
>
>Done with the attached aptch.

Just for completeness, I'm also adding the example from LWG 2164,
which is related.

Tested x86_64, committed to trunk.



[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 1105 bytes --]

commit 23cb1117d3b5073097ab15fcf9c0245aa98de067
Author: redi <redi@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Tue Jul 12 14:00:11 2016 +0000

    Add std::vector::emplace() testcase from LWG 2164
    
    	* testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc:
    	Add testcase from LWG 2164.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@238243 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
index d452b5b..8712216 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
@@ -135,6 +135,20 @@ test04()
   VERIFY( va[0]._i == 1 );
 }
 
+void
+test05()
+{
+  // LWG DR 2164
+  std::vector<int> v;
+  v.reserve(4);
+  v = { 1, 2, 3 };
+  v.emplace(v.begin(), v.back());
+  VERIFY( v[0] == 3 );
+  VERIFY( v[1] == 1 );
+  VERIFY( v[2] == 2 );
+  VERIFY( v[3] == 3 );
+}
+
 int main()
 {
   test01();

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 09/07/16 20:29 -0400, David Edelsohn wrote:
>On Sat, Jul 9, 2016 at 7:59 PM, Jonathan Wakely <jwakely@redhat.com> wrote:
>> On 09/07/16 13:47 -0400, David Edelsohn wrote:
>>>
>>> This patch has caused some new libstdc++ testsuite failures on AIX.
>>
>>
>> Which patch?
>>
>> My last patch only added a new test, that can't have caused failures
>> in unrelated tests.
>>
>> https://gcc.gnu.org/ml/libstdc++-cvs/2016-q3/msg00021.html
>
>I thought that there were a recent set of libstdc++ patches related to
>"insert'.

There was one July 4, but nothing since then has been committed, only
discussed. That touched vector::insert, so is highly unlikely to have
changed codegen for __gnu_debug::deque or __gnu_debug::list.

>What else could have caused these regressions?  Recent
>patches to C++ front-end?

Possibly, I've no idea, I haven't been watching the FE commits.

>Thanks, David
>
>>
>>
>>
>>
>>> FAIL: 23_containers/list/debug/insert4_neg.cc (test for excess errors)
>>>
>>> Excess errors:
>>>
>>>
>>> /tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
>>> error: __gnu_debug::_Error_formatter&
>>> __gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>>> char*) [with _Iterator = __gnu_debug::_Safe_iterator
>>> <std::_List_const_iterator<int>, std::__debug::list<int> >] causes a
>>> section type conflict with __gnu_debug::_Error_formatter&
>>> __gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>>> char*) [with _Iterator =
>>> __gnu_debug::_Safe_iterator<std::_List_iterator<int>,
>>> std::__debug::list<int> >]
>>>
>>> FAIL: 23_containers/deque/debug/insert4_neg.cc (test for excess errors)
>>>
>>> Excess errors:
>>>
>>>
>>> /tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
>>> error: __gnu_debug::_Error_formatter&
>>> __gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>>> char*) [with _Iterator = __gnu_debug::_Safe_iterator
>>> <std::_Deque_iterator<int, int&, int*>, std::__debug::deque<int> >]
>>> causes a section type conflict with __gnu_debug::_Error_formatter&
>>> __gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>>> char*) [with _Iterator =
>>> __gnu_debug::_Safe_iterator<std::_Deque_iterator<int, const int&,
>>> const int*>, std::__debug::deque<int> >]
>>>
>>> Thanks, David

Re: Improve insert/emplace robustness to self insertion

[David Edelsohn]

On Sat, Jul 9, 2016 at 7:59 PM, Jonathan Wakely <jwakely@redhat.com> wrote:
> On 09/07/16 13:47 -0400, David Edelsohn wrote:
>>
>> This patch has caused some new libstdc++ testsuite failures on AIX.
>
>
> Which patch?
>
> My last patch only added a new test, that can't have caused failures
> in unrelated tests.
>
> https://gcc.gnu.org/ml/libstdc++-cvs/2016-q3/msg00021.html

I thought that there were a recent set of libstdc++ patches related to
"insert'.  What else could have caused these regressions?  Recent
patches to C++ front-end?

Thanks, David

>
>
>
>
>> FAIL: 23_containers/list/debug/insert4_neg.cc (test for excess errors)
>>
>> Excess errors:
>>
>>
>> /tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
>> error: __gnu_debug::_Error_formatter&
>> __gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>> char*) [with _Iterator = __gnu_debug::_Safe_iterator
>> <std::_List_const_iterator<int>, std::__debug::list<int> >] causes a
>> section type conflict with __gnu_debug::_Error_formatter&
>> __gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>> char*) [with _Iterator =
>> __gnu_debug::_Safe_iterator<std::_List_iterator<int>,
>> std::__debug::list<int> >]
>>
>> FAIL: 23_containers/deque/debug/insert4_neg.cc (test for excess errors)
>>
>> Excess errors:
>>
>>
>> /tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
>> error: __gnu_debug::_Error_formatter&
>> __gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>> char*) [with _Iterator = __gnu_debug::_Safe_iterator
>> <std::_Deque_iterator<int, int&, int*>, std::__debug::deque<int> >]
>> causes a section type conflict with __gnu_debug::_Error_formatter&
>> __gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>> char*) [with _Iterator =
>> __gnu_debug::_Safe_iterator<std::_Deque_iterator<int, const int&,
>> const int*>, std::__debug::deque<int> >]
>>
>> Thanks, David

Re: Improve insert/emplace robustness to self insertion

[Jonathan Wakely]

On 09/07/16 13:47 -0400, David Edelsohn wrote:
>This patch has caused some new libstdc++ testsuite failures on AIX.

Which patch?

My last patch only added a new test, that can't have caused failures
in unrelated tests.

https://gcc.gnu.org/ml/libstdc++-cvs/2016-q3/msg00021.html



>FAIL: 23_containers/list/debug/insert4_neg.cc (test for excess errors)
>
>Excess errors:
>
>/tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
>error: __gnu_debug::_Error_formatter&
>__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>char*) [with _Iterator = __gnu_debug::_Safe_iterator
><std::_List_const_iterator<int>, std::__debug::list<int> >] causes a
>section type conflict with __gnu_debug::_Error_formatter&
>__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>char*) [with _Iterator =
>__gnu_debug::_Safe_iterator<std::_List_iterator<int>,
>std::__debug::list<int> >]
>
>FAIL: 23_containers/deque/debug/insert4_neg.cc (test for excess errors)
>
>Excess errors:
>
>/tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
>error: __gnu_debug::_Error_formatter&
>__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>char*) [with _Iterator = __gnu_debug::_Safe_iterator
><std::_Deque_iterator<int, int&, int*>, std::__debug::deque<int> >]
>causes a section type conflict with __gnu_debug::_Error_formatter&
>__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
>char*) [with _Iterator =
>__gnu_debug::_Safe_iterator<std::_Deque_iterator<int, const int&,
>const int*>, std::__debug::deque<int> >]
>
>Thanks, David

Re: Improve insert/emplace robustness to self insertion

[David Edelsohn]

This patch has caused some new libstdc++ testsuite failures on AIX.

FAIL: 23_containers/list/debug/insert4_neg.cc (test for excess errors)

Excess errors:

/tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
error: __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator = __gnu_debug::_Safe_iterator
<std::_List_const_iterator<int>, std::__debug::list<int> >] causes a
section type conflict with __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator =
__gnu_debug::_Safe_iterator<std::_List_iterator<int>,
std::__debug::list<int> >]

FAIL: 23_containers/deque/debug/insert4_neg.cc (test for excess errors)

Excess errors:

/tmp/20160708/powerpc-ibm-aix7.1.0.0/libstdc++-v3/include/debug/formatter.h:387:7:
error: __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator = __gnu_debug::_Safe_iterator
<std::_Deque_iterator<int, int&, int*>, std::__debug::deque<int> >]
causes a section type conflict with __gnu_debug::_Error_formatter&
__gnu_debug::_Error_formatter::_M_iterator(const _Iterator&, const
char*) [with _Iterator =
__gnu_debug::_Safe_iterator<std::_Deque_iterator<int, const int&,
const int*>, std::__debug::deque<int> >]

Thanks, David