On 05/24/2010 03:18 PM, Steven Schveighoffer wrote:
On Mon, 24 May 2010 15:58:46 -0400, Andrei Alexandrescu
<[email protected]> wrote:
On 05/24/2010 01:12 PM, Steven Schveighoffer wrote:
On Mon, 24 May 2010 13:36:01 -0400, Andrei Alexandrescu
<[email protected]> 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.
Sorry. Yes, by-key iteration should be possible.
Andrei
