Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search

[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): Robert