Subtyping iterators

Discussion in 'C++' started by Michael Le Barbier Grünewald, May 9, 2012.

  1. 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
    Michael Le Barbier Grünewald, May 9, 2012
    #1
    1. Advertising

  2. Michael Le Barbier Grünewald

    Marc Guest

    Michael Le Barbier Grünewald wrote:

    > 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
    Marc, May 9, 2012
    #2
    1. Advertising

  3. Michael Le Barbier Grünewald <> wrote:
    > ??? 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).
    Juha Nieminen, May 10, 2012
    #3
  4. Hi Marc, hi Frank,

    thank you for your replies,

    On Wednesday, May 9, 2012 2:20:50 PM UTC+2, K. Frank wrote:
    > 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, May 11, 2012
    #4
  5. Hi Juha, thank you very much for your detailed answer!

    On Thursday, May 10, 2012 9:01:23 AM UTC+2, Juha Nieminen wrote:

    > 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 Le Barbier Grünewald, May 14, 2012
    #5
  6. Michael Le Barbier Grünewald

    Guest

    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.
    , May 14, 2012
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. valentin tihomirov

    Subtyping issue

    valentin tihomirov, Jun 30, 2005, in forum: VHDL
    Replies:
    1
    Views:
    542
    Jonathan Bromley
    Jun 30, 2005
  2. Ragnar
    Replies:
    2
    Views:
    343
    Dan Cernat
    Nov 7, 2003
  3. Marcin Kaliciñski

    Iterators and reverse iterators

    Marcin Kaliciñski, May 8, 2005, in forum: C++
    Replies:
    1
    Views:
    485
    Kai-Uwe Bux
    May 8, 2005
  4. shawn
    Replies:
    2
    Views:
    265
    shawn
    Oct 17, 2005
  5. Replies:
    3
    Views:
    371
Loading...

Share This Page