Jason Pan

使用 initializer_list & variant 优雅地构造 NestedInteger

黄杰 / 2021-09-14

之前文章提到，我个人在刷 LeetCode 时，会利用自己搭建的框架，编写测试用例。在刷到题目#341时，需要构造一个 NestedInteger 的类。简单的讲，它有以下特点：

本文介绍如何使用 C++ 优雅的实现 NestedInteger 这个类，其中涉及到使用 std::initializer_list 和 std::variant，最后着重介绍了 initializer_list 的各种情形下的推导细节。

一、直观实现

根据上边的描述，直观地 NestedInteger 实现可以封装整数和向量两种类型，再额外使用一个枚举类型来标记对象表示的是何种类型。因为同一时间只可能是同一种类型，可以利用 union，但是 union 对其中的类型有严苛的限制，这里直接使用两个不同类型的成员变量存储：

class NestedInteger {
 public:
  // ... constructor/destructor and get/set APIs  
 private:
  enum { INT, VECTOR } type_;
  int val_int_;
  std::vector<NestedInteger> val_vec_;
};

二、使用 std::initializer_list

我们知道 C++ 11 开始支持 列表初始化(List Initialization)，比如因为 std::vector 有这样一个构造函数：

template<typename value_type, typename allocator_type >
vector(initializer_list<value_type> __l,
       const allocator_type& __a = allocator_type());

因此，我们可以方便的在构造向量的时候，直接传入向量内容。

// c++11 initializer list syntax:
std::vector<std::string> words{"hello", "world"};

可不可以 {1, {2, {3, 4}}, 5} 去构造我们定义的 NestedInteger 呢？ 答案是肯定的。

首先，我们要考虑输入初始化列表是 {2} 的情况，直接接收一个整数作为参数的构造函数可以支持[隐藏细节1]：

NestedInteger(int i) : type_(INT), val_int_(i) {}

其次，我们考虑如果输入初始化列表是 {1, 2} 则意味着需要产生一个 NestedInteger，而其中的 vector<NestedInteger> 存储的是储存着保存 Integer 值的类型。[隐藏细节2] 因此，这里对应的构造函数结构应该是：

NestedInteger(std::initializer_list<NestedInteger> ni) {
  for (auto it = ni.begin(); it != ni.end(); it++) {
    val_vec_.push_back(*it);
  }
}

最后，上边的构造函数还能够接收 {1, {2, {3, 4}}, 5} 形式的非初始化列表。

这里的首先-其次-最后，隐藏了关于初始化列表的许多一些细节，会在最后一部分再做详细讨论。

三、使用 std::variant

之前的实现，一共是使用了三个成员变量：

直观上，两个存储变量的变量可以存储在一个 union 中，但是 union 对属性类型有非常严格的要求 。

从 C++ 17 开始，有一个 std::variant 类模板，表示一个类型安全的联合体。 std::variant 的一个实例在任意时刻要么保有其一个可选类型之一的值，要么在错误情况下无值。详见 cppreference 说明

通过一个 std::variant<int, std::vector<NestedInteger>> 类型的成员变量，就可以替代上述三个变量。具体的：

四、最终代码

#include <cassert>
#include <variant>
#include <vector>
class NestedInteger final {
 public:
  NestedInteger(int i) : value(i) {}
  NestedInteger(std::initializer_list<NestedInteger> ni) : value(ni) {}

  inline bool isInteger() const { return std::holds_alternative<int>(value); }
  inline int getInteger() const {
    assert(std::holds_alternative<int>(value));
    return std::get<int>(value);
  }

  inline const std::vector<NestedInteger>& getList() const {
    assert(std::holds_alternative<std::vector<NestedInteger>>(value));
    return std::get<std::vector<NestedInteger>>(value);
  }

 private:
  std::variant<int, std::vector<NestedInteger>> value;
};

TL;DR 深入理解初始化列表

通过提出几个问题并对其进行解释，来深入的理解一下初始化列表的底层逻辑。

1. 为什么定义了 NestedInteger(int i) 就能使用 ni{1}

其实定义了 NestedInteger(int i) 之后，直接能使用的表达式是：

NestedInteger ni(1);
auto nip = new NestedInteger(2);

而 NestedInteger ni{1}; 是会先找 NestedInteger(initializer_list) 的定义，如果找不到，会将花括号中的内容展开，作为参数，寻找对应的构造函数。

class C {
 public:
  C(int i) { std::cout << "C(int)" << std::endl; }

  C(std::initializer_list<C> i) {
    std::cout << "C(initializer_list)" << std::endl;
  }
};

int main() {
  C c1(1);
  std::cout << "---" << std::endl;
  C c2{1};
}

输出：

C(int)
---
C(int)
C(initializer_list)

2. 为什么不能使用自动推导类型的模板

这个问题描述的更清楚一点就是，下边的构造函数声明/定义：

NestedInteger(std::initializer_list<NestedInteger> ni);

如果改写成：

template<typename T>
NestedInteger(std::initializer_list<T> ni);

针对以下若干种场景：

  NestedInteger ni1{1};
  NestedInteger ni2{1, 2, 3}; 
  NestedInteger ni3{{1}, 2, 3}; 
  NestedInteger ni4{{1, 2, 3}};
  NestedInteger ni5{{1, 2, 3}, {4, 5, 6, 7}};

会发生：

3. 为什么可以使用指定元素的构造函数

当使用 NestedInteger(std::initializer_list<NestedInteger> ni); 声明/定义时，同样考虑之前的 5 个变量定义：

参考资料