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?

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.

3) Use DTL's implementation of set.

Thanks.
~ Clay

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

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

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

Nova contains an intrusive red/black tree implementation:

http://www.dsource.org/projects/nova/browser/trunk/NOVA/DS/intrusive/redblacktree.d

Klaus

KlausO wrote:
> clayasaurus wrote:
>>
>> Thanks for the info, so all I have to do is create a balanced binary tree with a foreach iterator? :) Seems simple enough.
>>
>> ~ Clay
> 
> Nova contains an intrusive red/black tree implementation:
> 
> http://www.dsource.org/projects/nova/browser/trunk/NOVA/DS/intrusive/redblacktree.d 
> 
> 
> Klaus

Sounds interesting... I posted some questions on your forum. Thanks.
~ Clay

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

Suppose that I don't need sorting, would an associative array work just as well? I'm looking at the code again and it isn't very clear that sorting is a requirement, just that I need to have fast insert, lookup (and if not in container, add it), and deletion.

Then again, if all that was needed was a hashmap, then I wonder why the author didn't use STL map.

clayasaurus wrote:
> 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.
>>
> 
> Suppose that I don't need sorting, would an associative array work just as well? I'm looking at the code again and it isn't very clear that sorting is a requirement, just that I need to have fast insert, lookup (and if not in container, add it), and deletion.
> 
> Then again, if all that was needed was a hashmap, then I wonder why the author didn't use STL map.

iirc stl's map are sorted too, and also use rb-tree usually as implementation. I think a set in STL is a subset of a map. There is no hashmap in standard (98) C++.
So for insert, lookup and deletion a set makes sense in STL.

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

C++'s balanced binary trees are red-black trees. I had just proposed that someone do a red-black tree implementation for D. It's not hard, the algorithms are well known. It just takes a little time to sit down and do it.

KlausO wrote:
> clayasaurus wrote:
>>
>> Thanks for the info, so all I have to do is create a balanced binary tree with a foreach iterator? :) Seems simple enough.
>>
>> ~ Clay
> 
> Nova contains an intrusive red/black tree implementation:
> 
> http://www.dsource.org/projects/nova/browser/trunk/NOVA/DS/intrusive/redblacktree.d 

Looks like you've already done it! It seems a little complex to use, however. It shouldn't be necessary to define new classes/structs in order to use it. I should be able to just:

import whatever.redblacktree;

RedBlackTree(char[], int) foo;	// create a red-black tree with key type of char[] and value type of int.

...
foo["hello"] = 3;
foo["betty"] = 25;
bar(foo["hello"]);	// bar(3)
foo.remove("betty"));
...
foreach (v; foo)
	writefln("value is %s", v);

Walter Bright wrote:
> 
> Looks like you've already done it! It seems a little complex to use, however. It shouldn't be necessary to define new classes/structs in order to use it. 

That's because it's the intrusive form of a red black tree.

Clay had some questions about them I tried to answer:
http://www.dsource.org/forums/viewtopic.php?t=1959

> I should be able to just:
> 
> import whatever.redblacktree;
> 
> RedBlackTree(char[], int) foo;    // create a red-black tree with key 

:-) I guess you meant
  RedBlackTree!(char[], int) foo;

> type of char[] and value type of int.
> 
> ...
> foo["hello"] = 3;
> foo["betty"] = 25;
> bar(foo["hello"]);    // bar(3)
> foo.remove("betty"));
> ...
> foreach (v; foo)
>     writefln("value is %s", v);

Seems to be an interesting task to get used to the new foreach
features. I'll give it a try.

Klaus