www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - C++ Container equivalents

reply Bruce Adams <tortoise_74 no.yahoo.spam.co.uk> writes:
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
next sibling parent Carlos Santander <csantander619 gmail.com> writes:
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
prev sibling next sibling parent Downs <default_357-line yahoo.de> writes:
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
prev sibling next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
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
next sibling parent Bruce Adams <tortoise_74 spam.no.yahoo.co.uk> writes:
Bill Baxter Wrote:

 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.

Amazingly its not a bugzilla issue - it is now http://d.puremagic.com/issues/show_bug.cgi?id=1420
 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 15 2007
prev sibling parent reply Christian Kamm <kamm.incasoftware shift-at-left-and-remove-this.de> writes:
 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
Aug 16 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
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
Aug 16 2007
parent Bruce Adams <tortoise_74 ya.hoo.no.sp.amme.co.uk> writes:
Bill Baxter Wrote:

 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

Great to watch the open source process at work :)
Aug 16 2007
prev sibling next sibling parent reply Tomas Lindquist Olsen <tomas famolsen.dk> writes:
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
next sibling parent reply Bruce Adams <tortoise_74 spam.no.yahoo.co.uk> writes:
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
parent Jascha Wetzel <"[firstname]" mainia.de> writes:
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
prev sibling parent Brad Roberts <braddr puremagic.com> writes:
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
Aug 15 2007
prev sibling next sibling parent reply Henning Hasemann <hhasemann web.de> writes:
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
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
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.
 
 Henning
 

Well, post a link for goodness sake! :-) --bb
Aug 15 2007
prev sibling next sibling parent Jascha Wetzel <"[firstname]" mainia.de> writes:
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
prev sibling next sibling parent Henning Hasemann <hhasemann web.de> writes:
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
prev sibling next sibling parent Deewiant <deewiant.doesnotlike.spam gmail.com> writes:
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.
Aug 15 2007
prev sibling next sibling parent Henning Hasemann <hhasemann web.de> writes:
 
 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
prev sibling parent reply Sean Kelly <sean f4.ca> writes:
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
parent reply Deewiant <deewiant.doesnotlike.spam gmail.com> writes:
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
parent Bruce Adams <tortoise_74 nospam.ya.hoo.co.mapson.uk> writes:
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.
Aug 15 2007