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

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

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]);
}

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

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.

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

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

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?

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.
>
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=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.
>
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

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.