How do I fix my STL style container to hold incomplete or abstract types?

Question

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

---

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

---

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 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?

Answer 1

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*>.

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.

Answer 2

You need to use a pointer to incomplete type rather than incomplete type itself, i.e something along the lines of value_type* pData instead of value_type data.

If you do that, compiler will not attempt to instantiate an incomplete type as it's ok with pointers to incomplete (but not with incomplete-by-value).

Here is 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
}

Note how they use pointers all over the place, never the actual object. The only exception here is the allocator object, but my guess is, it also never instantiates value_type. Hope this helps.

P.S Great question BTW