What should the iterator type be in this C++ template?

Question

While working on some graphics code a while back, I wrote Rect and Region classes using ints as the underlying coordinate holder, and that worked fine. The Region was implemented as a simple class extension to an STL list, and just contains a list of Rects.

Now I also need the same kinds of classes using doubles as the underlying coordinate holder, and decided to try my hand at templatizing it. So I basically replaced "int" with "typename T" in an intelligent manner and fixed the problems.

But there's one remaining problem that has me stumped. I want to calculate a Region's bounding box by doing a union on all the Rects that comprise it. That works fine when not templatized, but g++ chokes on the list iterator when this is templatized.

Here's the relevant code:

// Rect class that always remains normalized
template <typename T>
class KRect
{
public:

    // Ctors
    KRect(void)
        : _l(0), _t(0), _r(0), _b(0)
    {
    }
    void unionRect(const KRect& r)
    {
        ...
    }

private:
    T _l, _t, _r, _b;
};

// Region class - this is very brain-dead
template <typename T>
class KRegion : public std::list< KRect<T> >
{
public:
    ...

    // Accessors
    KRect<T> boundingBox(void)
    {
        KRect<T> r;
        iterator i;
        for (i = this->begin(); i != this->end(); i++)
        {
            r.unionRect(*i);
        }
        return r;
    }
    ...
};

When that code isn't part of a template, so that T is definite (e.g. an int), the "iterator i" line works fine. But in what you see above, g++ on Ubuntu emits errors which I don't find very informative:

include/KGraphicsUtils.h: In member function ‘KRect<T> KRegion<T>::boundingBox()’:
include/KGraphicsUtils.h:196: error: expected ‘;’ before ‘i’
include/KGraphicsUtils.h:197: error: ‘i’ was not declared in this scope
include/KGraphicsUtils.h: In member function ‘KRect<T> KRegion<T>::boundingBox() [with T = int]’:
--- redacted ---:111:   instantiated from here
include/KGraphicsUtils.h:196: error: dependent-name ‘std::foo::iterator’ is parsed as a non-type, but instantiation yields a type
include/KGraphicsUtils.h:196: note: say ‘typename std::foo::iterator’ if a type is meant

My guess is this is a type qualification issue with some template-y spin I'm not familiar with. I've tried all kinds of things like:

std::list< KRect<T> >::iterator i;
this->iterator i;

but nothing seems to work.

Any suggestions?

Answer 1

iterator is a dependent type (it depends on a template argument) and needs to be prefixed with typename:

typename std::list< KRect<T> >::iterator i;

Better style would be to provide a class-wide typedef:

template <typename T>
class KRegion : public std::list< KRect<T> >
{
    typedef std::list< KRect<T> > base;
    typedef typename base::iterator iterator;
    // ...
};

Answer 2

I think gf has your answer, but I'd like to suggest having the region manage a list as a member instead of a base class:

template <typename T>
class KRegion
{
protected:
     typedef std::list< KRect<T> > ListType;
     ListType list;
public:
    ...
    // Accessors
    void addRect(KRect<T> & rect) { list->push_back(rect); }
    ...
    KRect<T> boundingBox(void)
    {
        KRect<T> r;
        ListType::iterator i;
        for (i = list->begin(); i != list->end(); i++)
        {
            r.unionRect(*i);
        }
        return r;
    }
    ...
};

My motivation for this suggestion is that you may, one day, want to use a different container for storing your KRects, and having the list as an internal member would let you do so without breaking all of your client code.