This is the mail archive of the mailing list for the libstdc++ project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Fix stable_sort to work on iterators returning rvalue

Attached patch applied then.

2012-05-29 François Dumont <>

    * include/bits/stl_tempbuf.h (__uninitialized_construct_buf)
    (__uninitialized_construct_buf_dispatch<>::__ucr): Fix to work
    with iterator returning rvalue.
    * testsuite/25_algorithms/stable_sort/ New.


On 05/28/2012 09:59 PM, Christopher Jefferson wrote:
On 28 May 2012, at 20:00, François Dumont wrote:

On 05/28/2012 12:11 PM, Christopher Jefferson wrote:
My main concern is one I have mentioned previously. I'm unsure all our code works with things like move_iterator, even when it correctly compiles. We previously took out internal uses of move_iterator, because while the code compiled it did not work correctly. Look at bug : for any example.

With this change, code which uses move_iterator, and operator< which pass by value, will cause values to be 'eaten' during the sort. Now, the standard in my opinion doesn't say this would be a bug, but it certainly seems like it would be unpleasant.

How to fix this? The simplest way might be to wrap all predicates / operator< in a wrapper which just takes lvalue references. Not sure if it is worth going to that much pain just to fix this.

At the very least, I would want to see a bunch of tests which make sure we don't have any other code which accidentally 'eats' users data. Make sure you catch all the various bits of sort, some of which get triggered rarely. I realise that is putting other people to a higher standard than I put myself, but we have learnt this is a tricky area :)

Does it mean that you refuse the patch ?

The patch purpose is not to make the code compatible with move_iterator but to make it compatible with iterator types that return pure rvalue through their dereference operator. As a side effect std::move_iterator are going to compile too which might be bad but is it really a reason to forbid other kind of iterators ?

Of course we should find a good way to handle move_iterator, and I can spend some time on it, but I think that it should be the subject of a dedicated patch.
Sorry, just to clarify (also, I have been having problems with my mail client).

I believe this patch is good, I withdraw any complaint.

I believe there is a serious issue with move_iterator in use with almost all standard libraries, but it is disconnected from this patch.


Index: include/bits/stl_tempbuf.h
--- include/bits/stl_tempbuf.h	(revision 187979)
+++ include/bits/stl_tempbuf.h	(working copy)
@@ -1,7 +1,7 @@
 // Temporary buffer implementation -*- C++ -*-
 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
-// 2010, 2011
+// 2010, 2011, 2012
 // Free Software Foundation, Inc.
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -182,25 +182,25 @@
     struct __uninitialized_construct_buf_dispatch
-      template<typename _ForwardIterator, typename _Tp>
+      template<typename _Pointer, typename _ForwardIterator>
         static void
-        __ucr(_ForwardIterator __first, _ForwardIterator __last,
-	      _Tp& __value)
+        __ucr(_Pointer __first, _Pointer __last,
+	      _ForwardIterator __seed)
 	  if(__first == __last)
-	  _ForwardIterator __cur = __first;
+	  _Pointer __cur = __first;
-			      _GLIBCXX_MOVE(__value));
-	      _ForwardIterator __prev = __cur;
+			      _GLIBCXX_MOVE(*__seed));
+	      _Pointer __prev = __cur;
 	      for(; __cur != __last; ++__cur, ++__prev)
-	      __value = _GLIBCXX_MOVE(*__prev);
+	      *__seed = _GLIBCXX_MOVE(*__prev);
@@ -213,9 +213,9 @@
     struct __uninitialized_construct_buf_dispatch<true>
-      template<typename _ForwardIterator, typename _Tp>
+      template<typename _Pointer, typename _ForwardIterator>
         static void
-        __ucr(_ForwardIterator, _ForwardIterator, _Tp&) { }
+        __ucr(_Pointer, _Pointer, _ForwardIterator) { }
   // Constructs objects in the range [first, last).
@@ -223,23 +223,22 @@
   // their exact value is not defined. In particular they may
   // be 'moved from'.
-  // While __value may altered during this algorithm, it will have
+  // While *__seed may be altered during this algorithm, it will have
   // the same value when the algorithm finishes, unless one of the
   // constructions throws.
-  // Requirements: _ForwardIterator::value_type(_Tp&&) is valid.
-  template<typename _ForwardIterator, typename _Tp>
+  // Requirements: _Pointer::value_type(_Tp&&) is valid.
+  template<typename _Pointer, typename _ForwardIterator>
     inline void
-    __uninitialized_construct_buf(_ForwardIterator __first,
-				  _ForwardIterator __last,
-				  _Tp& __value)
+    __uninitialized_construct_buf(_Pointer __first, _Pointer __last,
+				  _ForwardIterator __seed)
-      typedef typename std::iterator_traits<_ForwardIterator>::value_type
+      typedef typename std::iterator_traits<_Pointer>::value_type
-	  __ucr(__first, __last, __value);
+	  __ucr(__first, __last, __seed);
   template<typename _ForwardIterator, typename _Tp>
@@ -254,9 +253,9 @@
 	  _M_buffer = __p.first;
 	  _M_len = __p.second;
-	  if(_M_buffer)
+	  if (_M_buffer)
 	    std::__uninitialized_construct_buf(_M_buffer, _M_buffer + _M_len,
-					       *__first);
+					       __first);
Index: testsuite/25_algorithms/stable_sort/
--- testsuite/25_algorithms/stable_sort/	(revision 0)
+++ testsuite/25_algorithms/stable_sort/	(revision 0)
@@ -0,0 +1,42 @@
+// Copyright (C) 2012 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
+// 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
+// <>.
+// [lib.stable.sort]
+#include <vector>
+#include <algorithm>
+#include <testsuite_hooks.h>
+  bool test __attribute__((unused)) = true;
+  std::vector<bool> bools;
+  bools.push_back(true);
+  bools.push_back(false);
+  bools.push_back(true);
+  bools.push_back(false);
+  std::stable_sort(bools.begin(), bools.end());
+  VERIFY( !bools[0] && !bools[1] && bools[2] && bools[3] );
+  test1();

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]