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
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;