MAR
20
2006

Template Olympics

I want to have an iterator with an encapsulated "next" function. These iterators will be returned from a class that knows how to advance over the data structure, but that should be completely hidden from the users of the iterator.

Simply declaring the iterator must not require knowledge of the function which is advancing the iterator. (As that will be implementation dependant with multiple implementations. See the create() function in the second example.)

Here's a first implementation that I wrote which violates the line requirement above, but is in pure templates (using a functor):

(Sorry, all of the blank lines get removed by kdedevelopers.org.)



class IntNext
{
public:
IntNext() : m_current(0) {}
int operator()()
{
return m_current++;
}
private:
int m_current;
};

template
class Iterator
{
public:
T next()
{
return m_next();
}
private:
Next m_next;
};

int main()
{
Iterator it;

std::cout << it.next() << std::endl;
std::cout << it.next() << std::endl;

return 0;
}


Here's an uglier version, which works and meets the requirements, but requires a base class with a virtual member:


template
class Next
{
public:
virtual ~Next() {}
virtual T next() = 0;
};

class IntNext : public Next
{
public:
IntNext() : m_current(0) {}
virtual int next()
{
return m_current++;
}
private:
int m_current;
};

template
class Iterator
{
public:
Iterator(Next *next) : m_next(next) {}
~Iterator()
{
delete m_next;
}
T next()
{
return m_next->next();
}

private:
Next *m_next;
};

static Iterator create()
{
return Iterator(new IntNext);
}

int main()
{
Iterator it = create();

std::cout << it.next() << std::endl;
std::cout << it.next() << std::endl;

return 0;
}


That works, but I still don't like it. Anyone that comes up with a pure template way of doing this gets a cookie. For now I'm going to go with the second one just so that I stop screwing with things and can move on with the code, but the floor is open. :-)

Me, aKademy

In other news, no aKademy for me this year. There's exactly one week this summer that I have pre-existing plans and we nailed it. Meh.

Comments

I have two solutions, both relying on partial template specialization. The first uses a partial specialized class called Next:


template
class Next;

template<>
class Next
{
public:
Next() : m_current(0) {}

int next() { return m_current++; }

private:
int m_current;
};

template
class Iterator
{
private:
typedef Next NextType;

public:
T next()
{
return m_next.next();
}

private:
NextType m_next;
};

The second version uses a compile-time map for figuring out the right class to perform the "next" operation (e.g. NextInt):


class IntNext
{
public:
IntNext() : m_current(0) {}

int next() { return m_current++; }

private:
int m_current;
};

template
struct NextMap;

template<>
struct NextMap
{
typedef IntNext Type;
};

template
class Iterator
{
private:
typedef typename NextMap::Type NextType;

public:
T next()
{
return m_next.next();
}

private:
NextType m_next;
};

This second version is better if you need to give the "next" classes different names, at a cost of being slightly more complicated.


By hoirkman at Mon, 03/20/2006 - 23:29

Unfortunately I want to encapsulate iteration algorithms (over a small number of types) -- I probably should have made that more clear.

The more I think about it, this probably won't be possible with pure templates, but it's quite possible that there are still some tricks that I'm forgetting about. :-)

To get a bit closer to what I'm trying, imagine a data structure which can be traversed in multiple ways. I want to have a generic iterator class, where the user doesn't have to worry about how that structure is being traversed because (a) for each type of traversal there may be multiple implementations (i.e. a database vs. an in-memory data structure) and (b) I want to encapsulate different traversal algorithms (for simplicity, just imagine going forwards or backwards through a list).

In my above simplification, the logic to choose the backing data structure and the algorithm type would be in the create() function.

Thanks for the thought -- good stuff. :-)


By Scott Wheeler at Tue, 03/21/2006 - 00:17

Class CContactList
{
public:
CBuddy* GetNext();
private:
std::vector<*CBuddy> contactlist;
};

CBuddy* CContactList::GetNext()
{
static std::vector::iterator it = this->contactList.begin();
if(it != this->contactList.end())
{
return (*it++);
}
it = this->contactList.begin();
return NULL;
}

usage: while(buddy = GetContactList->GetNext()){...};

Very simple and hides the iterator and vector implementation.


By george anderson at Tue, 03/21/2006 - 14:44

In this case hiding the implementations is easy -- encapsulating multiple implementations is the trick. (i.e. having multiple implementations working with the same API)

For the moment I wrote a cleaned up version of the second example, which I can live with:


template
class Iterator
{
public:
class Mutator
{
public:
virtual ~Mutator() {}
virtual const T &next() = 0;
virtual bool hasNext() const = 0;
};
Iterator(Mutator *mutator);
~Iterator();
const T &next();
bool hasNext() const;
private:
Mutator *m_mutator;
};

template
Iterator::Iterator(Mutator *mutator) : m_mutator(mutator)
{

}

template
Iterator::~Iterator()
{
delete m_mutator;
}

template
const T &Iterator::next()
{
return m_mutator->next();
}

template
bool Iterator::hasNext() const
{
return m_mutator->hasNext();
}


By Scott Wheeler at Tue, 03/21/2006 - 15:29