4
\$\begingroup\$

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;
}
\$\endgroup\$
5
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ May 13, 2021 at 22:36
  • \$\begingroup\$ 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. \$\endgroup\$
    – JDługosz
    May 14, 2021 at 16:14
  • \$\begingroup\$ 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. \$\endgroup\$ May 14, 2021 at 19:30
  • \$\begingroup\$ @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. \$\endgroup\$
    – JDługosz
    May 17, 2021 at 13:53
  • \$\begingroup\$ 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. \$\endgroup\$ May 17, 2021 at 14:09

3 Answers 3

5
\$\begingroup\$

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");
    }
}
\$\endgroup\$
5
  • \$\begingroup\$ Do those "some coding styles" only trigger on raw pointers? Also, are you actually for them? And why? \$\endgroup\$ May 15, 2021 at 20:42
  • \$\begingroup\$ 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. \$\endgroup\$ May 16, 2021 at 11:53
  • \$\begingroup\$ I mean that the style-guide you refer to only cares about raw pointers, not smart-pointers, which cannot be that easily marked. \$\endgroup\$ May 16, 2021 at 12:19
  • \$\begingroup\$ Yes, it didn't give any recommendations for pointer-like objects. \$\endgroup\$ May 16, 2021 at 12:30
  • \$\begingroup\$ 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. \$\endgroup\$
    – JDługosz
    May 17, 2021 at 13:59
3
\$\begingroup\$

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());
}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.