[TOC]

术语介绍

  • Rule Of Three 引自WikiPedia, Rule of three) > The rule of three(also known as the Law of The Big Three or The Big Three) is a rule of thumb in C++ that claims that if a class defines one of the following, it should probably explicitly define all three: 1. destructor; 2. copy constructor; 3. copy assignment operator

说的是如果一个类定义了下面三个函数中的任意一个, 那么这个类很有可能需要明确地在类中定义全部这三个函数: 1. 析构函数; 2. 拷贝构造函数; 3. 赋值操作符

  • Copy And Swap Idiom

    首先, Idiom在这里的意思是指在计算机编程当中所常用到的一些做法和技巧, 参考Programming idiom

    然后是Copy-and-swap. Copy-and-swap指的是在写一个需要实现Rule of Three中提到的三个函数的类时, 使用的一个技巧, 这个技巧用于编写赋值操作符, 而使用这个技巧写出来的赋值操作符函数不仅避免了"代码的复制", 还满足"强异常安全"函数的要求.

Rule Of Three

问题的引出

想要实现一个Trie数据结构, 其支持小写字母的字符串的快速插入,删除和查询. 最开始的API如下所示:

// trie.h
class Trie {
  public:
    Trie();
    ~Trie();
    size_t size();
    bool contains(const string& key) const;
    void insert(const string& key);
    void remove(const string& key);
    string longestPrefixOf(string query) const; // Trie中包含query的最长前缀
    vector<string> keys() const; // Trie中包含的所有字符串
    vector<string> keysWithPrefix(const string& key) const;
  private:
    class Node;
    const static int R = 26; // 26个小写字母
    Node *root; // Node是代表Trie树中每个节点的辅助类
    destroy(Node *x) // 被析构函数调用, 销毁以x节点为根节点的Trie树
}

// trie.cc
// 在main中测试一下Trie类的功能
// 代码有点code duplicate, 因为主要是用来演示用
// 对此反感的话, 请直接看每段注释
int main() {
    // 新建一个Trie trie, 并且插入三个单词
    // 然后打印出trie中所包含的所有单词
    Trie trie = Trie();
    cout << "The size of the trie is: ";
    cout << trie.size() << endl;
    trie.insert("she");
    trie.insert("sells");
    trie.insert("shore");
    vector<string> vs;
    vs = trie.keys();
    for (vector<string>::iterator it = vs.begin(); it != vs.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;

    // 使用trie来copy construct一个newTrie
    // 并且调用remove删除掉newTrie中的一个字符串
    // 然后打印newTrie和trie中的所有字符串
    Trie newTrie(trie);
    cout << "The size of the newTrie is: ";
    cout << newTrie.size() << endl;
    newTrie.remove("sells");
    vs = newTrie.keys();
    for (vector<string>::iterator it = vs.begin(); it != vs.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
    vs = trie.keys();
    for (vector<string>::iterator it = vs.begin(); it != vs.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

对于第二段, 我们预期的正确结果应该是newTrie打印的是"she shore"而trie打印出来的则是"sells she shore".

然而编译运行之后, 结果却是newTrie确实打印出的是"she shore"但是trie打印出来的也是"she shore", 而且, 程序执行到最后就崩溃了.

那么就那gdb来看一下, 为什么会这样吧. 使用gdb的基本调试功能run和backtrace. run命令出来的结果还好说, 最后给出的一个错误信息就只是一个 segment fault, 然而使用backtrace命令来查看调用栈的错误的时候, 就发现Trie::destroy(Trie::Node*)()被无限调用, 进入了一个死循环.

问题的确定

思考一下原因, destroy()函数会被无限调用, 就说明错误应该出在析构函数上面, 因为整个类中只有析构函数用到了destroy()这个函数, 但是粗看之下 并没有发现太多的问题:"Trie和newTrie各种调用自己的析构函数, 应该不会有问题吧???" 但是输出的结果当中还有另外一个结果不符合预期的结果, 那就是newTrie删除了一个字符串之后, trie的字符串中也删除了相应的字符串. 然后再考虑到Trie中代表根节点的数据结构是一个指向Node的指针, 而 newTrie是由trie拷贝构造而成的, 几个点结合起来看, 形成了下面一个比较符合逻辑的推断:Trie newTrie(trie)这个拷贝构造, 将trie中的root 指针也拷贝给了newTrie, 也就是说, newTrie和trie的指针指向的是同一颗Trie树.

上面的逻辑能够解释错误的两个点:

  1. 删除newTrie中的字符串, 造成trie中字符串删除, 显而易见;

  2. gdb在追踪调用栈的时候将错误定位在destroy()函数, 也可以说是析构函数中. 因为newTrie和trie在脱离main函数之后, 都要经由析构函数 进行析构, 无论哪个先析构, 总会造成root为空指针, 而第二个再析构的时候, 其行为应该是未定义(undefined)的.

了解编译器偷偷干了些什么

细看Trie class的定义, 可以发现, 并没有定义一个拷贝构造函数. 但是在实际的测试代码中, 我们确实用到了它, 而且编译通过, 运行成功了, 就是 其最后的结果好像不是很理想. 那么很容易就能够联想到, 应该是编译器替我们的Trie类生成了拷贝构造函数.

参考c++98的标准, 在第12节Special member functions的开头, 能够找到如下描述:

The default constructor, copy constructor, and copy assignment constructor, and the destructor are special member functions. The implementation will implicitly declare these member functions for a class type when the program does not explicitly declare them, except as noted in 12.1. The implementation will define them if they are used, as specified in 12.1, 12.4 and 12.8.

标准中说得很清楚, 当我们类自己没有声明自己的缺省构造函数, 拷贝构造函数, 拷贝赋值操作符, 或者析构函数的时候, 编译器会默默地声明这些函数. 这4个函数被称为Special member functions, 而当这4个函数中某个函数被调用的时候, 编译器又会自动为我们的类定义这个函数.

如果我们定义了一个空类, 那么实际上它经过编译器的编译之后会看起来像这样.

// 定义一个空类
class Empty {};

// 上面的空类, 和下面的类的作用效果是一样的.
// 编译器暗中声明的函数, 只有在被调用时才会被创建出来.
class Empty {
  public:
    Empty() {...}
    ~Empty() {...}
    Empty(const Empty& rhs) {...}
    Empty& operator=(const Empty& rhs) {...}
}

先抛开缺省构造函数和析构函数不管, 我们现在的想要了解编译器自动生成的拷贝构造函数和拷贝赋值操作函数在被调用的时候, 它们是怎样将一个物件中的成员变量赋值给另外一个物件.

继续参考c++98标准, 在第12.8节Copy class object的第8条和第13条描述了编译器自动生成的这两个函数的工作方式, 由于两个的工作方式基本一样, 所以这里给出一个, 第8条, 引用:

The implicitly-defined copy constructor for class X performs a memberwise copy of its subobjects. The order of copying is the same as the order of initialization of bases and members in a user-defined constructor. Each subobjects is copied in the manner approriate to its type:

  • if the subobject is of class type, the copy constructor for the class is used;
  • if the subobject is an array, each element is copied, in the manner approriate to the element type;
  • if the subobject is of scalar type, the built-in assignment operator is used.

上面的所提到的, 前两个类型都一目了然, 那么第三条的scalar type又指代的是什么样子的数据类型呢?

在标准的3.9节Types的第10条, 写着:

Arithmetic types, enumeration types, pointer types, and pointer to member types, and cv-qualified versions of these types are collectively called scalar type.

可以看到, 指针类型, 指向类中成员(non-static)的指针类型, 都属于scalar type. 结合上面编译器自动生成的两个函数的工作方法, 我们可以得出下列的推断, 当我们的类中包含了一个指针的话, 而且我们又没有自己定义拷贝构造函数和拷贝赋值操作符, 那么编译器自动生成的这两个函数, 会在它们里面做类似下面的操作:

// 假设a是一个在X类中的指向一个non-static变量的指针
X (const X& rhs) {
    this->a = rhs.a;
}

X& operator=(const X& rhs) {
    this->a = rhs.a;
    return *this;
}

那么看下面的代码.

#include <iostream>
using namespace std;
struct X {
    X(int * a) {
        this->a = a;
    }
    int *a;
};

int main() {
    int a = 10;
    X x1(&a);
    X x2(x1);
    *x2.a = 20;
    cout << *x1.a << endl;
}

其输出是什么呢? 答案当然是20. 因为x2使用编译器所创建的拷贝构造函数经由x1生成, 如我们上面提到的, 这个拷贝构造函数里面不过是做了将自己的a指针的地址赋值给x2的a指针, 所以两个指针指向的是相同的一个int变量. 通过x2.a改变指向的int变量的值当然改变了x1.a所dereference出来的值.

那么, 我们当初的问题的答案就很清晰了, 因为有个Nodo *root指针在Trie类中, 而且我们没有自己的拷贝构造函数和拷贝赋值操作符, 这两个的函数, 在被调用时都是编译器给我们创建的. 因此, trie和newTrie的root指向的当然会是同一个Trie树, 而后面所发生的错误, 就很容易理解了.

那么既然知道了编译器创建的这些特殊的成员函数在使用当中可能会有问题, 那么该怎么样去选择什么时候应该自己明确定义这些函数, 什么时候可以不用定义呢?

首先, 对于缺省构造函数来说, 如果缺省构造函数无法正确地初始化我们的类所有的变量, 我们就应该自己写一个构造函数. 对于剩下的另外三个有怎么样做决定呢?

根据开头所说的: 如果我们的类中包括了拷贝构造, 析构, 拷贝赋值操作这三个函数中的一个, 那么我们很可能需要明确定义全部这三个函数. 简单来说, 要么全部定义, 要么全部不定义.

三个函数全部不定义

先举一个全部不定义的列子.

#include <iostream>
using namespace std;
struct Date {
    friend ostream& operator<<(ostream& os, const Date& d);
    Date(int y, int m, int d)
        : year(y), month(m), day(d) {}
    int year, month, day;
};

ostream& operator<< (ostream& os, const Date& d) {
    cout << d.year << "-" << d.month << "-" << d.day;
    return os;
}

class System {
public:
    // 并没有定义三个特殊的成员函数
    // 如果类中重载了构造函数, 要使用缺省构造函数需明确定义
    System() : name(""), birthday(1900, 1, 1) {

    }
    // 重载构造函数
    System(const string& n, const Date& birth)
        : name(n), birthday(birth) {}
    void setName(const string& n) {name = n;}
    string getName() {return name;}
    Date getBirthday() {return birthday;}
    void setBirthday(const Date &d) {birthday = d;}
private:
    string name;
    Date birthday;
};

int main() {
    Date bd1(1970, 1, 1);
    Date bd2(1977, 1, 1);
    Date bd3(2001, 3, 24);
    string name = "Unix";
    System p1(name, bd1); // 使用重载过的构造函数
    System p2(p1);        // 使用编译器自动生成的拷贝构造函数
    System p3;            // 使用缺省构造函数
    p3 = p1;              // 使用编译器自动生成的拷贝赋值操作符
    p2.setName("Linux");  // 对后面连个System物件, 设置名称和生日
    p3.setName("OS X");
    p2.setBirthday(bd2);
    p3.setBirthday(bd3);
    // 输出最后三个System物件的信息
    cout << "p1: " << p1.getName() << " " << p1.getBirthday() << endl
         << "p2: " << p2.getName() << " " << p2.getBirthday() << endl
         << "p3: " << p3.getName() << " " << p3.getBirthday() << endl;
}

可以看到, 在System类中并没有定义析构函数, 拷贝构造函数和拷贝赋值操作符三个特殊的成员函数, 但是在main当中, 依然是能够正常地调用后面两个函数进行复制的操作. 修改p2, 和p3中的name和birthday对于p1都没有造成影响. 从代码的角度来看, 在复制的过程中做了下列的操作:

System p2(p1); // 编译器为System类创建拷贝构造函数, 如下

// 关于为什么拷贝构造函数的参数是const X&, 可以参考标准, 有详细说明
System(const System& rhs) : name(rhs.name), birthday(rhs.birthday){...}


System p3;
p3 = p1; // 编译器为System类创建拷贝赋值操作符
// 拷贝赋值操作符返回值是X&也是有原因的
System& operator=(const System& rhs) {
    name = rhs.name;
    birthday = rhs.birthday; // 调用Date中的拷贝赋值操作符
}

可以看到, 在处理一般的类(不涉及管理如指针这样的资源的类)的时候, 编译器为这个类创建的三个特殊的成员函数是足够完成任务的.

三个函数全部定义

而当我们的类设计到管理一个资源的时候, 我们有责任为自己的类定义全部的这三个函数.

还是以System类为例子, 我们将name的类型由string换成char*, 这样的话, 我们就应该为这个类编写自己的三个特殊成员函数.

class System {
public:
    System(const char* n, const Date& birth) {
        name = new char[strlen(n)+1];
        strcpy(name, n);
        birthday = birth;
    }

    ~System() {
        delete[] name;
    }

    // 仅仅有上面的两个是不够的
    // 我们还需要定义下面两个特殊成员函数
    System(const System& rhs) {
        name = new char[strlen(rhs.name)+1];
        strcpy(name, rhs.name);
        birthday = rhs.birthday;
    }

    System& operator=(const System& rhs) {
        // 处理自我赋值
        if (this != &rhs) {
            // 循环里面的做法也是有讲究的
            // 具体分析请参考effective c++条款11
            char* oldname = name;
            name = new char[strlen(rhs.name)+1];
            strcpy(name, rhs.name);
            birthday = rhs.birthday;
            delete [] oldname;
        }
        return *this;
    }

private:
    char* name;
    Date birthday;
};

如代码中所示, 如果要管理如指针, 或者类似使用built-in的assignment operator不能够正确完成复制任务的资源的时候, 我们必须要为自己的类实现这三个特殊的成员函数: 1. 析构函数, 负责资源的释放; 2. 赋值拷贝函数, 负责类的物件的拷贝构造操作; 3. 赋值拷贝操作符, 负责类的物件的赋值操作.

通常来说, 如果当我们需要为类明确定义析构函数的时候, 我们就应该反应过来, 我们应该为类明确定义这三个特殊的成员函数. 而当我们的类需要管理一种资源的时候, 也应该明确地位类定义这三个成员函数.

小结

除了rule of three之外, 在实现这条规则的时候, 我们可以发现, 其实在拷贝构造函数和拷贝赋值操作符的代码当中是有很多的code duplication的, 而且上面的实现还有有可能抛出异常的. 所以在第二篇, 介绍解决上面的问题的方法, 就是copy-and-swap idiom.

太长了, 还是分两篇写吧(=.=)

参考文献

  1. C++98 standard
  2. effective c++, Scott Meyers, 条款5, 10, 11, 13
  3. StackOverflow, What is The Rule of Three?