c++ - 使用对嵌入的双端队列成员的引用初始化的树元素会为此导致 nullptr

Question

following program尝试创建由对 std::deque 的引用组成的节点树元素。

#include <deque>

struct Node;
using Pool = std::deque<Node>;

struct Node
{
    Node(int d, Pool& pool)
        : level{d}
        , l{d > 0 ? pool.emplace_back(d - 1, pool) : *this}
        , r{d > 0 ? pool.emplace_back(d - 1, pool) : *this}
    {
    }

    int level;
    const Node& l;
    const Node& r;

    int check() const
    {
        if(!(&l == this))
            return l.check() + 1 + r.check();
        else
            return 1;
    }
};

int main()
{
    int depth{2};
    Pool pool;
    Node c(depth, pool);
    return c.check()==7 ? 0 : 1;
}

它创建了正确数量的元素，但并非所有引用都初始化为放置的元素和 level未为高于 0 的级别设置变量.

最后，程序由于this而失败成为 nullptr当check()函数被执行。

如何正确初始化引用？

Answer 1

概括

问题是您正在调用 emplace_back在 deque来自 emplace_back 调用的构造函数.当其中一种方法已经在进行中时，您不得修改容器。这是由 section [reentrancy] of the C++ standard 禁止的(感谢@T.C.)。

Except where explicitly specified in this International Standard, it is implementation-defined which functions in the C++ standard library may be recursively reentered.

要了解为什么不允许这种事情，这里有一个更明显的例子。想象一下调用 std::vector::push_back()来自 std::vector 正在调用的复制构造函数在为另一个重新分配期间 push_back()进行中。重新分配的工作原理是在释放旧内存之前分配新的内存块，因此您暂时会得到三个 block ，并且最多两个新元素可能会以不同的"new" block 结束。

解决方案概述

从根本上说，问题是两件事的结合:

std::deque<Node>::emplace_back()正在被 Node::Node(...) 调用

std::deque<Node>::emplace_back()正在调用 Node::Node(...)

结合这两个问题，std::deque::emplace_back()最终会调用自己。因此，解决方案是修复这两件事之一。

具体解决方案

使用包装函数，我称之为 make() . make()调用自身，并调用 emplace_back() (它调用 Node::Node(...) )，但是 Node::Node(...)从不打电话 emplace_back() .

这是(1)思想的变体。它还使用包装函数，但它使用引用成员(如原始问题)，因此它必须首先构造子节点。

这解决了另一个问题:Node::Node(...)允许 emplace_back() ，但这一次 emplace_back()不允许构造Node对象。我这样做的方法是使用指向 Node 的指针的双端队列。对象。然而，正如所写的，这个解决方案并不是异常安全的，我认为它比其他解决方案丑陋得多。

这本质上是@AMA 的巧妙想法:我再次使用包装函数，但这次包装函数被称为 Node::Node(int, Pool&) !关键是，这会调用自己和 emplace_back() .但是emplace_back()调用不同的构造函数，即复制构造函数，我手动编写它以避免它复制对临时对象的引用，并且从不回调 emplace_back() .

奖金解决方案!这里的部分复杂性是由于使用 *this作为哨兵值。将指针与 nullptr 一起使用更传统。此解决方案执行此操作(因此使用像解决方案 1 那样的指针成员)，并首先创建子节点(如解决方案 2)，作为奖励，该创建是完全非侵入性的。

解决方案 1:包装函数和指针

#include <deque>

struct Node;
using Pool = std::deque<Node>;

struct Node
{
    Node(int d)
        : level{d}, l{this}, r{this}
    {
    }
    static Node& make(int d, Pool& pool)
    {
        pool.emplace_back(d);
        Node& result = pool.back();
        if (d > 0) {
            result.l = &make(d - 1, pool);
            result.r = &make(d - 1, pool);
        }
        return result;
    }

    int level;
    const Node* l;
    const Node* r;

    int check() const
    {
        if(l != this)
            return l->check() + 1 + r->check();
        else
            return 1;
    }
};

int main()
{
    int depth{2};
    Pool pool;
    Node& c = Node::make(depth, pool);
    return c.check()==7 ? 0 : 1;
}

解决方案 2:带有引用成员的包装函数

注意:这会改变 deque 中元素的顺序: 子元素首先插入，所以它们现在比它们的父元素早。

#include <deque>

struct Node;
using Pool = std::deque<Node>;

struct Node
{
    static Node& make(int d, Pool& pool)
    {
        Node* l = nullptr;
        Node* r = nullptr;
        if (d > 0) {
            l = &make(d - 1, pool);
            r = &make(d - 1, pool);
        }
        pool.emplace_back(d, l, r);
        return pool.back();
    }

    Node(int d, Node* l_ptr, Node* r_ptr)
        : level{d}
        , l{l_ptr ? *l_ptr : *this}
        , r{r_ptr ? *r_ptr : *this}
    {
    }

    int level;
    const Node& l;
    const Node& r;

    int check() const
    {
        if(!(&l == this))
            return l.check() + 1 + r.check();
        else
            return 1;
    }
};

int main()
{
    int depth{2};
    Pool pool;
    Node& c = Node::make(depth, pool);
    return c.check()==7 ? 0 : 1;
}

解决方案3:容器中的指针

这使用引用，并避免使用辅助函数，并以正确的顺序将元素存储在池中。在目前的形式中，它不是异常(exception)安全的，例如如果调用 new为 r抛出异常(例如 std::bad_alloc )然后 l不会被释放。这将很难解决，最终我认为其他解决方案会更简洁。

#include <deque>
#include <memory>

struct Node;
using Pool = std::deque<std::unique_ptr<const Node>>;

struct Node
{
    Node(int d, Pool& pool)
        : level{d}
        , l{d > 0 ? *new Node(d - 1, pool) : *this}
        , r{d > 0 ? *new Node(d - 1, pool) : *this}
    {
        if (&l != this) {
            pool.emplace_back(&l);
        }
        if (&r != this) {
            pool.emplace_back(&r);
        }
    }

    int level;
    const Node& l;
    const Node& r;

    int check() const
    {
        if(!(&l == this))
            return l.check() + 1 + r.check();
        else
            return 1;
    }
};

int main()
{
    int depth{2};
    Pool pool;
    Node c(depth, pool);
    return c.check()==7 ? 0 : 1;
}

解决方案4:两个构造函数

这可以说是最简单的解决方案，但我认为与解决方案 1 和解决方案 2 不同，它不保留对临时对象的任何悬空引用并不完全明显。

#include <deque>

struct Node;
using Pool = std::deque<Node>;

struct Node
{
    Node(int d, Pool& pool)
        : level{d}
        , l{d > 0 ? pool.emplace_back(Node(d - 1, pool)) : *this}
        , r{d > 0 ? pool.emplace_back(Node(d - 1, pool)) : *this}
    {
    }

    Node(const Node& other)
        : level{other.level}
        , l{&other.l == &other ? *this : other.l}
        , r{&other.r == &other ? *this : other.r}
    {
    }

    int level;
    const Node& l;
    const Node& r;

    int check() const
    {
        if(!(&l == this))
            return l.check() + 1 + r.check();
        else
            return 1;
    }
};

奖励解决方案:指针、包装函数和 nullptr

最简单的解决方案是，如果您准备使用指针，请先构造子节点，然后使用 nullptr而不是 this作为哨兵值。请注意 Node现在与 Pool 完全分离和 make() .

#include <deque>

struct Node {
    int level;
    const Node* const l;
    const Node* const r;

    Node(int level, const Node* l, const Node* r):
        level(level), l(l), r(r)
    {
    }

    int check() const
    {
        if(l)
            return l->check() + 1 + r->check();
        else
            return 1;
    }
};

using Pool = std::deque<Node>;

Node* make(int d, Pool& pool)
{
    Node* l = d > 0 ? make(d - 1, pool) : nullptr;
    Node* r = d > 0 ? make(d - 1, pool) : nullptr;
    return &pool.emplace_back(d, l, r);
}

解决方案图