dcollections 1.0 and 2.0a beta released

[Steven Schveighoffer]

On Mon, 24 May 2010 15:58:46 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

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

No there isn't.  I wouldn't make that an interface, as it's not  
foreachable.  I'd build a special range for it.

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

Including keys?!!!

Still not a straight answer.  If you should be able to iterate keys, then  
say you should be able to iterate keys.  If you shouldn't, then say that.

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

I don't really know what this means.  The interfaces are a way to plug  
containers in at runtime.  They are not meant to be the entire API for the  
collection.  You can absolutely add whatever functionality that does not  
fit in the interface as an additional feature, and users will have to use  
the exact type in order to use that feature.

-Steve