C++Talk.NET

Charles Bissonnette · Guest

I've wrote an iterator for my class "Seg" and and the class has an member
typedef that defines that iterator

typedef SegIter iterator;

Everything used the standard way of definining iterator from STL

SegIter is defined like this :

class SegIter : public std::iterator<std::bidirectional_iterator_tag, Seg*>
{
.....
}
Seg objects are segment from an interval tree.

When defining a region to iterate from, let's say seg1->begin() to
Seg2->end(), you can so such with an unrolled loop

Seg::iterator iter;
for(iter = seg1->begin(), iter != seg2->End(), iter++)
{
.....
}

Currently, operator++() from the iterator is hardcored to do a depth-first
from the start to the end of the segment. However, I would like to customize
the traversal algorithm through a policy class

teamplate <class TraversePolicy>
class SegIter : public TraversePolicy
{
...
}

SegIter would then require the policy class to implement the method "bool
advance(SegIter*). The This pointer is passed as pointer to the policy class
... At this point I'm not sure if this is the right usage of policies (I just
read the book Modern C++ seems like Policies is appropriate for that).

Doing so implies that the policy is not reponsible for implementing the
traversal, but instead the iterator itself. How can I tell the iterator
which algorithm to use then? I though about how STL use compile time
polymorphism and function overloading to determine the right algorithm to
use depending on the type of iterator. I thought doing the same, by defining
a bunch of classes,

struct linear_traverse_type_tag
{};
struct hierarchical_traverse_tag
{};
struct depth_first_traverse_tag :
public hierarchical_traverse_tag
{};
struct breadth_first_traverse_tag :
public hierarchical_traverse_tag
{};
struct parent_chain_traverse_tag :
public hierarchical_traverse_tag
{};

And having the iterator implementing different overloaded version of Advance

SegIter& advance(depth_first_traverse_tag &);
SegIter& advance(breadth_first_traverse_tag &);
SegIter& advance(parent_chain_traverse_tag &);

For each Policy class that I would define, they would define a typedef
_traversal with the right type mentioned above. Even better, I could have
the policy class being a template class and the argument being the traversal
tag.

template<class traversal>
class SegIter : public GenericTraversePolicy<SegIter, traversal>
{

}

In this cass, GenericTraversePolicy class is not really a policy class but
simply a templatized class that knows with overloaded Advance from the
iterator to call.

I'm really not sure if what i'm describing above is the right way of solving
this problem. My first concern is STL which expect an iterator of a class to
be of one type. That iterator cannot be templatized. Otherwize, how STL
determine with iterator to use?
I'm not so sure also if the use of STL here is the right approach too. I've
been reading the Range Concept from the Book "Imperfect C++" and it seems
like Range may also offer a better way of solving this problem.

Any feedback how to solve this problem is appreciated,

Regards,
-Charles

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Alberto Barbati · Guest

Charles Bissonnette wrote: