digitalmars.D.learn - C++ Container equivalents
- Bruce Adams (37/37) Aug 14 2007 Hi,
- Carlos Santander (8/58) Aug 14 2007 Tango has the tango.util.collection package.
- Downs (107/110) Aug 14 2007 This is kind of embarrassing, because there's no such thing as sets in
- Bill Baxter (19/26) Aug 14 2007 Yes the situation is pretty sad. D - the language with built-in arrays
- Bruce Adams (8/40) Aug 15 2007 What's worse than having this defect is burying it.
- Christian Kamm (5/8) Aug 16 2007 I like those changes, so I took the liberty of changing ArcLib's copy to
- Bill Baxter (4/14) Aug 16 2007 Cool. And thanks to you ArcLib folks for making it available in the
- Bruce Adams (2/18) Aug 16 2007 Great to watch the open source process at work :)
- Tomas Lindquist Olsen (3/3) Aug 14 2007 Stewart Gordon posted his version of this not too long ago:
- Bruce Adams (7/10) Aug 15 2007 Quoting from that page:
- Jascha Wetzel (6/10) Aug 15 2007 what he means is probably that a hash table implementation doesn't need
- Henning Hasemann (7/12) Aug 15 2007 Thanks for that info, I always asked myself why they need both, too :)
- Brad Roberts (7/17) Aug 15 2007 Careful, that's not quite correct. D's builtin associate arrays use a
- Henning Hasemann (17/17) Aug 15 2007 As said before the situation is bad, but allows for re-inventing the
- Bill Baxter (4/21) Aug 15 2007 Well, post a link for goodness sake!
- Henning Hasemann (7/9) Aug 15 2007 Ill try to bring up my website this week, then I'll post it on announce.
- Jascha Wetzel (7/7) Aug 15 2007 i'll throw in
- Deewiant (4/4) Aug 15 2007 An old binary heap I used as a priority queue:
- Sean Kelly (20/31) Aug 15 2007 Tango has some containers that are roughly equivalent to those in the
- Deewiant (5/11) Aug 15 2007 It might be worth it adding the big O notation anyway: if you know what ...
- Bruce Adams (14/27) Aug 15 2007 Off topic but what I'd love to see is complexity constraints.
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?
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.
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.
I've seen references to dtl and minTL. dtl is apparently 'resting'.
The link to minTL seems to be broken.
Ideally I want to use something that is a sanctioned part of D/Phobos
or likely to become so.
Who can point me in the right directions?
Regards,
Bruce.
I've pasted the complete list from the SGI site and filled in
what I can which is almost nothing.
Sequences:
vector - D (dynamic) array
deque - D (dynamic) array?
list
slist
bit_vector
Associative Containers:
set
map - D associative array (strictly a hash
map)
multiset
multimap
hash_set
hash_map - D associative array
hash_multiset
hash_multimap
hash
basic_string - D array (char[])
rope
Aug 14 2007
Carlos Santander <csantander619 gmail.com>
Bruce Adams escribió:
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?
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.
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.
I've seen references to dtl and minTL. dtl is apparently 'resting'.
The link to minTL seems to be broken.
Ideally I want to use something that is a sanctioned part of D/Phobos
or likely to become so.
Who can point me in the right directions?
Regards,
Bruce.
I've pasted the complete list from the SGI site and filled in
what I can which is almost nothing.
Sequences:
vector - D (dynamic) array
deque - D (dynamic) array?
list
slist
bit_vector
Associative Containers:
set
map - D associative array (strictly a hash
map)
multiset
multimap
hash_set
hash_map - D associative array
hash_multiset
hash_multimap
hash
basic_string - D array (char[])
rope
Tango has the tango.util.collection package.
There is also the MinTL library (I don't have the link to it ATM). I think
someone updated it fairly recently, but I'm not completely sure.
I think there are more options out there, but those are the only two I can
think
of right now. Check the Wiki for more about that.
--
Carlos Santander Bernal
Aug 14 2007
Bruce Adams wrote: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.This is kind of embarrassing, because there's no such thing as sets in D, natively. The closest you can come is probably bool[Type], that is, an associative array. Regarding lists, here's a proto-implementation I threw together. Basic functionality is missing, but you should get the idea. The actual struct is Phobos/Tango-agnostic. Have fun! --downs struct list(T) { private { static struct entry { T value=void; entry *next=null, prev=null; } entry *first=null, last=null; void update(bool left)(entry *e, entry *newEntry) { static if(left) { if (e==first) first=newEntry; else { e.prev.next=newEntry; newEntry.prev=e.prev; } } else { if (e==last) last=newEntry; else { e.next.prev=newEntry; newEntry.next=e.next; } } // at this point we have effectively removed e. // but we keep it around to prevent the GC from wailing in anguish // delete e; } } static list opCall(T[] init) { list res; foreach (entry; init) res.push_back(entry); return res; } static list opCall(entry *a, entry *b) { list res=void; res.first=a; res.last=b; return res; } void push(bool front)(T what) { auto newEntry=new entry; newEntry.value=what; static if (front) { if (first) { newEntry.next=first; first.prev=newEntry; } first=newEntry; if (!last) last=first; } else { if (last) { newEntry.prev=last; last.next=newEntry; } last=newEntry; if (!first) first=last; } } bool opEquals(T[] comp) { size_t count=0; foreach (entry; *this) { if (count==comp.length) return false; if (comp[count++]!=entry) return false; } if (count!=comp.length) return false; return true; } list opSlice(size_t from, size_t to) { entry *start=first; while (from--) { start=start.next; to--; } entry *end=start; while (--to) end=end.next; return list(start, end); } void opSliceAssign(list what, size_t from, size_t to) { entry *start=first; while (from--) { start=start.next; to--; } entry *end=start; while (--to) end=end.next; update!(true)(start, what.first); update!(false)(end, what.last); } int opApply(int delegate(ref T) dg) { entry *current=first; writefln("_____"); scope(exit) writefln("'''''"); while (true) { writefln("Entry ", current.value); auto res=dg(current.value); if (res) return res; if (current==last) return 0; current=current.next; } } int opApply(int delegate(ref size_t, ref T) dg) { size_t count=0; foreach (ref entry; *this) { auto res=dg(count, entry); ++count; if (res) return res; } return 0; } alias push!(true) push_front; alias push!(false) push_back; size_t length() { size_t res=0; foreach (bogus; *this) ++res; return res; } T[] toArray() { auto res=new T[length]; foreach (id, entry; *this) res[id]=entry; return res; } } import std.stdio; void main() { list!(int) test; test.push_back(5); test.push_front(4); test.push_back(8); writefln(test.toArray); assert(test==[4, 5, 8]); writefln(test[1..2].toArray); assert(test[1..2]==[5]); test[1..2]=list!(int)([6, 7]); writefln(test.toArray); assert(test==[4, 6, 7, 8]); }
Aug 14 2007
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?
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.
Yes the situation is pretty sad. D - the language with built-in arrays
and hashes, and meta-programming facilities that make little girls cry,
but forget it if you're looking for a simple Set type.
The closest thing to "official" container classes is what's in Tango.
Nothing is going to be added to Phobos as far as I know. Walter just
doesn't have time for it. But Walter is also unwilling to loosen the
reigns, so basically Phobos is going nowhere any time soon.
Hopefully discussions at the D conference will help point the way to a
solution to the library predicament D's in.
Anyway, here are some set-like things I have sitting around:
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
http://www.billbaxter.com/projects/d/sets.d)
I also have a class wrapper around an associative array that adds things
to make it more set-like.
(http://www.billbaxter.com/projects/d/aa_set.d)
--bb
Aug 14 2007
Bill Baxter Wrote:Bruce Adams wrote:What's worse than having this defect is burying it. Amazingly its not a bugzilla issue - it is now http://d.puremagic.com/issues/show_bug.cgi?id=1420Hi, 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? 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.Yes the situation is pretty sad. D - the language with built-in arrays and hashes, and meta-programming facilities that make little girls cry, but forget it if you're looking for a simple Set type.The closest thing to "official" container classes is what's in Tango. Nothing is going to be added to Phobos as far as I know. Walter just doesn't have time for it. But Walter is also unwilling to loosen the reigns, so basically Phobos is going nowhere any time soon.Walter needs to delegate.Hopefully discussions at the D conference will help point the way to a solution to the library predicament D's in.At least its only a week away.Anyway, here are some set-like things I have sitting around: 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 http://www.billbaxter.com/projects/d/sets.d) I also have a class wrapper around an associative array that adds things to make it more set-like. (http://www.billbaxter.com/projects/d/aa_set.d) --bb
Aug 15 2007
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.dI 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
Aug 16 2007
Christian Kamm wrote:Cool. And thanks to you ArcLib folks for making it available in the first place. --bbArclib 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.dI 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
Aug 16 2007
Bill Baxter Wrote:Christian Kamm wrote:Great to watch the open source process at work :)Cool. And thanks to you ArcLib folks for making it available in the first place. --bbArclib 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.dI 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
Aug 16 2007
Stewart Gordon posted his version of this not too long ago: http://pr.stewartsplace.org.uk/d/sutil/ they seem pretty nice and use phobos.
Aug 14 2007
Tomas Lindquist Olsen Wrote:Stewart Gordon posted his version of this not too long ago: http://pr.stewartsplace.org.uk/d/sutil/ they seem pretty nice and use phobos.Quoting from that page: "datetime A set of object-oriented date and time types serving as an alternative to std.date." 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?
Aug 15 2007
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.
Aug 15 2007
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
Aug 15 2007
On Wed, 15 Aug 2007, Jascha Wetzel wrote:Bruce Adams wrote: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, BradHashmap "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.
Aug 15 2007
As said before the situation is bad, but allows for re-inventing the wheel with a good excuse (the dream of all coders ;-)). I have written: - a double linked list - a dobule linked list that stays sorted - a set (based on hashmap over bool) - a heap - an implementation of the dijkstra algorithm - Iterator classes/Interfaces naturally all fitting together. Since I coded just what I needed for my current project, you would maybe miss some functionality but if you can use any of it, Im happy to share. 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
Aug 15 2007
Henning Hasemann wrote:As said before the situation is bad, but allows for re-inventing the wheel with a good excuse (the dream of all coders ;-)). I have written: - a double linked list - a dobule linked list that stays sorted - a set (based on hashmap over bool) - a heap - an implementation of the dijkstra algorithm - Iterator classes/Interfaces naturally all fitting together. Since I coded just what I needed for my current project, you would maybe miss some functionality but if you can use any of it, Im happy to share. HenningWell, post a link for goodness sake! :-) --bb
Aug 15 2007
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
Aug 15 2007
i'll throw in - an AVL tree - a doubly linked list - a stack - a queue - two poor sets http://mainia.de/container.d
Aug 15 2007
An old binary heap I used as a priority queue: -- Remove ".doesnotlike.spam" from the mail address.
Aug 15 2007
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
Aug 15 2007
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.
Aug 15 2007
Deewiant Wrote:Sean Kelly wrote: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.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.
Aug 15 2007