如何修复我的STL样式容器以保存不完整或抽象类型？

问题描述

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

A few days ago, I took it upon myself to try and write a basic tree implementation in the same style as the STL containers. Now I am trying to use it in my code, but two things don't seem to work that do work with say a std::vector. Namely, using incomplete types and using abstract types.

如何修复我的树实现来获得这个功能？

How do I fix my tree implementation for it to gain this functionality? I've tried to condense my code a bit to show you mainly the relevant parts.

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

---

hpp （精简）

---

util/tree.hpp (condensed)

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 ？

My tree has trouble with these types, whereas std::vector does not. I can see that it has to do with how I store the data inside the nodes, but I am drawing a blank when trying to come up with the right way to do it... How do I store things if not of type value_type?

推荐答案

由于类型不完整，编译器无法确定它的大小。由于需要按照值来存储对象的大小，编译器就会对它进行处理。如果你必须处理不完整的类型，你将需要使用一个指针容器。例如，在 Test 中，您可以使用 std :: vector< std :: unique_ptr< IncompleteType>> c $ c> std :: vector< IncompleteType *> 。

Since the type is incomplete the compiler has no way of determinng it's size. Since the size is needed to store the objects by value the compiler whines about it. If you must deal with incomplete types you will need to use a container of pointers. For instance in Test you can use std::vector<std::unique_ptr<IncompleteType>> or std::vector<IncompleteType*>.

您的代码还有另一个问题。 tree 和向量失败与 AbstractClass 按值存储。因为它有纯虚函数，当创建 Node 时不能实例化。

There is another issue in your code. tree and vector fail with AbstractClass because you are trying to store it by value. Since it has pure virtual functions it cannot be instantiated when the Node is created.

这篇关于如何修复我的STL样式容器以保存不完整或抽象类型？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！