如何修复 STL 样式容器以容纳不完整或抽象类型？

几天前，我尝试以与 STL 容器相同的风格编写一个基本的树实现。现在我尝试在我的代码中使用它，但是有两件事似乎不起作用，但可以说std::vector。即，使用不完整类型和使用抽象类型。

如何修复我的树实现以获得此功能？我尝试稍微压缩一下我的代码，主要向您​​展示相关部分。

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

实用程序/tree.hpp（浓缩）

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

编译时使用g++ -O3 -Wall -Wextra -pedantic -std=c++11 test.cpp，我得到以下输出：

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
       ^

我的树在这些类型上遇到了麻烦，而std::vector才不是。我可以看到这与我如何在节点内存储数据有关，但是当我试图想出正确的方法来做到这一点时，我一片空白......如果不是类型，我如何存储东西value_type?

由于类型不完整，编译器无法确定其大小。由于需要按值存储对象的大小，因此编译器会对此抱怨。如果必须处理不完整类型，则需要使用指针容器。例如在Test您可以使用std::vector<std::unique_ptr<IncompleteType>> or std::vector<IncompleteType*>.

您的代码中还有另一个问题。tree and vector失败与AbstractClass因为你试图按值存储它。由于它具有纯虚函数，因此无法在以下情况下实例化：Node被建造。