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