3

数日前、STL コンテナーと同じスタイルで基本的なツリー実装を作成することにしました。今、私は自分のコードでそれを使用しようとしていますが、2つのことがうまくいかないようです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;
};

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>>std::vector<IncompleteType*>

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.

于 2013-05-16T14:52:49.357 に答える
2

不完全な型自体ではなく、不完全な型へのポインタを使用する必要があります。つまり、value_type データの代わりに value_type* pData の行に沿ったものを使用する必要があります。

これを行うと、コンパイラは不完全な型のインスタンス化を試みません。これは、不完全へのポインタで問題ないためです (ただし、値による不完全では問題ありません)。

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
}

実際のオブジェクトではなく、あらゆる場所でポインターを使用する方法に注意してください。ここでの唯一の例外は allocator オブジェクトですが、私の推測では、value_type をインスタンス化することもありません。お役に立てれば。

PS 素晴らしい質問ところで

于 2013-05-16T18:04:55.417 に答える