dcollections 1.0 and 2.0a beta released

[Andrei Alexandrescu]

On 05/24/2010 01:12 PM, Steven Schveighoffer wrote:
> On Mon, 24 May 2010 13:36:01 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
>
>> On 05/24/2010 12:11 PM, bearophile wrote:
>>> Steven Schveighoffer:
>>>> Is it unreasonable to expect to be able
>>>> to iterate the keys in a trie? (I don't really know, I've never worked
>>>> with them)
>>>
>>> On tries you can iterate on all keys or on a sorted range of the keys.
>>
>> There's one more way of iteration that's unique to tries - by key
>> element (e.g. if key is string, you iterate by character). That would
>> be an exploratory iteration.
>>
>> At each step in the iteration you pass a character, so popFront()
>> takes an argument, it's popFront(char). trie.popFront('a') takes you
>> to all elements in the trie that start with 'a'. Then you can continue
>> exploring by e.g. trie.popFront('x') which takes you to all elements
>> that start with "ax". At any point the range may become dry (nothing
>> with this prefix). If the range is not empty, front() gives you
>> information about all strings that share the particular prefix you
>> have spanned (count and breadth comes to mind).
>
> That could be supported.

To paraphrase a commercial, "there's an interface for that" :o).

> But iterating over the keys, is that not advisable? Would your trie
> iterator be the only way to iterate over the elements? It seems rather
> non-useful.

I think a trie, like many other nontrivial containers, supports several 
means of iteration.

> Or is there another way to iterating the keys that would be more
> efficient than building an array to contain the 'key' for each node?

I don't know. I'm just glad I can explore that without having to think 
in interfaces.


Andrei