Understanding how to design STL-compatible iterators

Discussion in 'C++' started by Christian Hackl, Nov 29, 2007.

  1. Hi!

    I'm having some troubles trying to teach myself how to design my own
    iterator classes for use in STL algorithms. The concrete case is a
    self-written, rather primitive HTML parser class, which I want to be
    able to use like a real STL container, for example like this:

    HtmlParser parser("...code...");
    typedef std::vector<std::string> StringVector;
    typedef std::insert_iterator<StringVector> InsertIterator;
    StringVector tags;

    std::copy(parser.begin(), parser.end(), InsertIterator(tags,
    tags.begin()));


    The solution I've conceived works, but I don't completely understand why :)

    Behind the scenes, there's a self-written iterator class (which is also
    the return type of the parser's begin() and end() member functions),
    defined like this to make sure it supports all operations required by
    the STL algorithms:

    class HtmlParserIterator
    {
    public:

    HtmlTag const *operator->() const;
    HtmlTag operator*() const;
    bool operator==(HtmlParserIterator const &other) const;
    bool operator!=(HtmlParserIterator const &other) const;
    HtmlParserIterator &operator++();
    HtmlParserIterator const operator++(int);
    HtmlParserIterator &operator=(HtmlParserIterator const &other);

    private:

    friend class HtmlParser;

    HtmlParserIterator(HtmlParser &parser, size_t current_pos);

    HtmlParser &parser_;
    size_t current_pos_;
    };


    In the same header file, I also had to define some traits for my class
    using std::iterator_traits:

    template <>
    struct std::iterator_traits<HtmlParserIterator>
    {
    typedef std::forward_iterator_tag iterator_category;
    typedef HtmlTag value_type;
    typedef size_t difference_type;
    typedef HtmlParserIterator * pointer;
    typedef HtmlParserIterator & reference;
    };


    Here's my first question: What exactly does difference_type mean? I
    think I understand the others, but this one I'm not sure about. The
    iterator has a size_t data member "current_pos_", which represents the
    parser's current position in the string being parsed, so size_t seemed a
    logical choice for difference_type. However, what is difference_type
    *used* for by the STL algorithms? When do you need the "distance"
    between two iterators, anyway?

    My second question is about std::iterator. From what I've gathered from
    online sources, you are supposed to derive your own iterator classes
    from std::iterator to make sure they work properly with
    std::iterator_traits. I've seen examples of iterator adapters using
    std::iterator like that. I, however, haven't used std::iterator at all
    and yet my class works like a charm. So what's the use of std::iterator?

    As for a more a general questions, do you spot anything else in my
    sample code that can be considered dangerous or evil? For example,
    defining HtmlParserIterator's constructor private so that only its
    friend class HtmlParser can construct new iterators? Or keeping a
    reference to the parser class as a member of the iterator? Is that OK?

    Thanks for your help!


    --
    Christian Hackl
     
    Christian Hackl, Nov 29, 2007
    #1
    1. Advertising

  2. Christian Hackl

    Noah Roberts Guest

    Christian Hackl wrote:
    > Hi!
    >
    > I'm having some troubles trying to teach myself how to design my own
    > iterator classes for use in STL algorithms.


    Instead of doing it that way you can use the boost::iterator library to
    make the construction of std compliant iterators much easier.
     
    Noah Roberts, Nov 29, 2007
    #2
    1. Advertising

  3. Noah Roberts wrote:

    > Christian Hackl wrote:
    >>
    >> I'm having some troubles trying to teach myself how to design my own
    >> iterator classes for use in STL algorithms.

    >
    > Instead of doing it that way you can use the boost::iterator library to
    > make the construction of std compliant iterators much easier.


    Thanks for the hint. Strange enough, I didn't even think about using
    Boost for this.

    Still, I'd be very interested in some more theoretical background, as
    explained in my previous posting. After all, as I take it, the Boost
    Iterator Library is built upon facilites (or concepts, at least) that
    are already present in the standard library, so if I don't understand
    them I won't really understand how Boost iterators work, either.


    --
    Christian Hackl
     
    Christian Hackl, Nov 29, 2007
    #3
  4. Christian Hackl

    Noah Roberts Guest

    Christian Hackl wrote:
    > Noah Roberts wrote:
    >
    >> Christian Hackl wrote:
    >>>
    >>> I'm having some troubles trying to teach myself how to design my own
    >>> iterator classes for use in STL algorithms.

    >>
    >> Instead of doing it that way you can use the boost::iterator library
    >> to make the construction of std compliant iterators much easier.

    >
    > Thanks for the hint. Strange enough, I didn't even think about using
    > Boost for this.
    >
    > Still, I'd be very interested in some more theoretical background, as
    > explained in my previous posting. After all, as I take it, the Boost
    > Iterator Library is built upon facilites (or concepts, at least) that
    > are already present in the standard library, so if I don't understand
    > them I won't really understand how Boost iterators work, either.
    >
    >

    I'd suggest trying before jumping to that conclusion.
     
    Noah Roberts, Nov 29, 2007
    #4
  5. Christian Hackl

    red floyd Guest

    Christian Hackl wrote:
    > Noah Roberts wrote:
    >
    >> Christian Hackl wrote:
    >>>
    >>> I'm having some troubles trying to teach myself how to design my own
    >>> iterator classes for use in STL algorithms.

    >>
    >> Instead of doing it that way you can use the boost::iterator library
    >> to make the construction of std compliant iterators much easier.

    >
    > Thanks for the hint. Strange enough, I didn't even think about using
    > Boost for this.
    >
    > Still, I'd be very interested in some more theoretical background, as
    > explained in my previous posting. After all, as I take it, the Boost
    > Iterator Library is built upon facilites (or concepts, at least) that
    > are already present in the standard library, so if I don't understand
    > them I won't really understand how Boost iterators work, either.
    >


    I'd read Austern's "Generic Programming and the STL".
     
    red floyd, Nov 29, 2007
    #5
    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. Dan
    Replies:
    0
    Views:
    468
  2. Marcin Kaliciñski

    Iterators and reverse iterators

    Marcin Kaliciñski, May 8, 2005, in forum: C++
    Replies:
    1
    Views:
    488
    Kai-Uwe Bux
    May 8, 2005
  3. pwalker
    Replies:
    5
    Views:
    367
    Juha Nieminen
    Jul 31, 2007
  4. , India
    Replies:
    10
    Views:
    1,081
    James Kanze
    Aug 8, 2009
  5. pantagruel
    Replies:
    0
    Views:
    245
    pantagruel
    Feb 17, 2006
Loading...

Share This Page