Re: [boost] Re: (infinite) sequences using recurrence relations

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-08-07 17:10:27

Eric Ford wrote:

> Ok, I'm definitely confused.  I guess I don't understand how to
> reconsile "Containers are not part of stl" with "There are rules in
> the standard [for containers?] because the containers have to have
> requirements.".  

        History. Standard Template Library does not mean
'all the templates in the C++ Library', it is a library
of _algorithms_ characterized by using iterators as
parameters. The containers are irrelevant to this library:
the whole point of STL is that it is container independent.
The set of algorithms is also much bigger than those actually
Standardised (about 2/3 of the algorithms were thrown out
to keep C++ small :-)

        Of course, you need to have a way to make iterators
for the algorithms to work on. The two common ways are
to use concrete data structures (containers) and iterator
adaptors. So the algorithms aren't that useful without
containers, but the set of algorithms is small, whereas
the set of containers is effectively infinite: just a couple
of examples are thrown into the C++ Standard Library to
keep people happy.

        In practice, people use containers heavily,
and avoid algorithms, because the C++ core language
just doesn't have what it takes to do generic
programming. In languages (typically functional languages)
that have first class anonymous higher order functions,
almost all the work is done with algorithms, the containers
are usually trivial data structures (like lists) that are
barely worth Standardising: eg ML list:

        type 'a list = Empty | Cons of 'a * 'a list

Its a one liner. But you can write a LOT of algorithms
using it -- see LISP :-)

        To really understand all this: you can completely
forget about container requirements, because they aren't
relevant. The ONLY thing that matters about containers
is the functions used to produce the iterators: the iterators
have to obey strict rules for the algorithms to work.
The containers themselves just don't matter.

        As an example: the prototypical container
is the C array. Yet it doesn't obey sequence requirements?
Who cares?
        T a[n];
        a, a+i // i<=n

are a pair of valid iterators. That's all that matters.

-- 
John (Max) Skaller, mailto:skaller_at_[hidden] 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net