Re: [Boost-users] Re: Iterators and maps [was Re: Whereshould STLsuggestionsgo?]

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.