Understanding how to design STL-compatible iterators

[Christian Hackl]

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!

 

[Noah Roberts]

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.

 

[Christian Hackl]

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.

 

[Noah Roberts]

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.

 

[red floyd]

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".