Subtyping iterators

[Michael Le Barbier Grünewald]

Dear group,

interpreting iterators as handles to stream, it seems natural to try to represent
filters, combinators, and so on, as iterators as well. Being new to C++, Iam looking for advice on how to do the things right.

Let's say I want to define a filter for vector of integers, that is, implement the following signature:

class filter : public vector<int>::const_iterator
{
filter(bool predicate(int));

// Move to the next integer satisfying predicate
filter& operator++();
};

Here are my difficulties:

— A vector<int>::const_iterator does not know about the structure it is exploring, so I probably need to supply the corresponding (vector.end()) to my cosntructor (so that ++ knows where to stop). I feel it is a bit clumsy, is there a nicer way to deal with this?

— Passing function pointers as arguments is not so general as we may wantit, since the predicate could also be a member function or another callable (and object or a struct with () operator), so I am not quite sure about what I should use as a parameter.

For this second issue, I think I would like the predicate to be either:

1. or a plain function;
2. or a member function on some object;
3. or the result of partial application (with these bind1 and bind2 operators from the STL).

Probably, I could manage to write something for 1. and 2., but there is probably many ways to do this and I am pretty sure I am unable to satisfy 3. with a solid design.


I come from functional languages (where the problem is simply discarded!) so I feel very attracted by functional traits in C++ (these for_each and bind* templates for instance). But being a novice C++ programmer, I am not sure how will these facilities fit in larger projects. (I have the intuition that these facilities will not be usable at all in poorly designed programs..) So I would be very interested to know about your experiences in this domain or to know where I can read interesting or well-written code using these functional traits in C++.

Thanks for your help and your insights!
Michael

 

[Marc]

interpreting iterators as handles to stream, it seems natural to try
to represent filters, combinators, and so on, as iterators as well.
Being new to C++, I am looking for advice on how to do the things
right.

Let's say I want to define a filter for vector of integers,

You could take a look at:

http://www.boost.org/doc/libs/1_49_0/libs/iterator/doc/filter_iterator.html

 

[Juha Nieminen]

??? A vector<int>::const_iterator does not know about the structure it

is exploring, so I probably need to supply the corresponding
(vector.end()) to my cosntructor (so that ++ knows where to stop).
I feel it is a bit clumsy, is there a nicer way to deal with this?

In general, operator++ doesn't need to know where to stop because it's
the calling code that compares it to the range end iterator after each
increment.

(There are some cases where the iterator needs to know more about the
data structure it's handling than just the node it's currently pointing to.
In that case you can store a pointer to the data structure itself in the
iterator. std::back_insert_iterator is a good example of this.)

??? Passing function pointers as arguments is not so general as we may

want it, since the predicate could also be a member function or
another callable (and object or a struct with () operator), so I am
not quite sure about what I should use as a parameter.

The STL containers and algorithms that support some kind of user-defined
functor (such as a comparison functor) do so by taking the functor type
as template parameter (and then if a member function needs an actual
functor object, it uses that template type to take it as parameter).

If it's enough for the member function to know what the functor type
is, then you can make that function templated. However, if the entire
class needs to know it (eg. because it stores an object of that type
as a member variable) then there's no other way around it than to make
it a template parameter to the class itself (in which case you have to
specify it when instantiating the class). You can give it some default
value if one is common (in the same way as STL algorithms and data
containers do).

If you look at the specification of, for example, std::sort() and
std::map, you'll notice that they both take a comparison function as
template parameter (with a default value so that you don't need to
specify it every time if the default suffices).

 

[Michael Le Barbier Grünewald]

Hi Marc, hi Frank,

thank you for your replies,

This may or may not be relevant, but does Boost.Range

http://www.boost.org/doc/libs/1_49_0/libs/range/doc/html/index.html

do some of what you want?

indeed! Reading the source code was also quite useful (it is not so hairy as I feared it).

cheers,
Michael

 

[Michael Le Barbier Grünewald]

Hi Juha, thank you very much for your detailed answer!

In general, operator++ doesn't need to know where to stop because it's
the calling code that compares it to the range end iterator after each
increment.

The case where the iterator is used to explore the structure “in a special way”—for instance skipping some elements in a container—is one casewhere the specialised iterator needs to know more.

The code in std::back_insert_iterator was actually helpful.

The STL containers and algorithms that support some kind of user-defined
functor (such as a comparison functor) do so by taking the functor type
as template parameter (and then if a member function needs an actual
functor object, it uses that template type to take it as parameter).

If it's enough for the member function to know what the functor type
is, then you can make that function templated. However, if the entire
class needs to know it (eg. because it stores an object of that type
as a member variable) then there's no other way around it than to make
it a template parameter to the class itself (in which case you have to
specify it when instantiating the class).

I was not aware that template methods were allowed by the language!

Also, I feel the need to lear more about template techniques, maybe you know a good book or article on this subject?


Thank you very much for your helpful comments,
Michael

 

[michael.j.smith]

I'm not sure that the "iterator as a filter" concept fits naturally with C++.

As you suggested, the iterator would need to know where the end of the sequence is, which is not usually possible.

May I suggest that you look at some of the standard algorithms, such as std::remove_if() and std::replace_if().

In these algorithms, the filter can be passed to the algorithm as a functional object. I will suggest that this is a more "C++ ish" way of solving the problem.