问题的引入

最近有若干同学和我讨论在实现 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 就会在业内流行起来。然而，不知道这些新兴的语言什么时候会进入课堂呢？

参考资料