Re: Linearity of the STL containers and iterators (was: Re: std::string bad design????)
Seungbeom Kim wrote:
Le Chaud Lapin wrote:
You should try the iterators-state-in-the-container model. Everyone I
have met who has experience the pleasure of not having to create an
iterator to go with a container has raved about it, from students to
colleagues. It's addictive, and especially attractive when you are
iterating over a container that is 3-levels deep inside nested
containers.
So, what is it exactly, and what benefit does it give?
Just a historical note, but if you go back fifteen or more
years, you'll find that a lot of containers written then did use
internal iterators. If you don't find them today, it's largely
because experience showed them to be a bad idea.
[...]
is the notion
that all containers are linear, in the "movement" of the iterator is 1
dimensional.
Containers don't have to be linear, even though the current standard
library offers linear containers only.
In a very real sense, std::set and std::map aren't linear. A
standard iterator imposes a linearity in the access of the
elements, but that is, IMHO, part and parcel of the definition
of "iterator".
Obviously, there are other ways to access a collection of data.
Iterators are only a possibility; you don't have to use them
when they aren't appropriate.
The STL style doesn't preclude
more complex, non-linear containers such as the graphs provided by the
Boost Graph Library.
However, I believe iterators have to be linear, because every processing
is inherently linear at some level (without considering concurrency, of
course). In the sense that even if you do a breadth-first search on a
graph, you cannot visit two successors of a node at the same time but
you should visit one first and the other later. That can certainly
modelled as linear.
And don't forget that one container can provide many different kinds of
iterators; you can have iterators for preorder traversal and postorder
traversal on a tree, for example.
Where the idiom breaks down is when the next element to be
visited depends on the evaluation of the current element.
--
James Kanze (Gabi Software) email: james.kanze@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, France, +33 (0)1 30 23 00 34
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]