初始化的树元素引用了对deque成员的引用会导致nullptr

Question

在下面的程序试图建立一个由以引用的节点树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.当其中一个方法正在进行中时,不允许修改容器.这是C++标准的[reentrancy]部分所禁止的(感谢@TC).

除非在本国际标准中明确指定,否则它是实现定义的,可以递归地重新输入C++标准库中的函数.

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

解决方案概述

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

• std::deque<Node>::emplace_back()被调用的 Node::Node(...)
• std::deque<Node>::emplace_back()打电话给 Node::Node(...)

结合这两个问题,std::deque::emplace_back()最终会自我调用.因此,解决方案是解决这两件事中的一件.

具体方案

1. 使用我调用的包装函数make().make()调用自己,调用emplace_back()(调用Node::Node(...)),但从Node::Node(...)不调用emplace_back().
2. 这是对(1)的思想的变化.它还使用包装函数,但它使用引用成员(如原始问题),因此必须首先构造子节点.
3. 这解决了另一个问题:Node::Node(...)允许emplace_back(),但这次emplace_back()不允许构造Node对象.我这样做的方式是,我使用的双端队列指针到Node对象.但是,正如所写,这个解决方案不是例外安全,我认为它比其他解决方案更加丑陋.
4. 这基本上是@ AMA的巧妙构思:我再次使用包装函数,但这次调用了包装函数Node::Node(int, Pool&)!关键是,这称自己和emplace_back().但是emplace_back()调用一个不同的构造函数,即复制构造函数,我手动编写它以避免它复制对temporaries的引用,并且从不回调emplace_back().
5. 奖金解决方案!这里的部分复杂性是由于使用了*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:容器中的指针

这使用引用,并避免使用辅助功能,并以正确的顺序存储池中的元素.在其当前形式中,它不是例外安全,例如,如果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);
}

解决方案图