Equivilent of STL Set in D ? ...

[Sean Kelly]

clayasaurus wrote:
> Hello, I am converting some C++ code which happens to use STL Set to D. 
> I was thinking of ways to implement set in D, but since I never got much 
> into STL set in C++ I want to make sure I am thinking right.
> 
> 1) Are D's associative arrays equivalent to STL Set? I've read that Set 
> is pretty much just a sorted associative array, can this functionality 
> be achieved in D (using struct as a key type) by overloading opCmp?

No.  D's associative array is implemented as a hash table, which is 
unordered by nature.  If you require the elements to be sorted you'll 
either have to use a different container or copy the values to an array 
and sort the array before doing whatever you want to do with the sorted 
values.  The word count example does this, for example.

> 2) I suppose I could implement this as a sorted linked list. As far as I 
> can tell set is only being used to hold a collection of elements that 
> are sorted in a certain way.

The C++ set is implemented as a balanced binary tree, and some sort of 
binary tree is probably your best bet if you want a sorted container 
with decent lookup performance.

> 3) Use DTL's implementation of set.

Definitely an option.


Sean