August 15, 2007 Re: C++ Container equivalents | ||||
---|---|---|---|---|
| ||||
Posted in reply to Bruce Adams | i'll throw in - an AVL tree - a doubly linked list - a stack - a queue - two poor sets http://mainia.de/container.d |
August 15, 2007 Re: C++ Container equivalents | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jascha Wetzel | 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 |
August 15, 2007 Re: C++ Container equivalents | ||||
---|---|---|---|---|
| ||||
Posted in reply to Bruce Adams | 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. |
August 15, 2007 Re: C++ Container equivalents | ||||
---|---|---|---|---|
| ||||
Posted in reply to Bill Baxter | > 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 |
August 15, 2007 Re: C++ Container equivalents | ||||
---|---|---|---|---|
| ||||
Posted in reply to Bruce Adams | 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 |
August 15, 2007 Re: C++ Container equivalents | ||||
---|---|---|---|---|
| ||||
Posted in reply to Sean Kelly | 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. |
August 15, 2007 Re: C++ Container equivalents | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jascha Wetzel | 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
|
August 15, 2007 Re: C++ Container equivalents | ||||
---|---|---|---|---|
| ||||
Posted in reply to Deewiant | 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.
|
August 16, 2007 Re: C++ Container equivalents | ||||
---|---|---|---|---|
| ||||
Posted in reply to Bill Baxter | > 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 |
August 16, 2007 Re: C++ Container equivalents | ||||
---|---|---|---|---|
| ||||
Posted in reply to Christian Kamm | 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
|
Copyright © 1999-2021 by the D Language Foundation