C++ 中交换两个值

本文中我们尝试以标准库编写者的身份实现C++标准程序库里最简单的算法之一：iter_swap。它卑微的职责就是接受两个迭代器并交换他们各自指向的对象的值，就像这样： 

template<class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2) {
  T tmp = *i1;
  *i1 = *i2;
  *i2 = tmp;
}

显然这并不能编译通过，因为T没有被定义。那么，它到底应该是什么呢？

因为我们现在扮演的是标准库编写者，我们可以要求所有迭代器实现提供一个名为value_type的嵌套类型，这样就可以用它替换上文的T了: 

template<class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2) {
  typename ForwardIterator1::value_type tmp = *i1;
  *i1 = *i2;
  *i2 = tmp;
}

如果你对这里的typename关键字迷惑不解，就应该先去看看C++标准。

到这里，我们应该可以实现这个算法了，遗憾的是，并没有。 C++中迭代器的设计是模仿指针的，这样做的用意是普通指针也可以用作合法的迭代器。 

void f(int* p1, int* p2) {
  iter_swap(p1, p2); // error: int* 没有 value_type 成员
}

我们尝试一个几乎可以解决任何问题的方法——引入额外的中间层。我们无法向所有迭代器中添加嵌套的::value_type，但是可以将其添加到带有一个迭代器类型参数的模板。在标准中，这个模板称为 iterator_traits： 

template<class Iterator> struct iterator_traits;

我们可以将它用在iter_swap中： 

template<class Iterator>
struct iterator_traits {
  typedef typename Iterator::value_type value_type;
}
template<class T>
struct iterator_traits<T*> {
  typedef T value_type;
  //...
}

template<class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2) {
  typename iterator_traits<ForwardIterator1>::value_type tmp = *i1;
  *i1 = *i2;
  *i2 = tmp;
}

问题并没有就此结束。假设我们就这样设计iter_swap，不久就会收到大量来着关心性能的客户的issue，抱怨我们定义的iter_swap对某些迭代器来说效率低下得可怕，有个家伙传入了一个 std::list<std::vector<std::string>> 的迭代器。

幸运的是，标准库中提供了一个可以用于vector的高效的swap，它只交换少量的内部指针，我们可以回复用户这样就可以了： 

std::swap(*i1, *i2);

然而这样的回答并不能令人满意。没什么iter_swap不去做这个工作而要交给用户呢？这就产生了另一个版本： 

template<class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2) {
  std::swap(*i1, *i2);
}

看上去挺好，但是你应该注意到了，iter_swap可以交换两个不同的类型，二swap函数只能交换两个相同的对象。

我们可以这样来解决这个问题：让那个慢的iter_swap实现保持不动，同时加入一个重载版本，让相同类型的迭代器使用swap： 

// 慢但总是可以
template<class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2) {
  typename iterator_traits<ForwardIterator1>::value_type tmp = *i1;
  *i1 = *i2;
  *i2 = tmp;
}

// 有时候更快
template<class ForwardIterator>
void iter_swap(ForwardIterator i1, ForwardIterator i2) {
  std::swap(*i1, *i2);
}

这样就可以交付使用了！

也许还有一些不够完美的地方。如果向iter_swap传入 std::vector<std::string> 和 std::list<std::string> 的迭代器会发生什么呢？这两个迭代器拥有相同的value_type，但是由于迭代器自身的类型不同，因此快速的iter_swap重载将不会被调用。我们可以对swap稍作改写： 

template<class T1, class T2>
void swap(T1& a, T2& b) {
  T1 tmp = a;
  a = b;
  b = tmp;
}

不幸的是，这种修改会使一类迭代器无法使用，就是operator*重载产生一个代理引用的哪一种迭代器。最广为人知的就是 vector<bool> 的迭代器了。 vector<bool> 以一个位存储每一个元素。由于实际上并不存在指向一个位之类的东西，所以使用了一个代理。

最终，我们需要的是这样一种方式：只有当迭代器具有相同的value_type并且其引用类型是真正的引用而非代理时才去使用快速的iter_swap。这就涉及两个问题：

  1. T是一个真正的引用吗？
  2. 这两个value_type相同吗？

为了方便，我们直接使用Boost来做这样辅助作这个选择： 

#include <boost/type_traits/is_reference.hpp>
#include <boost/type_traits/is_same.hpp>
#include <iterator> // iterator_taits
#include <utility>  // swap

namespace std {
  template<bool use_swap> struct iter_swap_impl;
  template<>
  struct iter_swap_impl<true> {
  template<class ForwardIterator1, class ForwardIterator2>
  static void do_it(ForwardIterator1 i1, ForwardIterator2 i2) {
  std::swap(*i1, *i2);
  }
  };
  template<>
  struct iter_swap_impl<false> {
  template<class ForwardIterator1, class ForwardIterator2>
  static void do_it(ForwardIterator1 i1, ForwardIterator2 i2) {
  typename iterator_traits<ForwardIterator1>::value_type tmp = *i1;
  *i2 = *i2;
  *i2 = tmp;
  }
  };

  template<class ForwardIterator1, class ForwardIterator2>
  void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2) {
  typedef iterator_traits<ForwardIterator1> traits1;
  typedef typename traits1::value_type v1; 
  typedef typename traits1::reference r1; 

  typedef iterator_traits<ForwardIterator2> traits2;
  typedef typename traits2::value_type v2; 
  typedef typename traits2::reference r2; 

  bool const use_swap = boost::is_same<v1, v2>::value
  && boost::is_reference<r1>::value
  && boost::is_reference<r2>::value;

  iter_swap_impl<use_swap>::do_it(i1, i2);
  }
};

这样应该就可以高兴地收工了。

By .