Equivilent of STL Set in D ? ...

clayasaurus clayasaurus at gmail.com
Wed Oct 18 17:41:04 PDT 2006

Sean Kelly wrote:
> 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.

Alright, since Set is a sorted associative container, I mistakenly 
thought it had something to do with an associative arrays.

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

Thanks for the info, so all I have to do is create a balanced binary 
tree with a foreach iterator? :) Seems simple enough.

~ Clay

More information about the Digitalmars-d-learn mailing list