From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id HAA06926; Wed, 28 Apr 2004 07:17:25 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id HAA06914 for ; Wed, 28 Apr 2004 07:17:24 +0200 (MET DST) Received: from ptb-relay02.plus.net (ptb-relay02.plus.net [212.159.14.213]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i3S5HNYM016236 for ; Wed, 28 Apr 2004 07:17:23 +0200 Received: from [80.229.56.224] (helo=chetara) by ptb-relay02.plus.net with esmtp (Exim) id 1BIhRj-000GKg-42 for caml-list@inria.fr; Wed, 28 Apr 2004 05:17:23 +0000 From: Jon Harrop Organization: University of Cambridge To: caml-list@inria.fr Subject: Re: [Caml-list] [ANN] The Missing Library Date: Wed, 28 Apr 2004 06:13:19 +0100 User-Agent: KMail/1.5.4 References: In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200404280613.19547.jdh30@cam.ac.uk> X-Miltered: at concorde by Joe's j-chkmail ("http://j-chkmail.ensmp.fr")! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 2004:99 iterator:01 deque:01 exhibit:01 iterator:01 exhibit:01 implemented:01 red-black:01 realised:01 equivalents:01 arrays:01 compiler:01 typedef:01 typedef:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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