问题

已知链表节点定义如下：

class ListNode {
public:
    int val;
    ListNode* next;
public:
    ListNode(int v, ListNode* n = NULL): val(v), next(n) {}
};

如何用 C++ 初始化出指定链表，如：1->2->3？

一般做法

直接法，这种方法遇到长的链表会导致一行长度过长：

1	ListNode* list = new ListNode(1, new ListNode(2, new ListNode(3)));

分步法，缩短列宽，缺点是初始化长度为n的链表需要n行代码：

1
2
3

ListNode* list = new ListNode(1);
ListNode* node2 = list->next = new ListNode(2);
node2->next = new ListNode(3);

循环法，最通用的做法：

int values[] = {1, 2, 3};
ListNode* list = new ListNode(values[0]);
ListNode* cur = list;
for (int i = 1; i < 3; ++i) {
    cur->next = new ListNode(values[i]);
    cur = cur->next;
}

可以看出，这3种方法都比较啰嗦，如果使用 C++11 的列表初始化，可以简化很多。

列表list 初始化initialization

列表初始化是C++11在旧语法的基础上提出的新语法。其提出是为了解决C++混乱的初始化语法：

int i = 1;              // C风格的初始化
int i(1);               // 构造初始化，与上面等价
int arr[] = {1, 2, 3};  // 花括号初始化，用于初始化数组或者结构体
struct { int i; char c; } a = {1, 'c'};

有了列表初始化，上面的初始化可以统一写成：

1
2
3

int i {1};
int arr[] {1, 2, 3};
struct { int i; char c; } a {1, 'a'};

STL 中的容器也支持这种初始化方法：

1 2	std::vector<int> v {1, 2, 3}; std::map<char, int> m {{'a', 1}, {'b', 2}};

这些容器是通过添加一个以std::initializer_list为参数的构造函数实现的。

以std::vector为例，其大致实现代码如下：

template <typename T>
class vector {
    ......
    vector(initializer_list<T> lst) {
        // lst是一个容器，可以通过迭代器遍历出其中的元素，用于初始化vector
        ...
    }
    ......
};

初始化链表

现在，让我们再来看下开头的问题。如何利用列表初始化语法初始化链表呢？

可以直接这样做：

1	ListNode* list {1, new ListNode {2, new ListNode {3}}};

但是这样，跟上面的方法 1 几乎是一样的，初始化语句中有许多冗余的new ListNode。

如何去掉new ListNode呢？

可以使用一个辅助类ListBuilder把new ListNode“包”起来：

struct ListBuilder {
    int v;
    ListNode* p;
    ListBuilder(ListNode* p = nullptr): p(p) {}
    ListBuilder(int d, ListBuilder b = ListBuilder())
        : p(new ListNode(d, b.p)) {}
    operator ListNode* () const {
        return p;
    }
};

用法是这样：

1	ListNode* list = ListBuilder {1, {2, {3}}};

当编译器遇到 ListBuilder {1, {2, {3}}} 时，认识到这是一个列表初始化，
会在 ListBuilder的构造函数中寻找匹配函数签名(int, ...)的函数。

ListBuilder(int d, ListBuilder b = ListBuilder()) 被匹配到。

{1, {2, {3}}}中的1被用于初始化参数d,{2, {3}}被用于初始化参数b。

因为b也是ListBuilder，上述过程会递归地进行下去，直到遇到{3}，递归终止。

最后，ListBuilder {1, {2, {3}}}初始化完成，得到一个ListBuilder实例，将它赋值给ListNode* list。

为了实现从ListBuilder到ListNode的转换，需要类型操作符重载：

1
2
3

operator ListNode* () const {
    return p;
}

练习

已知二叉树节点定义如下：

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
public:
    TreeNode(int x, TreeNode* l = nullptr, TreeNode* r = nullptr)
        : val(x), left(l), right(r) {}
};

如何用 C++ 初始化出二叉树？