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