swap函数的高效实现：右值引用和move

原创内容：cxsmarkchan

转载请注明出处

右值引用是C++11的重要特性之一，合理采用右值引用，可以避免不必要的复制操作，提高程序运行的效率。本文以swap函数的实现为例，说明右值引用的相关应用。

1 swap函数的传统实现方法及其问题

一个典型的swap函数如下：

template<class T>
void swap(T& a, T& b){
    T tmp = a; //调用复制构造函数
    a = b; //调用operatpr=
    b = tmp; //调用operatpr=
}
           

如果T是简单类型，则上述转换没有问题。但如果T是含有指针的复合数据类型，则上述转换中会调用一次复制构造函数，两次赋值运算符重载。以一个向量类型为例：

class vector{
private:
    int *_arr;
    int _size;
public:
    //仅考虑复制构造函数和赋值运算符重载
    vector(const vector& _right){
        _size = _right._size;
        _arr = new int[_size];
        for(int i = ; i < _size; i++){
            _arr[i] = _right._arr[i]; //该步骤需要重复_size次
        }
    }

    vector& operator=(const vector& _right){
        if(this != &_right){
            if(_arr != NULL)
                delete[] _arr;
            _size = _right._size;
            _arr = new int[_size];
            for(int i = ; i < _size; i++){
                _arr[i] = _right._arr[i]; //该步骤需要重复_size次
            }
        }
    }

    //析构函数
    ~vector(){
        if(_arr != NULL)
            delete[] _arr;
    }
};
           

不难看出，复制构造函数和赋值运算符重载函数的复杂度均为O(_size)，因此swap函数的复杂度亦为O(_size)。因此，这并不是一个高效的交换方法。

其实，执行

T tmp = a

时，本可以将

tmp._arr

直接指向

a._arr

，而不用执行一遍复制操作。遗憾的是，程序在执行

T tmp = a

时，会假设

a

和

tmp

是两个不同的变量，且将来都会被调用，因此只能将

a

复制一份给

tmp

。

一种变通的解决方案是如下函数：

void swap(vector& var1, vector& var2){
    int* _tmp_arr = var1._arr;
    var1._arr = var2._arr;
    var2._arr = _tmp_arr;
    int _tmp_size = var1._size;
    var1._size = var2._size;
    var2._size = _tmp_size;
}
           

该函数在交换vector变量时，复杂度为O(1)。不足之处是，

_arr

和

_size

是私有变量，需要通过友元函数来实现；同时对于每个不同的类型，都需要重写一遍swap函数。

右值引用可以很好地解决这一问题。

2 右值引用和move语义

2.1 右值

表达式的值可以分为左值和右值。左值可以出现在赋值表达式的左端或右端，右值则只能出现在赋值表达式的右端。例如：

string a;
a = "1234";
           

其中的

a

即为左值，而

"1234"

则为右值。简单地说，左值是一定意义上的持久变量，在表达式执行完后仍可以存在，右值则是临时变量，在表达式执行完毕后，就会被销毁。此外，一种比较简单的区分方式是：左值可以执行取地址操作，右值则不可以。从这个角度来说，有定义的变量均为左值，而函数返回值则为右值。

2.2 右值引用

所谓右值引用，则是指向右值的引用，可以用

&&

来定义：

右值引用也可以作为参数传入函数中：

// 假设Class1为有定义的类型
Class1 f1(){...}
void f2(const Class1&){...}
void f2(Class1&&){...}
int main(){
    Class1 c1;
    f2(c1); //调用f2(Class1&)
    f2(f1()); //调用f2(Class1&&)
}
           

在以上例子中，可以看出左值引用和右值引用的应用场景。对于

f2(c1)

，传入的是左值引用，该函数中必须假设参数

c1

在将来还有别的用处，因此不能轻易对

c1

的值进行修改，如果

f2

中要用到

c1

中动态开辟的对象，就需要复制一份；而

f2(f1())

中，传入的是右值引用，函数中已知传入的参数在本次调用后就会被销毁，可以直接将传入参数中的某些动态开辟的对象“据为己有”，无需复制。

移动构造函数和移动赋值运算符是比较典型的应用，如2.3节。

2.3 移动构造函数和移动赋值运算符

移动构造函数和移动赋值运算符如下：

//以下函数均在vector类中
//移动（move）构造函数
vector(vector&& _right){
    _size = _right._size;
    _arr = _right._arr; //由于知道_right引用的是临时变量，不会被继续使用，因此可以把_right._arr直接拿过来（即移动）
    _right._arr = NULL; //这个语句是表示_right对_arr已经失去所有权，防止_right在析构时销毁_arr。
}
//移动赋值运算符
vector& operator=(vector&& _right){
    if(this != &_right){
        if(_arr != NULL)
            delete[] _arr;
        _size = _right._size;
        _arr = _right._arr; //同样地，知道_right是右值引用，就可以直接把_right._arr拿过来。
        _right._arr = NULL;
    }
}
           

与第1节的复制构造函数和赋值运算符相比，移动构造函数和移动赋值运算符实现了右值中一些动态对象的“废物利用“，无需进行复制操作，从而可以极大地提高效率。

2.4 std::move函数

std::move

函数可以将左值转换为右值，该做法的意义在于：如果已知某个左值将来不会再用到，就可以用该函数将其转换为右值，传入含右值引用的函数中，进行”废物利用“。例如：

Class1 c1;
f2(c1); //调用f2(Class1&)函数
f2(std::move(c1)); //调用f2(Class1&&)函数，但程序员需要保证之后不会再用到c1的数据。
           

3 swap函数的高效实现

综合上述内容，swap函数的一个高效实现方法为：

template<class T>
void swap(T& var1, T& var2){
    T tmp = std::move(var1); //调用移动构造函数
    var1 = std::move(var2); //调用operator=(T&&)
    var2 = std::move(tmp); //调用operator=(T&&)
}
           

此时，swap中三次调用的均为move类函数，而这些函数的时间复杂度均为O(1)，因此swap的整体时间复杂度为O(1)。

4 小结

右值引用表示该引用对象今后将不再使用，在对象被析构之前，可以回收利用其中的一些有效信息。合理地运用右值引用，可以提高程序的运行效率。建议在含有动态对象的类中，都要写移动构造函数和移动赋值运算符重载函数。同时，如果确认某些对象不再使用，也可以使用move函数传入其右值引用。