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;
}

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");
    }
}

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.