使用 unique_ptrs 的基本前向列表

Question

作为学习 C++ 的练习，我想使用原始指针和 unique_ptrs 构建自己的前向列表。使用原始指针，我有：

struct node_raw {
    node_raw(int data_, node_raw *next_) : data(data_), next(next_) {}
    int data;
    node_raw *next;
};

然后我可以写这个

int main() {
    node_raw r1{1, nullptr};
    node_raw r2{2, &r1};
    node_raw r3{3, &r2};
}

获取转发列表：r3 -> r2 -> r1。

现在我想使用 unique_ptrs 做同样的事情。

struct node_unique {
    node_unique(int data_, std::unique_ptr<node_unique> next_) 
        : data(data_), next(std::move(next_)) {}
    int data;
    std::unique_ptr<node_unique> next;
};

这是我到目前为止的客户端代码：

int main() {
    node_unique u1{1, nullptr};
    node_unique u2{2, std::make_unique<node_unique>(std::move(u1))};
    node_unique u3{3, std::make_unique<node_unique>(std::move(u2))};
}

这给出了u3.next->data = 2，所以它似乎有效。但这是对的吗？为什么我需要std::move两次才能创建一个新节点？u1.data是不是因为已经移走了，所以现在查询无效了？基本上，使用 unique_ptrs 实现最小前向列表的规范方法是什么？

Answer 1

为什么我需要 std::move 两次才能创建新节点？

您无法复制，node_unique因为它因std::unique_ptr成员而隐式删除了复制构造函数。

现在查询 u1.data 是否无效，因为它已被移出？

不会。隐式生成的移动构造函数将复制该成员。int读取从中复制的成员并非无效。

但这是对的吗？

节点类本身并没有什么大问题¹，但您使用它的方式可能会产生误导。u1并且u2不属于根为 的列表的一部分u3。列表节点是移出节点u1和的浅拷贝u2。

您不一定需要这些变量；由于列表元素是动态的，因此您可以直接创建它们：

node_unique root (
    3,
    std::make_unique<node_unique>(
        2,
        std::make_unique<node_unique>(
            1,
            nullptr
        )
    )
);

基本上，使用 unique_ptrs 实现最小前向列表的规范方法是什么？

“最小”与您的要求相关。您可以通过删除构造函数以使节点成为聚合来使其更加最小。

我不会说有一种“规范”的方式来实现转发列表，但预计它会满足Container. 然而，这并不是最小的。

^{1除了析构函数具有线性递归深度这一事实之外，正如}Remy Lebeau指出的那样，这会导致中等大小的列表发生堆栈溢出。

您应该实现一个自定义析构函数来迭代地销毁节点。这需要一些思考来防止智能指针析构函数深入递归。