Getting improved iter_swap into 4.0?

[Chris Jefferson <caj at cs dot york dot ac dot uk>]

I attach a patch to stl_algobase.h that calls swap when iter_swap is 
passed two iterators with identical value_type, and also a test case 
that tests a few things. Note that this all tests in this test case pass 
with the existing implementation except (obviously) the single test 
which checks if iter_swap calls swap.

Note that while it might look like this patch changes std::swap, it in 
fact doesn't. I simply had to swap the order of iter_swap and swap so 
that iter_swap could call swap, hence why it appears in the diff.

This is a very simple patch and it wouldn't suprise me if someone else 
can come up with a better method of implementing this. Feel free :)

Now to the important point. I know that offically 4.0 is supposed to be 
frozen now except for a select number of projects. However I personally 
believe that it is very important that this works it's way into 4.0. In 
theory it should not effect existing code at all, and (obviously) 
produces quite huge improvements when people perform operations on large 
objects. I'm sure I'm not the only person who occasionally simply calls 
sort on an array of very long vector<ints>. Note that (as was discussed 
before) it looks like the standard may be changed to require this in a 
later version, and both STLport and icc already use swap to implement 
iter_swap (in fact this implementation is more lax than these, as if the 
value_types of the iterators are different it falls back on a simple 
assignment swap, which is not the case in icc and STLport).

However, it is also possible that it may break some code which was badly 
written before. The two main areas where I believe this can happen is 
where the value_type of the iterators have not been correctly defined or 
(obviously) where a swap(T&,T&) function has been declared but 
incorrectly implemented. I feel users will be "happier" with a change 
which 'breaks' code (even if it was originally incorrectly implemented) 
at a .0 release more than any other.

Of course if anyone feels that there might be as-yet unknown bugs to 
sort out from this, then I'm happy to leave it. However what are the 
chances of sneaking it into 4.0?

Sorry for the long rambling message,

Chris
--- stl_algobase.h.backup	2004-09-10 20:45:29.000000000 +0100
+++ stl_algobase.h	2004-09-10 23:14:30.000000000 +0100
@@ -77,6 +77,51 @@
 
 namespace std
 {
+
+  /**
+   *  @brief Swaps two values.
+   *  @param  a  A thing of arbitrary type.
+   *  @param  b  Another thing of arbitrary type.
+   *  @return   Nothing.
+   *
+   *  This is the simple classic generic implementation.  It will work on
+   *  any type which has a copy constructor and an assignment operator.
+  */
+  template<typename _Tp>
+    inline void
+    swap(_Tp& __a, _Tp& __b)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_SGIAssignableConcept<_Tp>)
+
+      const _Tp __tmp = __a;
+      __a = __b;
+      __b = __tmp;
+    }
+
+  template<typename _ForwardIterator1, typename _ForwardIterator2,int _I>
+    struct __iter_swap_helper
+    {
+      static void
+      __iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
+      {
+        typedef typename iterator_traits<_ForwardIterator1>::value_type
+          _ValueType1;
+        const _ValueType1 __tmp = *__a;
+        *__a = *__b;
+        *__b = __tmp; 
+      }
+    };
+
+  template<typename _ForwardIterator1, typename _ForwardIterator2>
+    struct __iter_swap_helper<_ForwardIterator1, _ForwardIterator2, 1>
+    {
+      static void 
+      __iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
+      {
+        swap(*__a, *__b);
+      }
+    };
   /**
    *  @brief Swaps the contents of two iterators.
    *  @param  a  An iterator.
@@ -104,31 +149,9 @@ namespace std
 				  _ValueType2>)
       __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
 				  _ValueType1>)
-
-      const _ValueType1 __tmp = *__a;
-      *__a = *__b;
-      *__b = __tmp;
-    }
-
-  /**
-   *  @brief Swaps two values.
-   *  @param  a  A thing of arbitrary type.
-   *  @param  b  Another thing of arbitrary type.
-   *  @return   Nothing.
-   *
-   *  This is the simple classic generic implementation.  It will work on
-   *  any type which has a copy constructor and an assignment operator.
-  */
-  template<typename _Tp>
-    inline void
-    swap(_Tp& __a, _Tp& __b)
-    {
-      // concept requirements
-      __glibcxx_function_requires(_SGIAssignableConcept<_Tp>)
-
-      const _Tp __tmp = __a;
-      __a = __b;
-      __b = __tmp;
+      __iter_swap_helper<_ForwardIterator1, _ForwardIterator2, 
+                         __are_same<_ValueType1, _ValueType2>::_M_type>
+        ::__iter_swap(__a,__b);
     }
 
   #undef min

// 25.2.2 iter_swap
//
// Copyright (C) 2004 Free Software Foundation, Inc.
// This program 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 2 of the License, or 
// (at your option) any later version.                             
//                                                         
// This program is distributed in the hope that it will be useful,   
// but WITHOUT ANY WARRANTY; without even the implied warranty of    
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the    
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software       
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
// USA


#include <vector>
#include <list>
#include <testsuite_hooks.h>

using std::vector;
using std::list;
using std::iter_swap;

int swaps=0;
struct SwapClass {};
struct NoSwap {
  NoSwap(int _i): i(_i) {}
  int i;
};

void 
swap(SwapClass& a, SwapClass& b) {
  swaps++;
}



vector<int> vec_int;
vector<vector<int> > vec_vec_int;
list<int> list_int;
vector<SwapClass> vec_swap;
list<SwapClass> list_swap;
vector<NoSwap> vec_noswap;
list<NoSwap> list_noswap;
int array_int[2]={0,1};

int
main()
{
  // Setup
  vec_int.push_back(1);
  vec_int.push_back(1);
  vec_vec_int.push_back(vec_int);
  vec_int[0] = 0;
  vec_vec_int.push_back(vec_int);
  list_int.push_back(0);
  list_int.push_back(1);
  vec_swap.push_back(SwapClass());
  vec_swap.push_back(SwapClass());
  list_swap.push_back(SwapClass());
  list_swap.push_back(SwapClass());
  vec_noswap.push_back(NoSwap(0));
  vec_noswap.push_back(NoSwap(1));
  list_noswap.push_back(NoSwap(0));
  list_noswap.push_back(NoSwap(1));

  // Tests
  // Normal array of integers
  iter_swap(array_int,array_int+1);
  VERIFY(array_int[0] == 1 && array_int[1] == 0);

  // std::vector of integers
  iter_swap(vec_int.begin(), --vec_int.end());
  VERIFY(vec_int[0] == 1 && vec_int[1] == 0);

  // std::vector of std::vector of integers
  iter_swap(vec_vec_int.begin(), --vec_vec_int.end());
  VERIFY(vec_vec_int[0][0] == 0 && vec_vec_int[1][0] == 1);
  
  // std::list of integers
  iter_swap(list_int.begin(), --list_int.end());
  VERIFY(*(list_int.begin()) == 1 && *(--list_int.end()) == 0);

  // Check that a class with a specialised swap has it called
  iter_swap(vec_swap.begin(), --vec_swap.end());
  iter_swap(list_swap.begin(), --list_swap.end());
  VERIFY(swaps == 2);

  // Check that a class with no specialised swap still works
  iter_swap(vec_noswap.begin(), --vec_noswap.end());
  iter_swap(list_noswap.begin(), --list_noswap.end());
  VERIFY(vec_noswap[0].i == 1 && vec_noswap[1].i == 0);
  VERIFY((*list_noswap.begin()).i == 1);
  VERIFY((*--list_noswap.end()).i == 0);
}