dcollections 1.0 and 2.0a beta released

[Andrei Alexandrescu]

On 05/24/2010 04:38 PM, Steven Schveighoffer wrote:
> On Mon, 24 May 2010 17:35:11 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
>
>> On 05/24/2010 04:08 PM, Steven Schveighoffer wrote:
>>> On Mon, 24 May 2010 16:27:46 -0400, Andrei Alexandrescu
>>> <SeeWebsiteForEmail at erdani.org> wrote:
>>>
>>>> Sorry. Yes, by-key iteration should be possible.
>>>
>>> OK, so we should be able to iterate keys. And the keys are not stored in
>>> the trie structure itself. So how does one iterate the keys of the
>>> container without reconstructing them from the trie nodes using the
>>> heap?
>>
>> You can't. At some point you need to copy tree traces into T[] arrays.
>> If the trie stores parent nodes, you don't need to do that as you can
>> expose a trace as a double-ended range containing the key.
>>
>> There's a kind of trie that was defined to avoid such issues; it
>> stores the keys in clear, in the leaves, at the expense of
>> duplication. I don't remember the name offhand. Does anyone?
>
> OK, so the keys function of Map should work just fine for a Trie
> implementation. Good to know.

This wins a little battle but not the war. Long term you're facing the 
sysyphic job of either knocking new containers into the existing 
interfaces, or extending the interfaces to accommodate new containers. 
It doesn't look to me like a winning proposition.

The FIC (Federation of Independent Containers) does not have that 
problem. It does have its specifications and guidelines but whichever 
container doesn't support some or even all of the required methods can 
simply define its own under other names. Then users can play with the 
containers and with the ranges they define as they find fit.


Andrei