Как мне исправить мой контейнер в стиле 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;
};

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?

3

Решение

Поскольку тип является неполным, компилятор не может определить его размер. Поскольку размер необходим для хранения объектов по значению, компилятор жалуется на это. Если вам приходится иметь дело с неполными типами, вам нужно использовать контейнер указателей. Например, в Test ты можешь использовать std::vector<std::unique_ptr<IncompleteType>> или же std::vector<IncompleteType*>,

В вашем коде есть еще одна проблема. tree а также vector потерпеть неудачу с AbstractClass потому что вы пытаетесь сохранить его по значению. Поскольку он имеет чисто виртуальные функции, он не может быть создан, когда Node создано.

5

Другие решения

Вам нужно использовать указатель на неполный тип, а не на сам неполный тип, то есть что-то вроде строк 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 Большой вопрос Кстати

2

По вопросам рекламы [email protected]