Thread overview | |||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
October 18, 2006 Equivilent of STL Set in D ? ... | ||||
---|---|---|---|---|
| ||||
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 |
October 18, 2006 Re: Equivilent of STL Set in D ? ... | ||||
---|---|---|---|---|
| ||||
Posted in reply to clayasaurus | 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 |
October 19, 2006 Re: Equivilent of STL Set in D ? ... | ||||
---|---|---|---|---|
| ||||
Posted in reply to Sean Kelly | 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 |
October 19, 2006 Re: Equivilent of STL Set in D ? ... | ||||
---|---|---|---|---|
| ||||
Posted in reply to clayasaurus | 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 |
October 19, 2006 Re: Equivilent of STL Set in D ? ... | ||||
---|---|---|---|---|
| ||||
Posted in reply to KlausO | 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
|
October 19, 2006 Re: Equivilent of STL Set in D ? ... | ||||
---|---|---|---|---|
| ||||
Posted in reply to Sean Kelly | 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.
|
October 19, 2006 Re: Equivilent of STL Set in D ? ... | ||||
---|---|---|---|---|
| ||||
Posted in reply to clayasaurus | 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.
|
October 21, 2006 Re: Equivilent of STL Set in D ? ... | ||||
---|---|---|---|---|
| ||||
Posted in reply to Sean Kelly | 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.
|
October 21, 2006 Re: Equivilent of STL Set in D ? ... | ||||
---|---|---|---|---|
| ||||
Posted in reply to KlausO | 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);
|
October 21, 2006 Re: Equivilent of STL Set in D ? ... | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter Bright | 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 |
Copyright © 1999-2021 by the D Language Foundation