using a binary tree container

[spir]

On 02/11/2011 01:30 PM, Dominic Jones wrote:
> == Quote from bearophile (bearophileHUGS at lycos.com)'s article
>> Dominic Jones:
>>> I have a list of strings and I want to determine whether or not a particular
>>> string in the is in that list.
>> What about using:
>> size_t[sting] yourStringSet;
>> Bye,
>> bearophile
>
> Would that not be constructing an associated array? Whilst an associated array
> would do the job, there is no value for the "key:value" pair, just a list of keys.
> In the C++ STL there are the "set" and "map" containers. I want something like "set".
> Dominic

Precisely. D does not have a Set type yet, at least officially, it's on the way 
(std.container is beeing worked on).

But a very common way to emulate sets in a language that has associative arrays 
is to build a bool[Element] AA, with true values only. Then, your keys are the 
elements, right? Values are just fake, but having them true bools, set[elem] 
returns true if present.
Unfortunately, D would raise an error if absent. But there is even better in D: 
(key in AA) returns a pointer, which is null if absent. Thus, (elem in set) 
correctly simulates test membership.

Note that in various languages (eg Python), builtin or library Set types are 
actually built like that. The reason is AAs are precisely built to make key 
lookup very fast, which is the main operation of a set. I guess (unsure) D's 
future set type will certainly also be built like that. I have one in stock, if 
you're interested.

Denis
-- 
_________________
vita es estrany
spir.wikidot.com