• 1

• 6.5k
• 18
• 41

#Design

I don't think that TerminalTrieNode is that good of an idea, for multiple reasons:

• You effectively cannot insert byte-strings that contain the char value '0円'. While this isn't likely to come up in purely ASCII based applications, it might e.g. for variants of unicode or handling of raw byte strings.

• Having to use pointers in TrieNode::children (due to inheritance) means (削除) doubling (削除ここまで) increasing the amount of pointer dereferences: One for the actual pointer, and at least one hidden in the std::unordered_map. This makes all operations slower due to cache misses.

• The whole get_word "hack" smells (as you noticed).

Also, it would be nice to retrieve information about which path a node is on.

Ideally, I'd like something along these lines:

class TrieNode {
 // Note: store TrieNode by value!
 std::unordered_map<char, TrieNode> children;
 // simple indicator if this is a leaf node (end of a word)
 bool is_leaf_node;
 // A reference to the path so far
 // Note: if memory usage gets too big, this could be replaced by a std::string_view
 // and storing the leaf strings in a dedicated pool. Non-leaf nodes would only refer to
 // a part of the stored string.
 std::string path;
public:
 TrieNode(std::string);
 std::string_view word() const;
 void make_leaf();
 bool is_leaf() const;
};

Sadly, this won't compile, as std::unordered_map doesn't support incomplete types (TrieNode is incomplete at the declaration of TrieNode::children). One easy solution would be using another hash map type that supports incomplete types, e.g. boost::unordered_map.

But: This solution sidesteps a lot (if not all) of the problems mentioned in @JVApen's answer.

#Other issues

Trie::prefix_apply only takes non-member functions, i.e. no function objects (like capturing lambdas or instance of classes with overloaded operator(std::string const&)) or possibly member functions (including the corresponding object). This can be fixed in two ways:

1. Take a std::function<void(std::string const&)> as parameter. This supports all of the above, but might incur a heap allocation upon construction.

2. Template it on a Callable&& which gets deduced for the passed function. This doesn't incur a heap allocation, but it also doesn't support the (admittedly rare case) usage of pointer to member functions. It also might cause some binary bloat, as a new function is generated for each instantiation (though they might provide more optimization opportunities, e.g. inlining).

A different design choice would be providing an iterator interface, though implementation of that is a bit more work. The advantage of that would be better compatibility with standard algorithms.