I wasn't sure what double-ended versus single-ended meant, and found some answer at the obvious place [1] which mentions Ada.Containers.Vectors is a dynamic array implementation which seems consistent with C++ [2]. While looking around I happened to bump into [3] which was too much for me but may be of interest to anyone playing with data structres. Skimming this shows it discussing efficiency of data structures in functional languages together with lazy variants of imperative language data structures. Would such apply to Smalltalk or is the object-oriented style of Smalltalk considered imperative rather than functional?
The standard tool set - OrderedCollection, Array, etc., are not functional at all - (myArray at: 1 put: 2) mutates myArray, - so I'd put them firmly on the "imperative" side of the fence.
There's nothing stopping one from writing functional data structures - Levente Uzonyi's written some persistent data structures, as have I. ("Persistent" means you get new versions of a data structure; if you hang onto those old versions you can roll back your changes.)
Can you explain a bit more Persistent? Tx
http://www.squeaksource.com/Nutcracker/ is my own play area for these sorts of structures - PersistentUnionFind looks like a functional data structure while internally massively using side effects. http://www.lshift.net/blog/2011/12/31/translating-a-persistent-union-find-fr... has references to the original papers I used for my translation.
Okasaki's book is really good reading, if a bit advanced. It also has a bunch of stuff beyond just showing functional data structures. (Note that the red-black tree implementation is _incomplete_ - he leaves deleting nodes as an exercise for the reader. (See http://matt.might.net/articles/red-black-delete/))
frank
[1] http://en.wikipedia.org/wiki/Double-ended_queue [2] http://en.wikipedia.org/wiki/Sequence_container_%28C%2B%2B%29 [3] http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf