Несколько дней назад я решил попробовать написать базовую реализацию дерева в том же стиле, что и контейнеры 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;
};
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
?
Поскольку тип является неполным, компилятор не может определить его размер. Поскольку размер необходим для хранения объектов по значению, компилятор жалуется на это. Если вам приходится иметь дело с неполными типами, вам нужно использовать контейнер указателей. Например, в Test
ты можешь использовать std::vector<std::unique_ptr<IncompleteType>>
или же std::vector<IncompleteType*>
,
В вашем коде есть еще одна проблема. tree
а также vector
потерпеть неудачу с AbstractClass
потому что вы пытаетесь сохранить его по значению. Поскольку он имеет чисто виртуальные функции, он не может быть создан, когда Node
создано.
Вам нужно использовать указатель на неполный тип, а не на сам неполный тип, то есть что-то вроде строк 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.
Надеюсь это поможет.
P.S Большой вопрос Кстати