[REBOL] Re: COLLECTing results
From: robert:muench:robertmuench at: 28-Jul-2003 10:16
> -----Original Message-----
> From: [rebol-bounce--rebol--com] [mailto:[rebol-bounce--rebol--com]]
> On Behalf Of Gregg Irwin
> Sent: Thursday, July 24, 2003 4:36 PM
> To: Robert M. Muench
> Subject: [REBOL] Re: COLLECTing results
> Smalltalk has similar concepts, and of course these types of
> things are often taught in conjunction with Lisp, Scheme, and
> other functional languages. Lots of places to draw inspiration from.
Hi, right. The STL is a quite different concept if you see it the first
time but the idea is very cute. I just want to give you some ramp-up to
it. The first thing the STL does, is separating algorithms from
data-structures. Next it defines a set of operators that can be used in
an abstract way:
sort(first, last, greater<T>());
Here, 'sort is the algorithm. 'first and 'last are pointers to the first
and last object of a datastructure. 'sort will iterate linear from
'first to 'last. The iteration to the next element is abstracted and the
implementation of the data-structure must know how to iterate from
'first to 'last. So 'sort just uses a function like 'next-element,
however this is implemented (in C++ this is done by pointer arithmetic).
The next thing is 'greater. This is the compare operator 'sort is going
to use. 'greater is type independent, you will specify the actual type
through 'T. The nice thing about the STL is, that there exists a bunch
of those functionids (IIRC that's what those things are called). So we
could even have used 'less<T> or whatever we define.
Further some info from some old FAQ:
What are containers?
Containers include such things as vectors, lists, queues,
priority queues, stacks, maps, and sets. In STL,
containers (data structures) are templatized. For
example, the stack class may be used with integers,
doubles, and user defined types.
What are iterators?
Iterators may be thought of as the key to STL, acting
as an intermediary between the algorithms and the
containers. You are already familiar with the concept
of an iterator when you think of the pointer used to
traverse an array. Iterators are objects in STL.
One may think of them as a finger moving across the
elements of a container. The five categories of
iterators are:
Random Access -> Bidirectional-> Forward -> Input
-> Output
How are iterators related to containers and algorithms?
One may think of each container and each algorithm as
being associated with a certain iterator. A vector has
a random access iterator, therefore it may use a random
access algorithms such as a sort. A container may use
any algorithm associated with its iterator or any
algorithm associated with an iterator to the right of
it in the above diagram. Therefore a vector (random
access iterator) may use algorithms associated with
bidirectional, forward, input or output iterators.
Can a vector be used with the binary_search algorithm
(takes a forward iterator) ? If we look at the diagram
above, forward is to the right of random access,
therefore we may use binary_search with a vector
container. Can a vector be used with copy (takes an
input and an output iterator)? Since input and output
are to the right of random access, vector may used
with copy.
There are quite a number of algorithms in STL,
including count(), copy(), replace( ), reverse( ), ...
Just as each container is associated with a certain
iterator, each algorithm is also associated with a
certain iterator(s).
count( ) - input iterator
copy ( ) - input and output iterator
replace( ) - forward iterator
reverse( ) - bidirectional iterator
Finally here are some links to get more about the idea (don't know if
all are still alive):
http://www.boost.org/
http://www.stlport.org/
http://www.sgi.com/Technology/STL/index.html
http://www.metabyte.com/~fbp/stl/effort.html
http://www.mindspring.com/~fluxsmith/Programming/library.html
http://www.sirius.com/~ouchida/
Robert
