Trie class using smart pointers

Question

When one writes C++ code to manipulate LinkedLists, Trees, etc. one creates a tmp pointer that points to the start/root and changes that pointer as one traverses along.

What would be the equivalent way of doing that in smart pointers?

Here, I wrote a Trie code using std::unique_ptr to understand how to pass pointers around. To make the program work, I had to dive inside the smart pointer and access the underlying raw pointer. Is this the right way of doing things? Or is it in fact possible to pass the unique_ptr around? I believe std::move will not be a good idea here since it will a destructive operation.

My code is as follows. Special call out to .get() function to get the raw pointer.

#include <iostream>
#include <memory>
#include <map>
class TrieNode
{
public:
 bool isLeaf{ false };
 std::map<char, std::unique_ptr<TrieNode>> children;
};
class Trie
{
 std::unique_ptr<TrieNode> root{nullptr};
public:
 Trie()
 {
 root.reset(new TrieNode());
 }
 void insert(const std::string& word)
 {
 auto node = root.get();
 for (auto ch : word)
 {
 if (node->children.find(ch) == node->children.end())
 {
 node->children[ch] = std::make_unique<TrieNode>();
 }
 node = node->children[ch].get();
 }
 node->isLeaf = true;
 }
 bool search(const std::string& word) const
 {
 auto node = root.get();
 for (auto ch : word)
 {
 if (node->children.find(ch) == node->children.end())
 {
 return false;
 }
 node = node->children[ch].get();
 }
 return (node && node->isLeaf);
 }
};
int main()
{
 Trie trie;
 trie.insert("application");
 std::cout << "does apple there in the trie? " << (trie.startsWith("app") ? "yes" : "no") << std::endl;
 std::cout << "is application there in the trie? " << (trie.search("apple") ? "yes" : "no") << std::endl;
 return 0;
}

• Loki Astari: The smart point is there to show ownership. As long as you are not using simple pointers to indicate ownership you are fine. It is totally fine to use simple pointers as you move around inside an object to keep track of where you are.
• JDługosz: You posted this to Code Review. Asking how to design with smart pointers is something you might want to ask on the main Stack Overflow site. Simple answer: if you need more than one pointer to it, it's not a unique_ptr. You need a shared_ptr.
• Toby Speight: That's not really right @JDługosz - if you need to share ownership, you need a shared pointer; if you just want to refer to objects within their lifetimes without owning them (like this), that's exactly what raw pointers are good for.
• JDługosz: @TobySpeight that depends on whether you consider the traversal code's tmp pointers to be the same owner as the class invariants that make up the data structure. In any case, I think it's dangerous and a bug waiting to happen.
• Toby Speight: No, the traversal pointers are non-owning (hence raw). They are valid only for the lifetime determined by the owners (the smart pointers). You can consider them to "borrow" access, just like std::string_view objects, iterators or indeed C++ references.

Answer 1

The details of TrieNode don't need to be visible outside of Trie, so I recommend making it a private (or protected) member type Trie::Node.

---

We don't need to write a constructor, if we initialise the root node with the value we want:

std::unique_ptr<TrieNode> root = std::make_unique<TrieNode>();

---

Some coding styles ask us to indicate when auto resolves to a pointer type:

 auto* node = root.get();

---

Prefer passing a std::string_view than a const std::string& - it saves having to construct a string object in many circumstances (including the const char* string literals used in this program). Either way, we're missing the required header file, and only succeed by dumb luck.

---

We're doing a lookup twice here:

 if (node->children.find(ch) == node->children.end())
 {
 node->children[ch] = std::make_unique<TrieNode>();
 }
 node = node->children[ch].get();

If we keep the result of find(), then we can use that iterator for that last line, instead of finding it all over again with []. Perhaps a good idea to use insert() for adding the new node; that gives you back an iterator:

 auto* node = root.get();
 for (auto const ch: word) {
 auto& children = node->children;
 auto it = children.find(ch);
 if (it == children.end()) {
 it = children.emplace(ch, std::make_unique<TrieNode>()).first;
 }
 node = it->second.get();
 }

Similarly, in search():

bool search(const std::string_view word) const
{
 auto* node = root.get();
 for (auto const ch: word) {
 auto& children = node->children;
 auto it = children.find(ch);
 if (it == children.end()) {
 return false;
 }
 node = it->second.get();
 }
 return node->isLeaf;
}

---

This call:

trie.startsWith("app")

This fails to compile, as there's no such member. It looks like part of the code is missing, which is certainly a sign that testing could be improved.

---

Don't flush streams unnecessarily using std::endl when a plain newline will do.

---

Improved program

#include <iostream>
#include <map>
#include <memory>
#include <string_view>
class Trie
{
 struct Node
 {
 bool isLeaf = false;
 std::map<char, std::unique_ptr<Node>> children = {};
 };
 std::unique_ptr<Node> root = std::make_unique<Node>();
public:
 void insert(const std::string_view word)
 {
 auto* node = root.get();
 for (auto const ch: word) {
 auto& children = node->children;
 auto it = children.find(ch);
 if (it == children.end()) {
 it = children.emplace(ch, std::make_unique<Node>()).first;
 }
 node = it->second.get();
 }
 node->isLeaf = true;
 }
 bool search(const std::string_view word) const
 {
 auto* node = root.get();
 for (auto const ch: word) {
 auto& children = node->children;
 auto it = children.find(ch);
 if (it == children.end()) {
 return false;
 }
 node = it->second.get();
 }
 return node->isLeaf;
 }
};
int main()
{
 Trie trie;
 trie.insert("application");
 for (auto const s: {"app", "apple", "application"}) {
 std::cout << s << (trie.search(s) ? " is present\n" : " not found\n");
 }
}

• Deduplicator: Do those "some coding styles" only trigger on raw pointers? Also, are you actually for them? And why?
• Toby Speight: I'm not sure what you mean by "trigger only on raw pointers". Obviously auto* p = std::make_unique<Foo>() is invalid, so using auto* isn't reasonable except for pointer types. I'm fairly neutral on the rule, but it doesn't take much effort to comply with it in my day job. Like all style guidelines, it helps to have an awareness that that it exists, so one can make a conscious choice whether to use it.
• Deduplicator: I mean that the style-guide you refer to only cares about raw pointers, not smart-pointers, which cannot be that easily marked.
• Toby Speight: Yes, it didn't give any recommendations for pointer-like objects.
• JDługosz: I think Concepts could be used for smart pointers, to generalize the idea that you are expecting (say) a random-access iterator, or a shared_ptr of some type.

Answer 2

While @Toby has properly removed the need for a custom ctor, you should still add a custom dtor to avoid recursion when destroying the trie:

~Trie(){
 auto comp = [](auto&&, auto&&){ return std::false_type(); };
 std::multimap<char, std::unique_ptr<Node>, decltype(comp)> x(comp);
 // All elements are equal to minimize work done by container
 for (auto p = std::move(root); x.merge(p->children), !x.empty(); x.erase(x.begin()))
 p = std::move(x.begin()->second());
}

Answer 3

Unnecessary use of std::unique_ptr

A std::unique_ptr is used to allocate memory and indicate ownership. However, most STL containers, including std::map, already do exactly that: they internally allocate memory for the keys and values they store, and semantically they uniquely own those. So having a map of std::unique_ptrs here is redundant, you can just write:

struct Node
{
 bool isLeaf{};
 std::map<char, Node> children;
};

You can also avoid using a std::unique_ptr for root by just making root a Node:

class Trie {
 struct Node {
 bool isLeaf{};
 std::map<char, Node> children;
 };
 Node root;
 ...
};

It doesn't really change the other functions much:

void insert(const std::string& word)
{
 auto* node = &root;
 for (auto ch : word)
 {
 // We don't need to check for the existence of ch;
 // std::map's operator[] will already create one if it isn't there.
 node = &node->children[ch];
 }
 node->isLeaf = true;
}
bool search(const std::string& word) const
{
 auto* node = &root;
 for (auto ch : word)
 {
 if (auto it = node->children.find(ch); it != node->children.end())
 {
 node = &it->second;
 }
 else
 {
 return false;
 }
 }
 return node->isLeaf; // node is never nullptr here
}

An important part of learning how to use something is also learning when not to use that something.