Fix a problem in inplace_merge, where we leave objects in a moved-from state.

[mclow.lists]

Summary

Bug report from Ted K, and solution outlined by Duncan Exon Smith.
Thanks for the info!

[EricWF]

Adding review comments. LGTM after addressing the comments.

include/algorithm

4365

_LIBCPP_INLINE_VISIBILITY

test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp

23

TEST_STD_VER >= 11 instead?

32

Should we assert that no self move-assignment occurs?

[mclow.lists]

Committed as revision 243530

include/algorithm

4365

I don't think so. That's a reasonably large function. Note that __merge is not so decorated.

include/algorithm

 
 // inplace_merge
 
+template <class _Compare, class _InputIterator1, class _InputIterator2,
+          class _OutputIterator>
+void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
+                          _InputIterator2 __first2, _InputIterator2 __last2,
+                          _OutputIterator __result, _Compare __comp)
+{
+    for (; __first1 != __last1; ++__result)
+    {
+        if (__first2 == __last2)
+        {
+            _VSTD::move(__first1, __last1, __result);
+            return;
+        }
+
+        if (__comp(*__first2, *__first1))
+        {
+            *__result = _VSTD::move(*__first2);
+            ++__first2;
+        }
+        else
+        {
+            *__result = _VSTD::move(*__first1);
+            ++__first1;
+        }
+    }
+    // __first2 through __last2 are already in the right spot.
+}
+
 template <class _Compare, class _BidirectionalIterator>
 void
 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,

         value_type* __p = __buff;
         for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p)
             ::new(__p) value_type(_VSTD::move(*__i));
-        __merge<_Compare>(move_iterator<value_type*>(__buff),
-                          move_iterator<value_type*>(__p),
-                          move_iterator<_BidirectionalIterator>(__middle),
-                          move_iterator<_BidirectionalIterator>(__last),
-                          __first, __comp);
+        __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
     }
     else
     {

             ::new(__p) value_type(_VSTD::move(*__i));
         typedef reverse_iterator<_BidirectionalIterator> _RBi;
         typedef reverse_iterator<value_type*> _Rv;
-        __merge(move_iterator<_RBi>(_RBi(__middle)), move_iterator<_RBi>(_RBi(__first)),
-                move_iterator<_Rv>(_Rv(__p)), move_iterator<_Rv>(_Rv(__buff)),
+        __half_inplace_merge(_Rv(__p), _Rv(__buff), 
+                             _RBi(__middle), _RBi(__first),
                              _RBi(__last), __negate<_Compare>(__comp));
     }
 }
 

test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp

 
 #include "test_iterators.h"
 
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+struct S {
+  S() : i_(0) {}
+  S(int i) : i_(i) {}
+  
+  S(const S&  rhs) : i_(rhs.i_) {}
+  S(      S&& rhs) : i_(rhs.i_) { rhs.i_ = -1; }
+  
+  S& operator =(const S&  rhs) { i_ = rhs.i_;              return *this; }
+  S& operator =(      S&& rhs) { i_ = rhs.i_; rhs.i_ = -2; return *this; }
+  S& operator =(int i)         { i_ = i;                   return *this; }
+  
+  bool operator  <(const S&  rhs) const { return i_ < rhs.i_; }
+  bool operator ==(const S&  rhs) const { return i_ == rhs.i_; }
+  bool operator ==(int i)         const { return i_ == i; }
+
+  void set(int i) { i_ = i; }
+  
+  int i_;
+  };
+#endif
+
 template <class Iter>
 void
 test_one(unsigned N, unsigned M)
 {
+    typedef typename std::iterator_traits<Iter>::value_type value_type;
     assert(M <= N);
-    int* ia = new int[N];
+    value_type* ia = new value_type[N];
     for (unsigned i = 0; i < N; ++i)
         ia[i] = i;
     std::random_shuffle(ia, ia+N);

     test<bidirectional_iterator<int*> >();
     test<random_access_iterator<int*> >();
     test<int*>();
+
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+    test<bidirectional_iterator<S*> >();
+    test<random_access_iterator<S*> >();
+    test<S*>();
+#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 }

test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp

         {return *x < *y;}
 };
 
+struct S {
+  S() : i_(0) {}
+  S(int i) : i_(i) {}
+  
+  S(const S&  rhs) : i_(rhs.i_) {}
+  S(      S&& rhs) : i_(rhs.i_) { rhs.i_ = -1; }
+  
+  S& operator =(const S&  rhs) { i_ = rhs.i_;              return *this; }
+  S& operator =(      S&& rhs) { i_ = rhs.i_; rhs.i_ = -2; return *this; }
+  S& operator =(int i)         { i_ = i;                   return *this; }
+  
+  bool operator  <(const S&  rhs) const { return i_ < rhs.i_; }
+  bool operator  >(const S&  rhs) const { return i_ > rhs.i_; }
+  bool operator ==(const S&  rhs) const { return i_ == rhs.i_; }
+  bool operator ==(int i)         const { return i_ == i; }
+
+  void set(int i) { i_ = i; }
+  
+  int i_;
+  };
+
+
 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
 #include "test_iterators.h"

 test_one(unsigned N, unsigned M)
 {
     assert(M <= N);
-    int* ia = new int[N];
+    typedef typename std::iterator_traits<Iter>::value_type value_type;
+    value_type* ia = new value_type[N];
     for (unsigned i = 0; i < N; ++i)
         ia[i] = i;
     std::random_shuffle(ia, ia+N);
-    std::sort(ia, ia+M, std::greater<int>());
-    std::sort(ia+M, ia+N, std::greater<int>());
-    binary_counting_predicate<std::greater<int>, int, int> pred((std::greater<int>()));
+    std::sort(ia, ia+M, std::greater<value_type>());
+    std::sort(ia+M, ia+N, std::greater<value_type>());
+    binary_counting_predicate<std::greater<value_type>, value_type, value_type> pred((std::greater<value_type>()));
     std::inplace_merge(Iter(ia), Iter(ia+M), Iter(ia+N), std::ref(pred));
     if(N > 0)
     {
         assert(ia[0] == N-1);
         assert(ia[N-1] == 0);
-        assert(std::is_sorted(ia, ia+N, std::greater<int>()));
+        assert(std::is_sorted(ia, ia+N, std::greater<value_type>()));
         assert(pred.count() <= (N-1));
     }
     delete [] ia;

     test<int*>();
 
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+    test<bidirectional_iterator<S*> >();
+    test<random_access_iterator<S*> >();
+    test<S*>();
+
     {
     unsigned N = 100;
     unsigned M = 50;