On Mon, 24 May 2010 17:47:18 -0400, Andrei Alexandrescu
<[email protected]> wrote:
On 05/24/2010 04:38 PM, Steven Schveighoffer wrote:
On Mon, 24 May 2010 17:35:11 -0400, Andrei Alexandrescu
<[email protected]> wrote:
On 05/24/2010 04:08 PM, Steven Schveighoffer wrote:
On Mon, 24 May 2010 16:27:46 -0400, Andrei Alexandrescu
<[email protected]> 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.
It's always easy to say that there may come a day when the interfaces
don't work -- none of us can see the future. When that day comes, we can
find a solution to it. The worst case scenario is that you simply don't
implement any interfaces. It does not detract from the interfaces that
exist. It would seem odd that some of the collections do not implement
the interfaces while others do. At the very least though, all containers
should be iterable, meaning they will implement the Iterator!V interface.
That at least allows it to interact with the other container types.
On the flip side, if containers did not implement interfaces, having to do
this:
class WrappedSet!(alias Impl, V) : Set!V
{
private Impl!V impl;
int functionToSatisfySet() { return impl.functionToSatisfySet(); }
...
}
seems to me like a lot more crufty and bloated than simply adding : Set!V
on the end of the class declarations.
But I'm willing to drop the interfaces for now since interfaces obviously
are an unpopular choice.
-Steve
