Equivilent of STL Set in D ? ...
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.
More information about the Digitalmars-d-learn