3

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

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

测试.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（压缩）

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？

4

2 回答 2

5

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

您的代码中还有另一个问题。tree并vector失败，AbstractClass因为您试图按价值存储它。由于它具有纯虚函数，因此在创建时无法实例化Node。

于 2013-05-16T14:52:49.357 回答
2

您需要使用指向不完整类型的指针而不是不完整类型本身，即类似于 value_type* pData 而不是 value_type 数据的指针。

如果您这样做，编译器将不会尝试实例化不完整的类型，因为它可以使用指向不完整的指针（但不能使用不完整的值）。

这是他们在vector.h中的做法：

 template<class _Ty,
    class _Alloc>
    class _Vector_val
        : public _Container_base
{
//blah blah blah
pointer _Myfirst;   // pointer to beginning of array
pointer _Mylast;    // pointer to current end of sequence
pointer _Myend; // pointer to end of array
_Alty _Alval;   // allocator object for values
}

注意他们是如何到处使用指针的，而不是实际的对象。这里唯一的例外是分配器对象，但我的猜测是，它也从不实例化 value_type。希望这可以帮助。

PS很好的问题顺便说一句

于 2013-05-16T18:04:55.417 回答