bool end_of_word;
Node(): end_of_word(false) {}
This would be probably more idiomatic to simply writewritten as
bool end_of_word = false;
Next,
explicit Trie(std::vector<std::string>);
is probably more idiomatic written as
template<typename Itr> Trie(Itr begin, Itr end);
Next,
std::unique_ptr<Node> root;
Why is it allocated on heap? It's a private member owned by this object, by putting it on heap you simply get some (noticeable) dereference overhead, and that's all.
Trie::Trie() {
root = std::unique_ptr<Node>(new Node());
}
Trie::Trie(std::vector<std::string> words) {
root = std::unique_ptr<Node>(new Node());
Irrespective of what's said above about root's type, such initializations are better put in initialization lists.:
Trie::Trie(): root(new Node) {}
And rememberif you upgrade to C++14, recall that make_unique is the new new:
Trie::Trie(std::vector<std::string> words)
: root(std::make_unique<Node>())
{}
Next,
for (const char & key : word) {
char type is small enough to be bound by value. Scalar and small POD types, when passed by reference, can create unnecessary overhead so it is better written as
for (char key : word) {
(or even
for (auto key : word) {
which makes perfect sense if you ever decide to make character type a parameter to your Trie.)
auto found = it->children.count(key);
if (!found)
return false;
it = it->children[key].get();
In C++, even with unordered containers, it is better done as
auto where = it->children.find(key);
if (where == it->children.end()) return false;
it = where->second.get();
And similarly for Insert().
Which, by the way, I would declare as
Trie &Insert(const std::string &);
But that is more like a personal preference.
How about adding a method that searches for all the elements whose keys start with a given prefix, and returns them either as a subnode, or a fresh container, like list or vector?
And the final boss: define an iterator type for your trie.
