Tree elements initialized with references to emplaced deque members results in nullptr for this

Question

The following program attempts to create a tree of nodes consisting of references to std::deque elements.

#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;
}

It creates the correct number of elements, but not all references are initialized to the emplaced elements and the level variable is not set for levels higher than 0.

Finally, program fails due to this being a nullptr when the check() function is executed.

How can the references be correctly initialized?

Answer 1

Summary

The problem is that you're calling emplace_back on the deque from a constructor being called by emplace_back. You are not allowed to modify a container while one of its methods is already in progress. This is prohibited by section [reentrancy] of the C++ standard (thanks to @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.

To see why this sort of thing isn't allowed, here is a more obvious example. Imagine calling std::vector::push_back() from a copy constructor which is being invoked by std::vector during reallocation for another push_back() in progress. Reallocation works by allocating the new chunk of memory before freeing the old one, so you'd temporarily end up with three chunks, and at best the two new elements might end up in different "new" chunks.

Solution overview

Fundamentally, the problem is the combination of two things:

• std::deque<Node>::emplace_back() is being called by Node::Node(...)
• std::deque<Node>::emplace_back() is making a call to Node::Node(...)

Combining these two problems, std::deque::emplace_back() ends up calling itself. The solution is therefore to fix one of these two things.

Specific solutions

1. Use a wrapper function, which I call make(). make() calls itself, and calls emplace_back() (which calls Node::Node(...)), but Node::Node(...) never calls emplace_back().
2. This is a variation on the idea of (1). It also uses a wrapper function, but it uses reference members (like the original question) so it has to construct the child nodes first.
3. This fixes the other problem: Node::Node(...) is allowed to emplace_back(), but this time emplace_back() is not allowed to construct Node objects. The way I do this is that I use a deque of pointers to Node objects. However, as written this solution is not exception safe, and I consider it much uglier than the other solutions.
4. This is essentially @AMA's ingenious idea: I again use a wrapper function, but this time the wrapper function is called Node::Node(int, Pool&)! The point is, this calls itself and emplace_back(). But emplace_back() calls a different constructor, namely the copy constructor, which I write manually to avoid it copying references to temporaries, and which never calls back to emplace_back().
5. Bonus solution! Part of the complexity here is due to using *this as a sentinel value. Using pointers with nullptr is more conventional. This solution does this (so uses pointer members like solution 1), and creates the child nodes first (like solution 2), and as a bonus the creation is totally non-invasive.

Solution 1: Wrapper function and pointers

#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;
}

Solution 2: Wrapper function with reference members

Note: this changes the order of elements in the deque: child elements are inserted first, so they are now earlier than their parents.

#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;
}

Solution 3: pointers in the container

This uses references, and avoids an auxiliary function, and stores elements in the pool in the correct order. In its current form it is NOT EXCEPTION SAFE e.g. if the call to new for r throws an exception (e.g. std::bad_alloc) then l will not be freed. This would be tricky to sort out, and ultimately I think the other solutions would be neater.

#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;
}

Solution 4: Two constructors

This is arguably the simplest solution, but I would argue that it's not completely obvious that it doesn't keep any dangling references to temporary objects, unlike solution 1 and solution 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;
    }
};

Bonus solution: Pointers, wrapper function and nullptr

The simplest solution is if you're prepared to use pointers, construct child nodes first, and use nullptr instead of this as a sentinel value. Note that Node is now cleanly separated from Pool and 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);
}

Diagram of solutions

Answer 2

A solution inspired from solutions 2 and 4 from Arthur Tacca answer (if you like it, give a +1 to Arthur; if you don't like it: it's my fault).

This solution use a second constructor (as solution 4) but call it directly (as delegating constructor) an a static method (inspired by solution 2) used to create the childs of the new node.

Remain unaltered the main point from Arthur: it's necessary to avoid a emplace_back() that call itself and insert the child nodes before the father.

Works also with c++11

#include <deque>

struct Node;

using Pool = std::deque<Node>;

struct Node
 {
   Node (int d, Pool & pool, Node const * pl, Node const * pr)
      : level { d }, l { pl ? *pl : *this }, r { pr ? *pr : *this }
    { }

   static Node const * getChild (int d, Pool & pool)
    {
      Node const * ret { nullptr };

      if ( d-- > 0 )
       {
         pool.emplace_back(d, pool, getChild(d, pool), getChild(d, pool));

         ret = & pool.back();
       }

      return ret;
    }

   Node (int d, Pool& pool)
      : Node { d, pool, getChild(d, pool), getChild(d, pool) }
    { }

   int level;

   Node const & l;
   Node const & r;

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

int main ()
 {
   int depth{2};
   Pool pool;
   Node c(depth, pool);

   return c.check()==7 ? 0 : 1;
 }