How to fix my STL style container for storing incomplete or abstract types?

Question

A few days ago, I took on the task of trying to write a basic tree implementation in the same style as STL containers. Now I'm trying to use it in my code, but two things do not seem to work, and they work with std::vector . Namely, using incomplete types and using abstract types.

How to fix my tree implementation to get this functionality? I tried to slightly condens my code to show you basically 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; }; 

---

util / tree.hpp (with compaction)

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

---

When compiling with g++ -O3 -Wall -Wextra -pedantic -std=c++11 test.cpp I get the following output:

 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 ^ 

My tree has problems with these types, while std::vector does not. I see that this is due to the way I store the data inside the nodes, but I draw a space trying to come up with the right way to do this ... How to store things, if not of type value_type ?

Answer 1

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

There is another problem in your code. tree and vector do not work with AbstractClass because you are trying to save it by value. Since it has pure virtual functions, it cannot be created when creating Node .

Answer 2

You need to use a pointer to an incomplete type, not a partial type, i.e. something along the lines of value_type * pData instead of data value_type.

If you do this, the compiler will not try to create an instance of an incomplete type, since this is normal with pointers to incomplete (but not with an incomplete value).

Here's how they do it in 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 } 

Notice how they use pointers everywhere, not the actual object. The only exception here is the allocator, but, in my assumption, it also never creates a value_type value. Hope this helps.

PS The big question is BTW