问题的引入

最近有若干同学和我讨论在实现 C++ vector 容器的时候如何实例化一个没有默认构造函数的类。比如下面的代码:

#include <cstddef>

template <class T>
class vector {
    size_t capacity, size;
    T *data;
public:
    vector() :
        capacity(10), // for example
        size(0),
        data(new T[capacity]) {
    }

    ~vector() {
        delete [] data;
    }
};

struct Point {
    int x, y;
    Point(int a, int b): x(a), y(b) {}
};

int main() {
    vector<int> a;
    vector<Point> b;
}

在实例化 vector<int> 的时候不会有问题,然而当实例化 vector<Point> 的时候就会出错了

placement_new.cc:11:18: error: no matching constructor for initialization of 'Point'
        data(new T[capacity]) {
                 ^
placement_new.cc:26:19: note: in instantiation of member function 'vector<Point>::vector' requested here
    vector<Point> b;

猜想

这个编译错误还是很容易可以看出来是由于 Point 类型没有默认构造函数,所以导致无法 new [] T

最开始我想到的解决方法是 将 T *data 替换为 T **data,这样由于 T* 类型是可以直接被 new 出来的,所以构造函数不会出错;当 push_back(value) 的时候,再令 data[back] = new T(value)

然而这样有个问题,浪费了大量的空间,也就是多占用了 sizeof(T*) * size 的空间。

怎么办呢?翻了下 Google 和 SGI STL 的代码我才发现原来 C++ 还有一个非常少见的语法。

解决方案

为什么 new T[size] 会报错呢?因为这句话实际上试图做两件事:

  • 申请一段长度为 sizeof(T) * size 的内存
  • T() 即默认构造函数构造这 size 个对象

既然 T 没有默认构造函数,而在构造 Array 的时候其实只是想要一段连续的内存池而已,那为什么我们不把分配内存和构造对象分开呢?

分配内存我们可以沿用 C 的那一套:

#include <cstdlib> // for malloc
T *data = reinterpret_cast<T*>(malloc(sizeof(T) * capacity));

然后在 push_back(value) 的时候怎么办呢?C++ 有一个叫做 placement new 的语法,可以给定一个指针,在这个指针的位置调用某个类型的构造函数:

#include <new> // for placement new
T* node = new (static_cast<void*>(&data[size])) T(value);

&data[size] 就是我们分配的连续空间的第一个可用空间,也就是我们要把元素放置的位置。T(value) 就是用 value 复制构造一个新的 T 对象,因为用的是复制构造函数,所以就绕开了默认构造函数这个问题。

析构

看起来问题已经圆满地解决了。然而,析构怎么办?delete [] data 吗?这段空间根本不是 new 出来的,和 delete 有什么关系呢?那直接用 free(data) 吗?

嗯,这样确实回收了 data。然而,原先在 data 里面的那些 T 类型的元素,他们如果也动态申请了内存,这么做并不能使它们释放内存。所以说我们需要手动调用析构函数。在 pop_back() 这样的函数中,我们就需要顺带把元素析构掉:

void pop_back() {
    data[size--].~T();
}

然后当 vector 要被析构的时候,我们先保证所有元素都已经被析构了,然后再释放内存。

~vector() {
    while (size) pop_back();
    free(data);
}

好了,这样问题就解决了。

完整示例

#include <new>
#include <cstddef>
#include <cstdlib>

template <class T>
class vector {
    size_t capacity, size;
    T *data;
public:
    vector() :
        capacity(10), // for example
        size(0),
        data(static_cast<T*>(malloc(sizeof(T) * capacity))) {
    }

    void push_back(const T& value) {
        void* ptr = data + (size++);
        new (ptr) T(value);
    }

    void pop_back() {
        data[size--].~T();
    }

    ~vector() {
        while (size) pop_back();
        free(data);
    }
};

struct Point {
    int x, y;
    Point(int a, int b): x(a), y(b) {}
};

int main() {
    vector<int> a;
    vector<Point> b;
}

后记

实际上,placement new 这个语法个人感觉十分黑暗,并且官方是强烈推荐尽量避免使用这个语法,除非你在和一些底层的数据打交道(比如编写容器),并且知道自己在做什么。因为无论是在编译器还是运行期,使用这个语法导致了错误,都是无法检测的。而且使用这个语法还要考虑内存对齐的问题,官方的态度是:如果你连内存对齐是什么都不知道(比如我),你最好还是不用这个语法。所以,要不是我看到了 SGI STL 确实是这么写的,我肯定不敢用。

If your Fred class needs to be aligned on a 4 byte boundary but you supplied a location that isn’t properly aligned, you can have a serious disaster on your hands (if you don’t know what “alignment” means, please don’t use the placement new syntax). You have been warned.

经过这个事情之后,我愈发觉得 C++ 的坑好多,愈发觉得 C++ 好难,愈发觉得 C++ 博大精深。我开始觉得是不是让初学者学 C++ 完全就是个错误的选择。最近看其他同学写数据结构课的大作业,我发现有许多地方都是在纠结 C++ 语法/语言的问题,而不是数据结构本身。而且实际上,上课的时候并不会告诉你这些坑在哪,设计模式是怎样的,规范是怎样要求的。

这几天 Rust 1.0 终于出了,据说许多人认为可以取代 C++ 的地位。我还没有了解过 Rust ,不过从我已有的一点点信息,我觉得这个完全抛弃历史包袱、和 C++ 高度兼容、支持底层控制、支持函数式编程、高性能的 Rust 看起来非常棒。虽然最近 C++ 也开始了进一步发展,可是我觉得 C++ 的发展只是让这个语言越来越复杂。或许有一天,C++ 真的会退出历史舞台,成为时代的眼泪。或许没过多久, Rust 就会在业内流行起来。然而,不知道这些新兴的语言什么时候会进入课堂呢?

参考资料