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