From: Ben Hutchings (ben.hutchings_at_[hidden])
Date: 2004-12-15 08:35:10
Jim Lear wrote:
> Ben Hutchings wrote:
>
>> No, but I think your concept of what an iterator is may be faulty.
>> Since an iterator "points" to a sequence element (or to the end of a
>> sequence) by itself; there is no need to combine it with a container
>> to access that element. You seem to want a regularity which doesn't
>> really make sense, hence my earlier guess that you wanted to write
>> container- independent code.
>
> Most of my concepts are definitely faulty (ask my wife), but they're
> especially so when it comes to iterators! :-)
>
> I read the suggested interview with Stepanov, and it (along with
> everyone's comments) was quite helpful. But, my ignorance runs deep and
> wide. My new (mis-?) understanding of the iterator is that it allows
> generic programming by providing a consistent interface to containers.
> As such, Stepanov did not want to understand the container to write an
> algorithm, but only the iterator and operations on iterators. Is my
> ignorance getting any narrower? :-)
Right. Besides, iterators can be used with sequences (by which I do not
mean STL sequences, but I cannot think of a better word) that are not
containers - for example, std::istream_iterator iterates over parseable
elements of an input stream and boost::function_output_iterator iterates
over arguments to be passed to a function. The STL iterator concept is
extremely general.
<snip>
> I think the light is beginning to turn on, but don't get your hopes up
> too much. Iterators are very heavy concepts for newbies.
I don't disagree.
<snip>
> Okay, okay! But I'm still pretty clueless because one of Ben's earlier
> statements still doesn't digest yet:
>
> Container-independent code is an impossible and pointless goal.
> maps have different semantics from other containers. <snip> What
> you can do is to write iterator-independent code, then use an
> iterator adapter to convert the iterators over pairs into iterators
> over the mapped values:
>
> I thought the idea of generic programming is to make
> container-independent code.
Let me expand on what I said. You can't in general write code that
works on whole containers and expect to be able to change the container
type at will, because containers have different properties and one
normally needs to choose one that provides appropriate semantics and an
appropriate trade-off between efficiency of various operations
(particularly speed of modification vs speed of access) for some
specific application. Iterators provide the bridge from containers to
generic algorithms, which allows a kind of container-independence in
generic libraries, but that doesn't mean that every algorithm makes
sense with every container. Further, some operations can be performed
much more efficiently on specific containers in a non-generic way. For
example, sorting a map makes no sense because it's always sorted, while
sorting a list can be done by changing links rather than moving its
elements, so it has a member function to do that.
> I'm not sure what an iterator adapter is,
> but is it necessary for "iterator-independent code?"
No, but iterator adapters may be useful or necessary to connect a
container with an algorithm you want to apply to it. The algorithms are
the things that are iterator-independent.
> I'm just a newbie
> who wants to sequence through my map, really. I don't want to be forced
> to understand iterators, adapters, iterator-independence, and generic
> programing paradigms to do so. :-)
<snip>
I'm afraid you're going to have to understand at least something about
iterators and generic programming to be able to make use of the standard
library.
Ben.