i'll throw in
- an AVL tree
- a doubly linked list
- a stack
- a queue
- two poor sets

http://mainia.de/container.d

Jascha Wetzel <"[firstname]"@mainia.de> wrote:
> what he means is probably that a hash table implementation doesn't need an ordering comparator, only equality. D's associative arrays are implemented as binary search trees with hash keys as index values. like this it needs both: ordering for the tree search and equality due to the non-injective hashing.

Thanks for that info, I always asked myself why they need both, too :)

Henning

-- 
GPG Public Key: http://keyserver.ganneff.de:11371/pks/lookup?op=get&search=0xDDD6D36D41911851 Fingerprint: 344F 4072 F038 BB9E B35D  E6AB DDD6 D36D 4191 1851

An old binary heap I used as a priority queue:

http://www.dsource.org/projects/tango/forums/topic/163#703

-- 
Remove ".doesnotlike.spam" from the mail address.

> Well, post a link for goodness sake!
> :-)

Ill try to bring up my website this week, then I'll post it on announce.

Henning

-- 
GPG Public Key: http://keyserver.ganneff.de:11371/pks/lookup?op=get&search=0xDDD6D36D41911851 Fingerprint: 344F 4072 F038 BB9E B35D  E6AB DDD6 D36D 4191 1851

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

Sean Kelly wrote:
> 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.
> 

It might be worth it adding the big O notation anyway: if you know what it means, it's quicker to scan for and interpret than a full-sentence explanation.

-- 
Remove ".doesnotlike.spam" from the mail address.

On Wed, 15 Aug 2007, Jascha Wetzel wrote:

> Bruce Adams wrote:
> > Hashmap "Unlike DMD's dodgy associative array implementation, it doesn't rely on an ordering comparator"
> > 
> > What's wrong with std.date and whats dodgey about associative arrays?
> 
> what he means is probably that a hash table implementation doesn't need an ordering comparator, only equality. D's associative arrays are implemented as binary search trees with hash keys as index values. like this it needs both: ordering for the tree search and equality due to the non-injective hashing.

Careful, that's not quite correct.  D's builtin associate arrays use a binary-tree only for buckets, not for the entire table.  The requirement is the same, but the suggestion that it's not a hash table but rather a simple binary-tree isn't correct.

Later,
Brad

Deewiant Wrote:

> Sean Kelly wrote:
> > 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.
> > 
> 
> It might be worth it adding the big O notation anyway: if you know what it means, it's quicker to scan for and interpret than a full-sentence explanation.
> 
> -- 
> Remove ".doesnotlike.spam" from the mail address.

Off topic but what I'd love to see is complexity constraints. Something like:

void function(int[] array)
{
   invariant {
      static assert(complexity(thisFunc) == constantTime);
   }
   foreach(x; array) {   // contraint failed - foreach implies O(n)
   }
}

In practice a compiler could only work out some simple cases of complexity constraint violation but even where it can't the assertion provides useful documentation.

> Arclib has a RedBlackTree class, and I made some changes to that for my own purposes. It implements set and multiset. http://www.billbaxter.com/projects/d/redblacktree.d

I like those changes, so I took the liberty of changing ArcLib's copy to
your version, modified for tango.
http://www.dsource.org/projects/arclib/browser/trunk/arc/templates/redblacktree.d

Cheers,
Christian

Christian Kamm wrote:
>> Arclib has a RedBlackTree class, and I made some changes to that for my
>> own purposes. It implements set and multiset.
>> http://www.billbaxter.com/projects/d/redblacktree.d
> 
> I like those changes, so I took the liberty of changing ArcLib's copy to
> your version, modified for tango.
> http://www.dsource.org/projects/arclib/browser/trunk/arc/templates/redblacktree.d
> 
> Cheers,
> Christian

Cool.  And thanks to you ArcLib folks for making it available in the first place.

--bb