On 04/20/2013 05:14 AM, Hardy wrote:
Further more, the algorithm on idea page, radix sort and data structure, trie is also an good and confident choice for me. could you please give me some suggestion about it?
I once wrote a radix tree (or trie.) It was a template class, just like the other STL containers, which took three template arguments: key type, value type, and scanning policy. A custom allocator could be added, I just didn't have the need for it. The scanning policy is used to parse the key, and I wrote two of those. The first was a character scanner, which simply breaks the input string into a sequence of characters, and as such it resembles the normal trie. The second was a namespace scanner, whose input is supposed to be namespace string (e.g. "Alpha::Bravo::Chalie") and which breaks the input into a sequence of namespace components (e.g. "Alpha", "Bravo", "Charlie".) It would be easy to supply other scanning policies, such as dot separated strings (e.g. "Alpha.Bravo.Charlie" as used by default in Boost.PropertyTree), paths (e.g. "Alpha/Bravo/Charlie"), and even UTF-8 character scanning.