🚀 go-pugleaf

In article <40c8ot$q00@metro.ucc.su.OZ.AU> maxtal@Physics.usyd.edu.au
(John Max Skaller) writes:

|> In article <1995Aug4.165955@opal.tufts.edu>,
|> Jonathan Borden <jkauer@opal.tufts.edu> wrote:
|> >In article <3vo8a7$jde@metro.ucc.su.OZ.AU>, maxtal@Physics.usyd.edu.au (John Max Skaller) writes:
|> >> 	valarray isn't an STL container because its purpose is
|> >> quite different. Here's my picture:
|> >> 
|> >> 	STL is based on the notion that everything can be organised
|> >> into sequences: these sequences are represented by pairs of iterators.
|> >> There are no trees in STL because a tree isn't a linear sequence.
|> >
|> >	hmmm... what about maps & sets, the hp implementation (and hence
|> >many derivatives) code these as red-black trees. In STL there are several
|> >types of iterators, a sequential iterator is one type, however, random access
|> >iterators also exist.

|> 	Perhaps I didn't explain well. Random access iterators indeed
|> exist, as does a container "set". But a random access is a shorthand
|> for sequential access, and an associative lookup is a shorthand
|> for a search of a linearly ordered set of elements.

|> 	That is, a set is first and foremost a sequence in which
|> inserting a new element automatically positions the element in
|> the "right" place in the sequence, as is a map: these things are "subtypes" 
|> of "sequences", that is, some of the methods can be made faster
|> (or are even possible) because they maintain stricter invariants
|> that the most basic linear access requirement. (sequential iteration)

Perhaps you should be more precise, and state that in the STL
implementation...

In my own implementation of sets and maps (done long before STL came
along), they are not sequences, and there is nothing in the concept
that imposes sequenciality on a set.

Formally, the presence of an iterator doesn't impose a linear
ordering, either, although I know of no implementation that would not
result in a (generally arbitrary) linear ordering.  (In my
implementation, for example, running the iterator over the same set
twice will result in visiting the members in the same order.  This is
an artifice of the implementation, however, and is not intrinsic in
the definition of iterator, at least, not in the definition I use.)

|> >> 	Why just sequences? The answer is that that is all that
|> >> a single thread of control can handle. Even conceptually parallel
|> >> processes must be organised into _some_ sequence for a conventional
|> >> computer to use it.
|> >> 
|> >	Since STL in fact supports more than lists and vectors as containers
|> >this answer does not follow. I'm not sure that STL references types of CPU's
|> >at all.

|> 	A vector is a sequence, obviously. So is a list.
|> 	The very notion of iteration is inherently a question of
|> enumerating things: linearity.

I would disagree, at least for the meaning we normally give to
`iterator' in this context.  An iterator does not formally impose an
ordering.  In particular, in my implementation of SetOf (which uses
open hashing), if an element is inserted while an iterator is active,
it is undefined whether the element will be considered before or after
the iterator.

-- 
James Kanze         Tel.: (+33) 88 14 49 00        email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils en informatique industrielle --
                              -- Beratung in industrieller Datenverarbeitung