Jason Pan

使用 initializer_list & variant 优雅地构造 NestedInteger

潘忠显 / 2021-09-14


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

本文介绍如何使用 C++ 优雅的实现 NestedInteger 这个类,其中涉及到使用 std::initializer_liststd::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 个变量定义:

参考资料