First half of LWG#2354: 'Unnecessary copying when inserting into maps with braced-init syntax'

llvm-svn: 256859

7 files changed, 235 insertions, 4 deletions

diff --git a/libcxx/include/__tree b/libcxx/include/__tree
index cb58a907814..94565bc3f74 100644
--- a/libcxx/include/__tree
+++ b/libcxx/include/__tree
@@ -909,6 +909,13 @@ public:
     iterator __insert_multi(const value_type& __v);
     iterator __insert_multi(const_iterator __p, const value_type& __v);
 
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+    pair<iterator, bool> __insert_unique(        value_type&& __v);
+    iterator __insert_unique(const_iterator __p, value_type&& __v);
+    iterator __insert_multi(                    value_type&& __v);
+    iterator __insert_multi(const_iterator __p, value_type&& __v);
+#endif
+
     pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
     iterator             __node_insert_unique(const_iterator __p,
                                               __node_pointer __nd);
@@ -1730,6 +1737,28 @@ __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p,
 #endif  // _LIBCPP_HAS_NO_VARIADICS
 
 template <class _Tp, class _Compare, class _Allocator>
+pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
+__tree<_Tp, _Compare, _Allocator>::__insert_unique(value_type&& __v)
+{
+    __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v));
+    pair<iterator, bool> __r = __node_insert_unique(__h.get());
+    if (__r.second)
+        __h.release();
+    return __r;
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, value_type&& __v)
+{
+    __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v));
+    iterator __r = __node_insert_unique(__p, __h.get());
+    if (__r.__ptr_ == __h.get())
+        __h.release();
+    return __r;
+}
+
+template <class _Tp, class _Compare, class _Allocator>
 template <class _Vp>
 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
 __tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v)
@@ -1754,6 +1783,28 @@ __tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, _Vp&& __v
 }
 
 template <class _Tp, class _Compare, class _Allocator>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__insert_multi(value_type&& __v)
+{
+    __node_base_pointer __parent;
+    __node_base_pointer& __child = __find_leaf_high(__parent, __v);
+    __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v));
+    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+    return iterator(__h.release());
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, value_type&& __v)
+{
+    __node_base_pointer __parent;
+    __node_base_pointer& __child = __find_leaf(__p, __parent, __v);
+    __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v));
+    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+    return iterator(__h.release());
+}
+
+template <class _Tp, class _Compare, class _Allocator>
 template <class _Vp>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::__insert_multi(_Vp&& __v)
diff --git a/libcxx/include/map b/libcxx/include/map
index 2416205d6f0..87add437a54 100644
--- a/libcxx/include/map
+++ b/libcxx/include/map
@@ -126,9 +126,11 @@ public:
     template <class... Args>
         iterator emplace_hint(const_iterator position, Args&&... args);
     pair<iterator, bool> insert(const value_type& v);
+    pair<iterator, bool> insert(      value_type&& v);                                // C++17
     template <class P>
         pair<iterator, bool> insert(P&& p);
     iterator insert(const_iterator position, const value_type& v);
+    iterator insert(const_iterator position,       value_type&& v);                   // C++17
     template <class P>
         iterator insert(const_iterator position, P&& p);
     template <class InputIterator>
@@ -336,9 +338,11 @@ public:
     template <class... Args>
         iterator emplace_hint(const_iterator position, Args&&... args);
     iterator insert(const value_type& v);
+    iterator insert(      value_type&& v);                                            // C++17
     template <class P>
         iterator insert(P&& p);
     iterator insert(const_iterator position, const value_type& v);
+    iterator insert(const_iterator position,       value_type&& v);                   // C++17
     template <class P>
         iterator insert(const_iterator position, P&& p);
     template <class InputIterator>
@@ -1089,6 +1093,17 @@ public:
         insert(const_iterator __p, const value_type& __v)
             {return __tree_.__insert_unique(__p.__i_, __v);}
 
+#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool>
+        insert(     value_type&& __v) {return __tree_.__insert_unique(_VSTD::forward<value_type>(__v));}
+
+    _LIBCPP_INLINE_VISIBILITY
+    iterator
+        insert(const_iterator __p,       value_type&& __v)
+            {return __tree_.__insert_unique(__p.__i_, _VSTD::forward<value_type>(__v));}
+#endif
+
     template <class _InputIterator>
         _LIBCPP_INLINE_VISIBILITY
         void insert(_InputIterator __f, _InputIterator __l)
@@ -1940,6 +1955,15 @@ public:
     iterator insert(const_iterator __p, const value_type& __v)
             {return __tree_.__insert_multi(__p.__i_, __v);}
 
+#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert( value_type&& __v) {return __tree_.__insert_multi(_VSTD::forward<value_type>(__v));}
+
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __p, value_type&& __v)
+            {return __tree_.__insert_multi(__p.__i_, _VSTD::forward<value_type>(__v));}
+#endif
+
     template <class _InputIterator>
         _LIBCPP_INLINE_VISIBILITY
         void insert(_InputIterator __f, _InputIterator __l)
diff --git a/libcxx/test/std/containers/associative/map/map.modifiers/insert_iter_rv.pass.cpp b/libcxx/test/std/containers/associative/map/map.modifiers/insert_iter_rv.pass.cpp
index 42b41fd7b86..fabafd332f4 100644
--- a/libcxx/test/std/containers/associative/map/map.modifiers/insert_iter_rv.pass.cpp
+++ b/libcxx/test/std/containers/associative/map/map.modifiers/insert_iter_rv.pass.cpp
@@ -52,7 +52,7 @@ int main()
         assert(r->first == 3);
         assert(r->second == 3);
     }
-#if __cplusplus >= 201103L
+#if TEST_STD_VER >= 11
     {
         typedef std::map<int, MoveOnly, std::less<int>, min_allocator<std::pair<const int, MoveOnly>>> M;
         typedef std::pair<int, MoveOnly> P;
@@ -83,5 +83,35 @@ int main()
         assert(r->second == 3);
     }
 #endif
+#if TEST_STD_VER > 14
+    {
+        typedef std::map<int, MoveOnly> M;
+        typedef M::iterator R;
+        M m;
+        R r = m.insert(m.end(), {2, MoveOnly(2)});
+        assert(r == m.begin());
+        assert(m.size() == 1);
+        assert(r->first == 2);
+        assert(r->second == 2);
+
+        r = m.insert(m.end(), {1, MoveOnly(1)});
+        assert(r == m.begin());
+        assert(m.size() == 2);
+        assert(r->first == 1);
+        assert(r->second == 1);
+
+        r = m.insert(m.end(), {3, MoveOnly(3)});
+        assert(r == prev(m.end()));
+        assert(m.size() == 3);
+        assert(r->first == 3);
+        assert(r->second == 3);
+
+        r = m.insert(m.end(), {3, MoveOnly(3)});
+        assert(r == prev(m.end()));
+        assert(m.size() == 3);
+        assert(r->first == 3);
+        assert(r->second == 3);
+    }
 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif
 }
diff --git a/libcxx/test/std/containers/associative/map/map.modifiers/insert_rv.pass.cpp b/libcxx/test/std/containers/associative/map/map.modifiers/insert_rv.pass.cpp
index a9d3277e6d9..813e425e568 100644
--- a/libcxx/test/std/containers/associative/map/map.modifiers/insert_rv.pass.cpp
+++ b/libcxx/test/std/containers/associative/map/map.modifiers/insert_rv.pass.cpp
@@ -11,6 +11,7 @@
 
 // class map
 
+// pair<iterator, bool> insert( value_type&& v);  // C++17 and later
 // template <class P>
 //   pair<iterator, bool> insert(P&& p);
 
@@ -55,7 +56,7 @@ int main()
         assert(r.first->first == 3);
         assert(r.first->second == 3);
     }
-#if __cplusplus >= 201103L
+#if TEST_STD_VER >= 11
     {
         typedef std::map<int, MoveOnly, std::less<int>, min_allocator<std::pair<const int, MoveOnly>>> M;
         typedef std::pair<M::iterator, bool> R;
@@ -89,5 +90,39 @@ int main()
         assert(r.first->second == 3);
     }
 #endif
+#if TEST_STD_VER > 14
+    {
+        typedef std::map<int, MoveOnly> M;
+        typedef std::pair<M::iterator, bool> R;
+        M m;
+        R r = m.insert({2, MoveOnly(2)});
+        assert(r.second);
+        assert(r.first == m.begin());
+        assert(m.size() == 1);
+        assert(r.first->first == 2);
+        assert(r.first->second == 2);
+
+        r = m.insert({1, MoveOnly(1)});
+        assert(r.second);
+        assert(r.first == m.begin());
+        assert(m.size() == 2);
+        assert(r.first->first == 1);
+        assert(r.first->second == 1);
+
+        r = m.insert({3, MoveOnly(3)});
+        assert(r.second);
+        assert(r.first == prev(m.end()));
+        assert(m.size() == 3);
+        assert(r.first->first == 3);
+        assert(r.first->second == 3);
+
+        r = m.insert({3, MoveOnly(3)});
+        assert(!r.second);
+        assert(r.first == prev(m.end()));
+        assert(m.size() == 3);
+        assert(r.first->first == 3);
+        assert(r.first->second == 3);
+    }
+#endif
 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 }
diff --git a/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_iter_rv.pass.cpp b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_iter_rv.pass.cpp
index b44f46429ec..de5aea614cb 100644
--- a/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_iter_rv.pass.cpp
+++ b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_iter_rv.pass.cpp
@@ -52,7 +52,7 @@ int main()
         assert(r->first == 3);
         assert(r->second == 2);
     }
-#if __cplusplus >= 201103L
+#if TEST_STD_VER >= 11
     {
         typedef std::multimap<int, MoveOnly, std::less<int>, min_allocator<std::pair<const int, MoveOnly>>> M;
         typedef std::pair<int, MoveOnly> P;
@@ -83,5 +83,36 @@ int main()
         assert(r->second == 2);
     }
 #endif
+#if TEST_STD_VER > 14
+    {
+        typedef std::multimap<int, MoveOnly> M;
+        typedef std::pair<int, MoveOnly> P;
+        typedef M::iterator R;
+        M m;
+        R r = m.insert(m.cend(), {2, MoveOnly(2)});
+        assert(r == m.begin());
+        assert(m.size() == 1);
+        assert(r->first == 2);
+        assert(r->second == 2);
+
+        r = m.insert(m.cend(), {1, MoveOnly(1)});
+        assert(r == m.begin());
+        assert(m.size() == 2);
+        assert(r->first == 1);
+        assert(r->second == 1);
+
+        r = m.insert(m.cend(), {3, MoveOnly(3)});
+        assert(r == prev(m.end()));
+        assert(m.size() == 3);
+        assert(r->first == 3);
+        assert(r->second == 3);
+
+        r = m.insert(m.cend(), {3, MoveOnly(2)});
+        assert(r == prev(m.end()));
+        assert(m.size() == 4);
+        assert(r->first == 3);
+        assert(r->second == 2);
+    }
+#endif
 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 }
diff --git a/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_rv.pass.cpp b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_rv.pass.cpp
index b1c043586d6..86fc6cef043 100644
--- a/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_rv.pass.cpp
+++ b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_rv.pass.cpp
@@ -51,7 +51,7 @@ int main()
         assert(r->first == 3);
         assert(r->second == 3);
     }
-#if __cplusplus >= 201103L
+#if TEST_STD_VER >= 11
     {
         typedef std::multimap<int, MoveOnly, std::less<int>, min_allocator<std::pair<const int, MoveOnly>>> M;
         typedef M::iterator R;
@@ -81,5 +81,35 @@ int main()
         assert(r->second == 3);
     }
 #endif
+#if TEST_STD_VER > 14
+    {
+        typedef std::multimap<int, MoveOnly> M;
+        typedef M::iterator R;
+        M m;
+        R r = m.insert({2, MoveOnly(2)});
+        assert(r == m.begin());
+        assert(m.size() == 1);
+        assert(r->first == 2);
+        assert(r->second == 2);
+
+        r = m.insert({1, MoveOnly(1)});
+        assert(r == m.begin());
+        assert(m.size() == 2);
+        assert(r->first == 1);
+        assert(r->second == 1);
+
+        r = m.insert({3, MoveOnly(3)});
+        assert(r == prev(m.end()));
+        assert(m.size() == 3);
+        assert(r->first == 3);
+        assert(r->second == 3);
+
+        r = m.insert({3, MoveOnly(3)});
+        assert(r == prev(m.end()));
+        assert(m.size() == 4);
+        assert(r->first == 3);
+        assert(r->second == 3);
+    }
+#endif
 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 }
diff --git a/libcxx/test/support/MoveOnly.h b/libcxx/test/support/MoveOnly.h
index e4d9f649560..b9653516cfd 100644
--- a/libcxx/test/support/MoveOnly.h
+++ b/libcxx/test/support/MoveOnly.h
@@ -17,6 +17,7 @@
 
 class MoveOnly
 {
+    friend class MoveOnly2;
     MoveOnly(const MoveOnly&);
     MoveOnly& operator=(const MoveOnly&);
 
@@ -34,6 +35,29 @@ public:
     bool operator< (const MoveOnly& x) const {return data_ <  x.data_;}
 };
 
+class MoveOnly2
+{
+    MoveOnly2(const MoveOnly&);
+    MoveOnly2& operator=(const MoveOnly2&);
+
+    int data_;
+public:
+    MoveOnly2(int data = 1) : data_(data) {}
+    MoveOnly2(MoveOnly2&& x)
+        : data_(x.data_) {x.data_ = 0;}
+    MoveOnly2& operator=(MoveOnly2&& x)
+        {data_ = x.data_; x.data_ = 0; return *this;}
+    MoveOnly2(MoveOnly&& x)
+        : data_(x.data_) {x.data_ = 0;}
+    MoveOnly2& operator=(MoveOnly&& x)
+        {data_ = x.data_; x.data_ = 0; return *this;}
+
+    int get() const {return data_;}
+
+    bool operator==(const MoveOnly2& x) const {return data_ == x.data_;}
+    bool operator< (const MoveOnly2& x) const {return data_ <  x.data_;}
+};
+
 namespace std {
 
 template <>
@@ -43,6 +67,12 @@ struct hash<MoveOnly>
     std::size_t operator()(const MoveOnly& x) const {return x.get();}
 };
 
+template <>
+struct hash<MoveOnly2>
+    : public std::unary_function<MoveOnly, std::size_t>
+{
+    std::size_t operator()(const MoveOnly2& x) const {return x.get();}
+};
 }
 
 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES