C++ Container equivalents

[Sean Kelly]

Bruce Adams wrote:
> Hi,
>     I'm sure these questions come up twice a day and yet there isn't a definitive page on the digital mars website or wiki4d that I can find.
> (I'd add it myself if I knew the answers and I could figure out how to use wiki4d).
> What are the best D equivalents to the STL containers?

Tango has some containers that are roughly equivalent to those in the 
STL.  They're a prt of Doug Lea's container library for Java.  To be 
honest, however, I think the design could be more D-like, and I want to 
review the design when I get a chance.  And being from a C++ background, 
that may mean an interface a bit more like the STL as well.

> bearing in mind the algorithmic complexity of various kinds of
> operation. I haven't actually seen a statement of what complexity
> operations on D arrays is.

Tango has a module containing array algorithms in tango.core.Array. 
Unlike the C++ spec however, algorithm complexity is stated in plain 
language rather than in big-O terms.  find(), for example, "performs a 
"linear scan of buf from [0 .. buf.length)," which implies that it has 
O(N) complexity.

> Most of the time D arrays should be enough. In C++ I end up using
> vector, map and set the most. The set is the main one I want
> to identify an equivalent to.

You can use the built-in AA as a set by mapping the value you care about 
to bool, unless sort order is important.  Also, I believe the Tango set 
is called "TreeBag."

> I've seen references to dtl and minTL. dtl is apparently 'resting'.

dtl was very promising but has been shelved basically indefinitely 
because Matthew is busy with other things.  However, I think the concept 
of ranges it contains would be a useful asset to any container package 
in D.  Whenever I get to look at Tango's containers, I want to do so in 
light of the ideas in dtl.


Sean