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 .