Template subclass pointer problem

Question

In a moment of madness, I decided to write a quadtree C++ template class. I've run into some weird compiler error that I don't understand with regard to subclasses and pointers to templates. I've found some hacky work arounds, but I wondered if anyone could shed some light on why my code wouldn't compile...

---

I'm on Linux, building with scons, using g++

My code looks something like this, I have a template class to describe a tree and a subclass describing 'leaves':

template <class value_type>
class QuadTree
{

public:

    class Leaf //-Subclass--------------------------
    {
        friend class QuadTree< value_type >;
    protected:
        value_type* m_data;

        Leaf();
        ~Leaf();

    }; //-end-subclass------------------------------

    QuadTree();

    ~QuadTree();

    Leaf * Insert ( const value_type & _x );

protected:

    QuadTree( Quadtree< value_type >* _parent );

    QuadTree< value_type >* m_parent;

    QuadTree< value_type >* m_children[4];

    std::set< Leaf* > m_leaves;

};

First pointer problem I get is in the QuadTree destructor:

template <class value_type>
QuadTree< value_type >::~QuadTree()
{
    // ... Delete children ...

    // I allocate each leaf, so I need to delete them
    std::set< Leaf* >::iterator it = m_leaves.begin(); // <-- bad
    std::set< Leaf* >::iterator endit = m_leaves.end(); // <-- bad
    for(;it != endit; ++it)
        delete *it;
}

When I compile I get this error: expected ';' before ‘it’ and expected ';' before ‘endit’. The other pointer error is in the Insert function definition:

template <class value_type>
Leaf * QuadTree< value_type >::Insert ( const value_type & _x ) // <-- bad
{
    // Insert stuff...
}

I get the compile error: expected constructor, destructor, or type conversion before ‘*’ token

Anyone know why I'm getting these errors? I've got fixes for the problems, but I want to know why I can't do it this way.

Ps. I've edited the code to show it here, so it is possible I've missed something I thought utterly irrelevant.

Edit. Fixed Quadtree -> QuadTree typo

Answer 1

You need the typename keyword to correct the first problem, as in:

typename std::set< Leaf* >::iterator it = m_leaves.begin();

The second problem is caused by the fact that Leaf and value_type do not name types at that line. You need to specify that you mean Leaf and value_type of Quadtree< value_type >, as in:

template <class value_type>
Quadtree< value_type >::Leaf * Quadtree< value_type >::Insert ( const typename Quadtree< value_type >::value_type & _x )

Answer 2

You need

typename std::set< Leaf* >::iterator it = m_leaves.begin(); 
typename std::set< Leaf* >::iterator endit = m_leaves.end();

The type of std::set depends on another template argument and you have to tell the compiler that this is actually a type. gcc 4.5.0 produces a better error message.

The second error is similar:

template <class value_type>
typename QuadTree<value_type>::Leaf* QuadTree< value_type >::Insert ( const value_type & _x )
{
    // Insert stuff...
}

Leaf is a inner class to QuadTree. You need to name it as such and you need to specify the type of the QuadTree as the inner class depends on the template parameter.

Another thing: You have a typo in QuadTree in many places.

Answer 3

In the first case you need to tell the compiler that std::set< Leaf* >::iterator is a type:

 typename std::set< Leaf* >::iterator it = ...
 typename std::set< Leaf* >::iterator endit = ...

Since Leaf depends (indirectly) on the template parameters the compiler can't now for sure what exact class Leaf will end up to be, and it doesn't know if there will be specializations for std::set<Leaf*> and how these specializations might define their iterator. Therefore the compiler assumes that iterator is a normal member variable of std::set< Leaf* >, unless told otherwise by the typename keyword.

The second problem is that when you specify the return vale Leaf you are not yet in your classes scope and the compiler doesn't know you're referring to the nested class. Use the completely qualified name of the class instead:

template <class value_type>
typename Quadtree< value_type >::Leaf * Quadtree< value_type >::Insert (...) ...

Answer 4

Unrelated... but still.

The Leaf class is an example of what you should not do.

class Leaf //-Subclass--------------------------
{
    friend class QuadTree< value_type >;
protected:
    value_type* m_data;

    Leaf();
    ~Leaf();

}; //-end-subclass------------------------------

• don't use protected for attributes, it's the same as using public. It means you cannot maintain any class invariant, and notably cannot guarantee there won't be any leak
• follow the Rule of the Sacred 3: if you write any of Destructor, Copy Constructor and Assignment Operator, you need to write the other two. Here the copy constructor and assignment operator should be protected to prevent object slicing (as much as possible) and they should take care about the memory.

Now the question: why do you use a pointer here ?

class Leaf
{
public:
  explicit Leaf(value_type data): mData(data) {}

private:
  value_type mData;
};

Seems perfectly fine and relieves you of the tedium of dealing with dynamically allocated memory.

By the way, your QuadTree class suffers from the same issue: it lacks a copy constructor and assignment operator.