Forward-declaring templates that need each other

Question

A professor at uni wanted us to implement a stack using an std::vector, and to write an "unstacking" iterator for it (that is, an iterator which when iterated over pops the top of the stack).
Everything could have been fine until he also decided he wanted all of it to be generic, using templates and all. That's when hell began.

So the first thing I did was writing template<typename T> class VectorStack:

//file VectorStack.hpp
template <typename T>
class VectorStack
{
    public:
        VectorStack();
        virtual size_t size();
        virtual bool empty();
        virtual void push(T obj);
        virtual T pop();

    private:
        vector<T> _data;
};  

Implementation may not be relevant here so I'll skip it. Don't hesitate to ask if you need it. Then I had to write template<typename T> class VectorStackIterator...

• In order for that iterator to unstack an instance of VectorStack, it must contain at least a pointer to that instance. So VectorStackIterator needs to know about VectorStack, which leads us to a first forward declaration.
• But also, VectorStack has begin() and end() methods which are supposed to return a VectorStackIterator. So VectorStack also needs to know about VectorStackIterator, which leads us to a second forward declaration.

So I wrote my iterator in a separate file:

//file VectorStackIterator.hpp
template<typename T>
class VectorStack;          //Forward declaration of the VectorStack

template<typename T>
class VectorStackIterator : public iterator<random_access_iterator_tag, VectorStack<T>>
{
    public:
        VectorStackIterator(size_t n, VectorStack<T>* instance);
        T operator--();
        bool operator==(VectorStackIterator other);
        bool operator!=(VectorStackIterator other);

    private:
        VectorStackIterator();
        T& operator=() {};

        size_t _n;
        VectorStack<T>* _instance;
};

...and updated my VectorStack to look like this:

//file VectorStack.hpp
template<typename T>
class VectorStackIterator;  //Forward declaration of the iterator

template <typename T>
class VectorStack
{
    public:
        //...

        VectorStackIterator<T> top();
        VectorStackIterator<T> bottom();

    //...
};  

Again, implementation of the iterator may not be relevant.
At this point, I already had the compiler screaming because I was using incomplete types everywhere. So I tried out something else: I put the declarations of both the VectorStack and the VectorStackIterator at the beginning of the same file, and only then, I put the definitions of all of the methods. Here is what it looks like:

//file VectorStack.hpp
#ifndef VECTOR_STACK_HPP
#define VECTOR_STACK_HPP

#include <vector>
using std::vector;

#include <iterator>
using std::iterator;

#include <exception>
using std::out_of_range;

template <typename T>
class VectorStack;   
//still had to forward-declare this because VectorStackIterator uses it in its own declaration.

//Class declaration (VectorStackIterator)
template<typename T>
class VectorStackIterator : public iterator<random_access_iterator_tag, VectorStack<T>>
{
    public:
        VectorStackIterator(size_t n, VectorStack<T>* instance);
        T operator--();
        bool operator==(VectorStackIterator other);
        bool operator!=(VectorStackIterator other);

    private:
        VectorStackIterator();
        T& operator=() {};

        size_t _n;
        VectorStack<T>* _instance;
};

//Class declaration (VectorStack)
template <typename T>
class VectorStack
{
    public:
        VectorStack();
        virtual size_t size();
        virtual bool empty();
        virtual void push(T obj);
        virtual T pop();

        VectorStackIterator<T> top();
        VectorStackIterator<T> bottom();

    private:
        vector<T> _data;
};

All of this is followed by the definition of every method declared above. I don't think that's where the error lies in, but please ask if you want me to provide it.

This is the closest attempt to a solution that I've come up with, but the compiler still complains about Incomplete types not allowed here when I declare a VectorStack<int> object in the main function:

#include "VectorStack.hpp"
int main(int argc, char** argv)
{
    VectorStack<int> v;            //Incomplete types not allowed here
    v.push(0);                     //Incomplete types not allowed here
    v.push(1);                     //Incomplete types not allowed here
    v.push(2);                     //Incomplete types not allowed here
    for (auto it = v.top(); it != v.bottom();) //Incomplete types not allowed here (x2)
    {
        cout << it-- << endl;
    }

    return 0;
}

If I try to forward-declare the iterator instead of the vector stack, then the vector stack is no longer incomplete, but the iterator is, and I get errors on the heading line of the for loop.
It looks like the compiler won't ever go beyond the forward declaration, to the actual definitions that make everything complete.

I'm running out of options, do you have any ideas?

Answer 1

It's a bit hard to follow your post. But in general, there are some things to keep in mind:

• Class members stored by value require complete types to be available at the time that the containing class is declared, because the compiler needs to know how much memory the object should take.
• Pointer and reference members do not need to be complete when declaring the containing class, because the size is always just the size of a pointer.
• Complete types are always required as soon as you start to use the object in question, because the compiler needs to know what member variables and functions that type should contain.
• If you ever get into a situation where you can't resolve "incomplete type" errors, double check your design to make sure that it makes sense; you don't want (for example) two types to circularly contain each other (by value, again references and pointers are fine).

That said, I think the standard way to handle this is:

class ClassB;
class ClassA {
    ClassB* or ClassB&
}
class ClassB {
    ClassA
}
ClassA::implementations // These two can happen in any order, since both ClassA and ClassB are complete at this point
ClassB::implementations

Since both of your classes are templated, the implementations need to be put in header files, so you may need to be careful with the way you structure your files to enforce the order in which these pieces will happen.