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 T, class Next>
class Iterator
{
public:
T next()
{
return m_next();
}
private:
Next m_next;
};
int main()
{
Iterator<int, IntNext> 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 T>
class Next
{
public:
virtual ~Next() {}
virtual T next() = 0;
};
class IntNext : public Next<int>
{
public:
IntNext() : m_current(0) {}
virtual int next()
{
return m_current++;
}
private:
int m_current;
};
template <class T>
class Iterator
{
public:
Iterator(Next<T> *next) : m_next(next) {}
~Iterator()
{
delete m_next;
}
T next()
{
return m_next->next();
}
private:
Next<T> *m_next;
};
static Iterator<int> create()
{
return Iterator<int>(new IntNext);
}
int main()
{
Iterator<int> 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.
Syndicate Blogs
I have two solutions, both
I have two solutions, both relying on partial template specialization. The first uses a partial specialized class called Next:
template<class T>
class Next;
template<>
class Next<int>
{
public:
Next() : m_current(0) {}
int next() { return m_current++; }
private:
int m_current;
};
template<class T>
class Iterator
{
private:
typedef Next<T> 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<class T>
struct NextMap;
template<>
struct NextMap<int>
{
typedef IntNext Type;
};
template<class T>
class Iterator
{
private:
typedef typename NextMap<T>::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.
Possible solution
Class CContactList
{
public:
CBuddy* GetNext();
private:
std::vector<*CBuddy> contactlist;
};
CBuddy* CContactList::GetNext()
{
static std::vector<CBuddy*>::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.
That's hiding, not encapsulation.
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 T>
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 <class T>
Iterator::Iterator(Mutator *mutator) : m_mutator(mutator)
{
}
template <class T>
Iterator::~Iterator()
{
delete m_mutator;
}
template <class T>
const T &Iterator::next()
{
return m_mutator->next();
}
template <class T>
bool Iterator::hasNext() const
{
return m_mutator->hasNext();
}
Good thinking, but...
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.