Where should STL suggestions go?
I know this is not the correct place to suggest new features to the STL, but I can't find a similar group for STL. Any suggestions? Sorry for the interruption. P.S. In case you're wondering what the suggestion is: Add ability to use random access operators with iterators. E.g. vector<int> intv; ... vector<int>::iterator i=intv.begin(); intv[i]++; It seems odd and confusing that iterators have pointer semantics but not random access semantics. -- Jim Lear
I know this is not the correct place to suggest new features to the STL, but I can't find a similar group for STL. Any suggestions?
Sorry for the interruption.
P.S. In case you're wondering what the suggestion is: Add ability to use random access operators with iterators. E.g.
vector<int> intv; ... vector<int>::iterator i=intv.begin(); intv[i]++;
What do you want that last line to do? To me it looks like you could be using "(*i)++;" instead to achieve the same result.
It seems odd and confusing that iterators have pointer semantics but not random access semantics.
they do already, well, some of them at least do (of which, vector is one): http://www.sgi.com/tech/stl/RandomAccessIterator.html. In fact, look in section 4.2 here: http://www.sgi.com/tech/stl/table_of_contents.html... that should answer more questions than I can. -- Matthew Peltzer -- goochrules@gmail.com
goochrules! wrote:
I know this is not the correct place to suggest new features to the STL, but I can't find a similar group for STL. Any suggestions?
Sorry for the interruption.
P.S. In case you're wondering what the suggestion is: Add ability to use random access operators with iterators. E.g.
vector<int> intv; ... vector<int>::iterator i=intv.begin(); intv[i]++;
What do you want that last line to do? To me it looks like you could be using "(*i)++;" instead to achieve the same result.
It seems odd and confusing that iterators have pointer semantics but not random access semantics.
they do already, well, some of them at least do (of which, vector is one): http://www.sgi.com/tech/stl/RandomAccessIterator.html.
Random access iterators do have random access semantics, but that particular expression won't compile with some (mutable) random access iterators. The problem is that the result of p[i] is only required to be convertible to the iterator's value_type. Cheers, -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
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<string, int> si_map_t; typedef map<string, si_map_t> 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.
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
David Abrahams wrote:
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?
I think I've seen them mentioned before but I haven't actually looked into them. I dare say they would be easier to use than what I suggested. Sorry about the duplicate of my message - the local mail server was acting up and I thought the first copy hadn't actually been sent. Ben.
Jim Lear wrote:
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; }
Am I just too ignorant to make any sense? :-) Maybe I'll crawl back into my hole. :-)
You're making sense, but consider this: why should the map get involved in that operation at all when you can do it all with the iterator? Seems like a design flaw to get another object involved needlessly. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
Jim Lear wrote: <snip>
Not only might it be a design flaw, but it may invite inefficiency. But really it's just consistency with other languages which iterate over the keys (like awk)
As you acknowledge, this is inefficient. The keys and mapped values necessarily exist in pairs, so once you've found a key, you've found the mapped value itself. Why bother performing another lookup? C++ is intended to be efficient enough that there's no need for any lower-level language except the odd bit of assembly.
and code clarity. Someone unfamiliar with STL would find the following obvious: for (m_type::iterator i=m.begin();...) for (mi_type::iterator j=m[i].begin();...) cout << m[i][j] << endl; But they may find for (m_type::iterator i=m.begin();...) for (mi_type::iterator j=i->second.begin();...) cout << j->second << endl; obtuse.
But "STL" or rather the corresponding parts of the standard library are a fundamental part of standard C++. Someone who learns C++ should learn how to use these things, and someone who hasn't wouldn't understand either of those!
Perhaps folks intimately familiar with iterators may find this is hard to believe. :-) An alternative question might be, why should one who uses maps and vectors also be required to be familiar with the intricacies of iterators? To me, that seems like a design flaw. I have never encountered another language that requires the user to understand iterators to the extent STL does.
Iterators are what allow you to use generic algorithms on containers (and other kinds of sequence, such as iostreams), where other languages generally limit you to a few specific algorithms built into their containers.
Ease of use and learning ought to be a priority in the design of these objects, to the extent it is efficient and safe. To use iterators in lieu of keys or indices seems to me like a great simplification for users. It completely obviates the need to understand iterators in this case (while still allowing existing iterator functionality).
I suspect it would also lead to great confusion over what iterators are, which I think is fundamentally important to making good use of the standard library. Ben.
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.
Ben Hutchings wrote:
Jim Lear wrote:
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.
I'm beggining to understand that, thanks to everyone's help. These concepts, while superior to the standard programming paradigm, are heavy pre-requisites for programmers to learn (especially old school dummies like yours truly). These prerequisites may be large impedements for people to adopt STL. 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. This would allow people to write useful (albeit bad) STL code quickly, while warning signs point the way to generic programming. But since I've had my generic programming lesson (directly from the experts, no less), I'll embrace the iterator concept and hope that everyone forgets that I ever suggested anything so silly as container[iterator]. :-) Grumble grumble... I always disliked pointer methods for accessing arrays in C... grumble grumble... :-) -- Jim Lear
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
On 12/13/04 5:42 PM, "Jim Lear" <jim.lear@legerity.com> wrote: [SNIP]
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; }
Am I just too ignorant to make any sense? :-) Maybe I'll crawl back into my hole. :-)
As other posters have stated, you're misunderstanding how iterators are used. They gave better explanations, but I'm butting in anyway. An iterator by itself already contains enough information to dereference its pointed-to element, or any sub-part of that element. You're asking for something like: 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". -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
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
On Wed, 15 Dec 2004 10:05:12 -0600, Jim Lear <jim.lear@legerity.com> wrote:
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.
You might be interested in the proposed BOOST_FOREACH then: http://article.gmane.org/gmane.comp.lib.boost.devel/114795 -- Caleb Epstein caleb dot epstein at gmail dot com
Jim Lear wrote:
Caleb Epstein wrote:
Jim Lear wrote:
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.
You might be interested in the proposed BOOST_FOREACH then:
ooooh! That's cool!
Sorry for jumping in late -- I just saw this thread. BOOST_FOREACH has just been put on the formal review queue. See: http://article.gmane.org/gmane.comp.lib.boost.devel/115364 The current implementation, documentation and tests can be found in the Boost Sandbox File Vault. You can download the Zip file here: http://tinyurl.com/57oyp Tinyurl link redirects to: http://boost-sandbox.sourceforge.net/vault/index.php?action=downloadfile&filename=foreach.zip&directory=eric_niebler& I'm told the links don't work for IE users. In that case, go to: http://boost-sandbox.sourceforge.net/vault then eric_niebler, then foreach.zip. -- Eric Niebler Boost Consulting www.boost-consulting.com -- No virus found in this outgoing message. Checked by AVG Anti-Virus. Version: 7.0.296 / Virus Database: 265.6.0 - Release Date: 12/17/2004
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<string, int> si_map_t; typedef map<string, si_map_t> 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.
participants (8)
-
Beman Dawes -
Ben Hutchings -
Caleb Epstein -
Daryle Walker -
David Abrahams -
Eric Niebler -
goochrules! -
Jim Lear