Alguns dias atrás, tentei escrever uma implementação de árvore básica no mesmo estilo dos contêineres STL. Agora eu estou tentando usá-lo no meu código, mas duas coisas não parecem funcionar que funcionam com umstd::vector. Ou seja, usando tipos incompletos e usando tipos abstratos.

Como faço para corrigir a implementação da minha árvore para obter essa funcionalidade? Eu tentei condensar meu código um pouco para mostrar principalmente as partes relevantes.

test.cpp

#include "util/tree.hpp"
#include <vector>

struct IncompleteType;

class AbstractType
{
public:
    virtual void do_something() = 0;
};

class Test
{
public:
    Test() = default;
private:
    tree<IncompleteType>        incompleteTree;
    std::vector<IncompleteType> incompleteVector;
    tree<AbstractType>          abstractTree;
    std::vector<AbstractType>   abstractVector;
};

struct IncompleteType
{
    int completed;
};

util / tree.hpp (condensado)

template <class T, class Alloc = std::allocator<T> >
class tree
{
public:
    typedef Alloc                           allocator_type;
    typedef typename Alloc::value_type      value_type;
    typedef value_type&                     reference;
    typedef const value_type&               const_reference;
    typedef typename Alloc::difference_type difference_type;
    typedef typename Alloc::size_type       size_type;

    class node
    {
    public:
        value_type data;

        const std::vector<std::unique_ptr<node> >& get_children() const { return children_; }
        node*                                      get_parent() const { return parent_; }
        node*                                      get_right() const { return right_; }

        bool operator== (const node&) const;

        size_t size() const;
        bool   has_ancestor(const node* n) const { return parent_ != nullptr && (parent_ == n || parent_->has_ancestor(n)); }

        friend class tree;

    protected:
        std::vector<std::unique_ptr<node> > children_;
        node*                               parent_ = nullptr;
        node*                               right_  = nullptr;

        node() = default;
        node(value_type data) : data(data) {}
    };

    class iterator
    {
        // ...
    };

    class const_iterator
    {
        // ...
    };

    tree() = default;
    tree(const tree&) = default;

    tree& operator= (const tree&) = default;

    // iterators begin(), etc ...

    // operators ...

    // size(), empty(), ...

    node*       get_root() { return &root_; }
    const node* get_root() const { return &root_; }

    node* add_new_node(const value_type& val) { return add_new_node_to(&root_, val); }
    node* add_new_node_to(node*, const value_type&);
    bool  prune_node(node*&);

private:
    node root_;
};

Ao compilar comg++ -O3 -Wall -Wextra -pedantic -std=c++11 test.cpp, Recebo a seguinte saída:

In file included from test.cpp:1:0:
util/tree.hpp: In instantiation of ‘class tree<IncompleteType>::node’:
util/tree.hpp:138:7:   required from ‘class tree<IncompleteType>’
test.cpp:19:30:   required from here
util/tree.hpp:28:14: error: ‘tree<T, Alloc>::node::data’ has incomplete type
   value_type data;
              ^
test.cpp:6:8: error: forward declaration of ‘tree<IncompleteType>::value_type {aka struct IncompleteType}’
 struct IncompleteType;
        ^
In file included from test.cpp:1:0:
util/tree.hpp: In instantiation of ‘class tree<AbstractType>::node’:
util/tree.hpp:138:7:   required from ‘class tree<AbstractType>’
test.cpp:21:30:   required from here
util/tree.hpp:47:3: error: cannot allocate an object of abstract type ‘AbstractType’
   node(value_type data) : data(data) {}
   ^
test.cpp:8:7: note:   because the following virtual functions are pure within ‘AbstractType’:
 class AbstractType
       ^
test.cpp:11:15: note:   virtual void AbstractType::do_something()
  virtual void do_something() = 0;
               ^
In file included from test.cpp:1:0:
util/tree.hpp:28:14: error: cannot declare field ‘tree<AbstractType>::node::data’ to be of abstract type ‘AbstractType’
   value_type data;
              ^
test.cpp:8:7: note:   since type ‘AbstractType’ has pure virtual functions
 class AbstractType
       ^

Minha árvore tem problemas com esses tipos, enquantostd::vector não. Eu posso ver que isso tem a ver com a forma como eu armazeno os dados dentro dos nós, mas estou desenhando um espaço em branco ao tentar chegar ao caminho certo para fazê-lo ... Como faço para armazenar coisas se não do tipovalue_type?