Ben Hutchings wrote:

Jim Lear wrote:

...

The map iterators are really what tripped me up as an STL newbie. One must understand the iterators are implemented as pairs for maps, and pointers for vectors and other things. By providing an "T operator[](iterator)" function for random access and associative containers (and for sequences maybe), one could achieve a consistant interface.

Container-independent code is an impossible and pointless goal. maps have different semantics from other containers. You may want to iterate over just the mapped values, but other people may want to iterate over the keys, or over the pairs (and indeed, so may you, in other part of your program). Who's to say which of these is right? 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:

Have you seen http://www.zib.de/weiser/vtl/ and http://www.boost.org/libs/range/index.html? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

Jim Lear wrote: <snip>

I'm a little overwhelmed by these discussions, so forgive me for my ignorance or incapacity to communicate. My intention isn't to create container-independent code.

Ah, good.

My intention is to create code for maps (and vectors) that looks like what I think code for maps (and vectors) would look like. Iterators look to me like pointers to linked lists for vectors, and like pairs of pointers for maps.

Iterators are kind of like pointers into arrays, but possibly with some limitations on how you can use them; random-access iterators have no such limitations, whereas input and output iterators only allow you to go through the sequence once, forward, one step at a time. Iterators over maps are bidirectional iterators, which are somewhere in-between: they can then be moved forward and backward over the sequence however many times you want, but only one step at a time. They do not behave like pairs of pointers but like pointers to pairs. (The standard iterator categories unfortunately combine requirements on traversal operations with requirements on access operations; if you want to know exactly what the iterator categories mean, look elsewhere.)

There is nothing wrong with these semantics, except they seem odd compared to some other languages semantics for associative arrays (e.g. awk). However, overloading the operator[] in the map class to take iterators as a parameter would allow iterators to be treated like keys, if one desires, which to me seems more natural. This would still allow one to iterate over keys, mapped values, or pairs.

So in the absolute most abhorently poor code example (let's just call it "meta-code"), the map operator would behave like:

data_type &operator[](const iterator &i) { return i->second; }

I think that code should actually work if you only replace "data_type" to "mapped_type", but I suggest you don't go editing your <map> header just yet!

Am I just too ignorant to make any sense? :-) Maybe I'll crawl back into my hole. :-)

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

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.

At 11:20 AM 12/15/2004, Jim Lear wrote:

... I still cling to the notion that something like the container[iterator] concept should be included, and bad old-style programming should be accomodated, as long as they're accompanied by lots of footnotes explaining that using such concepts will make one's code container-dependent.

Other's have had the same feeling; but eventually the light dawns and they realize that trying do dumb down the STL would result in something harder rather than easier to use.

This would allow people to write useful (albeit bad) STL code quickly, while warning signs point the way to generic programming.

It turns out that the fastest way to write STL code is simply to learn to use the STL as specified in the standard or in the usual texts, and not try to somehow do it "better" or "easier". Let me relate something I experienced myself and have also heard from probably a dozen programmers who had a similar experience when they first learned to use the STL. After working enough examples to at least be able to get simple STL code working, I decided to try to use a std::map and a std::vector in a real application. Told the client the app would be ready in two weeks. It was running the same afternoon. I never looked back. HTH, --Beman

Daryle Walker wrote:

int const a[] = { 1, 2, 3, 4 }; int const * p = &a[0];

assert( a[p] == 1 );

Hopefully you know that the "a[p]" expression is nonsensical in C++ (or C). The library containers and iterators are (mostly) supposed to act like built-in arrays and pointers. So the dereferencing semantics of STL is kept as close as possible, but no closer, to built-in operations. Note that "p" already has enough information to utilize the first element without involving "a".

Yes, you are right, the container[iterator] doesn't make sense. I'm just longing for the "for (i in map) print i,map[i];" simplicity of awk and other languages. -- Jim Lear

Jim Lear wrote:

The map iterators are really what tripped me up as an STL newbie. One must understand the iterators are implemented as pairs for maps, and pointers for vectors and other things. By providing an "T operator[](iterator)" function for random access and associative containers (and for sequences maybe), one could achieve a consistant interface.

Container-independent code is an impossible and pointless goal. maps have different semantics from other containers. You may want to iterate over just the mapped values, but other people may want to iterate over the keys, or over the pairs (and indeed, so may you, in other part of your program). Who's to say which of these is right? 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: #include "boost/bind.hpp" #include "boost/iterator/transform_iterator.hpp" ... my_map_type map; generic_function_on_iterators( boost::make_transform_iterator( map.begin(), boost::bind(&my_map_type::second, _1), boost::make_transform_iterator( map.end(), boost::bind(&my_map_type::second, _1)); (Unfortunately the return type of boost::bind is unspecified.) It would perhaps be useful for map to have member functions like keys_begin(), keys_end(), etc. <snip>

#include <map> #include <string> #include <iostream>

void main() {

Should return int.

typedef map si_map_t; typedef map ssi_map_t; ssi_map_t table; table["0"]["0"]=20; table["0"]["1"]=21; table["1"]["0"]=10; table["1"]["1"]=11;

for (ssi_map_t::iterator i=table.begin(); i!=table.end(); i++) for (si_map_t::iterator j=i->second.begin(); j!=i->second.end(); j++) cout << j->second << endl; // Blech! :-) This is quite obscure for newbies.

<snip> I realise that pairs don't have very helpful member names, but I really don't think it's that weird for iteration to yield both keys and mapped values. Ben.