Hello,

I have a list of strings and I want to determine whether or not a particular string in the is in that list. Assuming I should store the list of strings in a binary tree to facilitate fast searching, I had a look at the std.container documentation and found RedBlackTree, but the documentation for it has no examples. May someone offer an example of how to use it?

Thank you,
Dominic Jones

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

On 02/11/2011 01:05 PM, bearophile wrote:
> 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

bool[st<r>ing] yourStringSet;

does the job and better matches semantics

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

== Quote from bearophile (bearophileHUGS@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

Dominic Jones:

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

Phobos2 is young, and it doesn't contain a HashSet yet. So you may use built-in associative arrays as a set, with a default value, or you may use the Ordered Tree Set that's in the collections module (look at the its unittests for some usage examples), or you may write a HashSet and then put it in Bugzilla so if it's good enough it will be added to Phobos. My suggestion is to use the built-in associative array.

Bye,
bearophile

On 02/11/2011 01:30 PM, Dominic Jones wrote:
> == Quote from bearophile (bearophileHUGS@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

On 02/11/2011 06:55 PM, spir wrote:
> On 02/11/2011 01:30 PM, Dominic Jones wrote:
>> == Quote from bearophile (bearophileHUGS@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

By the way, i may be wrong on that, but D's builtin AAs seem /very/ fast on key access. You'd probably have a hard time even approaching their performance using whatever kind of tree (or rather, of trie). I tried ;-) Both with string and bit-seq keys (in the latter case, thus using a bit-trie). If ever you have any good result on this path, I am very interested.

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

what with this?:
	auto arr = ["foo", "bar", "aaa", "zzz"];
	sort(arr);
	assert(canFind("foo"));
	assert(canFind("aaa"));
	assert(!canFind("aa"));
I had a "Error	1	Error: module algorithem is in file 'std\algorithem.d' which
cannot be read	main.d	"
when I tried to compile, so I couldn't check it.

On 02/11/2011 08:46 PM, Tom wrote:
> what with this?:
> 	auto arr = ["foo", "bar", "aaa", "zzz"];
> 	sort(arr);
> 	assert(canFind("foo"));
> 	assert(canFind("aaa"));
> 	assert(!canFind("aa"));
> I had a "Error	1	Error: module algorithem is in file 'std\algorithem.d' which
> cannot be read	main.d	"
> when I tried to compile, so I couldn't check it.

canFind is in std.algorithm: import it. (with the prefix "std.")

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

On Fri, 11 Feb 2011 14:46:26 -0500, Tom <no.email@gmail.com> wrote:

> what with this?:
> 	auto arr = ["foo", "bar", "aaa", "zzz"];
> 	sort(arr);
> 	assert(canFind("foo"));
> 	assert(canFind("aaa"));
> 	assert(!canFind("aa"));
> I had a "Error	1	Error: module algorithem is in file 'std\algorithem.d'

it's spelled "algorithm", no e in there.

-Steve