Re: [Caml-list] [ANN] The Missing Library

[Jon Harrop <jdh30@cam.ac.uk>]

On Wednesday 28 April 2004 5:31 am, Brian Hurt wrote:
> It's been too long since I've used the STL- what data structures and
> algorithms does it provide?

The main thing is that it is iterator-centric, so you pass iterators around 
instead of containers. For example, to represent a subarray without having to 
copy it. These iterators are classified according to their abilities (e.g. 
trivial, forward, random-access etc.). I think these classifications are 
theoretical - a C++ compiler can't enforce them so if a program misuses an 
iterator then trying to compile it will often produce 10 pages of 
gobbledygook errors pointing into the standard library.

This is quite useful for 1D containers, which the STL provides (list, slist, 
vector, deque), but it doesn't lend itself well to many useful containers 
(trees, matrices, higher-dimensional arrays) which exhibit more interesting 
connectivities than a bidirectional iterator can represent and which do not 
exhibit a clear notion of "sub".

So you get things like an STL set, implemented using red-black trees, which is 
actually an ordered set and which lets you insert and delete elements, 
iterate through them, all the usual stuff. They chose to use semi-inclusive 
bound (e.g. "[a,b)") and, consequently, you typically had an "end" iterator 
which pointed beyond the end of the container (equivalent to the NULL pointer 
in a C list, in raw terms).

I often found myself using a "typedef" to give my current favourite STL 
container a new name which a bunch of my code could then use. When I felt 
that another container type was trendy enough to switch to, I'd just change 
the "typedef" line. That's actually quite useful for trying out different 
data structures for performance etc.

The STL also provided data structures (e.g. valarray, complex) which were 
intended to be used for high-performance numerics. But this was horribly 
misguided as, basically, you can't do decent optimisation on those without 
them being built-in types. The Blitz++ library went some way to addressing 
this by (ab)using the (Turing complete!) template type system to perform 
partial specialisations and AST optimisations on expressions. But then 
everyone realised that was just too nasty, and it died a death.

I'm not saying that these things can't be done in ocaml, just that you can do 
them easily in C++ using the STL. I'd be very interested to hear ocaml 
equivalents though! If you want to know more about the STL then I suggest you 
refer back to Stepanov's ramblings, rather than looking at the "standard" 
which was, unfortunately, bastardised by a committee...

Cheers,
Jon.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners