Trie data structure in C++ with add and search

Question

I am learning C++11 and wanted to practice data structures so here is my trie implementation with add and search functions. What are some things to improve?

trie.h

#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>

namespace {
    class Node
    {
    public:
        Node();
        ~Node();
        Node(char c);
        char get_value() const;
        bool get_leaf() const;
        void set_leaf();

        Node* get_child(const char key);
        std::vector<Node *> children;

    private:
        char value;
    };
}

class NodePointerComp
{
public:
    explicit NodePointerComp(const char key);
    char const key_;
    bool operator()(Node const *n) const;

};

class Trie
{
public:
    Trie();
    ~Trie();
    void add_word(std::string const &word);
    bool search(std::string const &word);
    std::vector<std::string> find_suffix(std::string const &s, int max);

private:
    Node *root;
    Node* find_string(std::string const &word);
};

trie.cpp

#include "trie.h"

Node::Node() {}
Node::Node(char c) : value(c) {}

char Node::get_value() const { return value < 0 ? -value : value; }

bool Node::get_leaf() const { return value < 0 ? true : false; }

// a string with char -128 or a nullchar will break this
void Node::set_leaf()
{
    if (value > 0)
        value = -value;
}

NodePointerComp::NodePointerComp(const char key) : key_(key) {}

bool NodePointerComp::operator()(Node const *n) const { return n->get_value() == key_; }

Node* Node::get_child(const char key)
{
    auto x = std::find_if(children.begin(), children.end(), NodePointerComp(key));
    if (x == children.end())
        return nullptr;

    return *x;
}

Node::~Node()
{
    for (auto c : children)
        delete c;
}


Trie::Trie()
{
    root = new Node();
}

void Trie::add_word(std::string const &word)
{
    Node *curr = root;

    uint32_t i = 0;
    for (i; i < word.length(); i++)
    {
        if (curr->get_child(word[i]) == nullptr)
            break;

        curr = curr->get_child(word[i]);
    }

    for (i; i < word.length(); i++)
    {
        curr->children.push_back(new Node(word[i]));
        curr = curr->children.back();
    }

    curr->set_leaf();

}


std::vector<std::string> Trie::find_suffix(std::string const & s, int max)
{
    Node *curr = find_string(s);
    if (!curr || max == 0)
        return {};

    std::vector<std::string> output;
    std::stack<std::pair<Node*, std::string>> st;

    for (auto c : curr->children)
        st.push({ c, ""});

    while (!st.empty())
    {
        auto p = st.top();
        st.pop();

        p.second += p.first->get_value();
        if (p.first->get_leaf())
        {
            output.push_back(p.second);
            if (output.size() == max)
                break;
        }

        for (auto c : p.first->children)
            st.push({ c, p.second });

    }

    return output;
}

Node* Trie::find_string(std::string const & word)
{
    Node *curr = root;
    std::string str;

    for (auto c : word)
        if ((curr = curr->get_child(c)) == nullptr)
            return nullptr;

    return curr;
}

bool Trie::search(std::string const &word)
{
    auto *p = find_string(word);
    if (p) return p->get_leaf();
    return false;
}

Trie::~Trie()
{
    delete root;
}

Answer 1

This is a pretty good implementation from what I see. It's easy to read and looks very straightforward. Nice work!

Naming

For the most part your naming is good. There are a few small things I would change. For example, the get_leaf() method. When I read the name I thought it was going to retrieve a leaf node, but I couldn't see how it could determine which one. In reality, it returns a bool that tells whether it is a leaf or not. I would rename it to is_leaf() to avoid confusion.

I also don't like the word value as it's fairly meaningless. It represents a letter in the set of words formed by that branch of the trie. I would name it character or letter.

Organization

For the default constructor for a Node, in C++11 and later, you don't need to write it out by hand. In the header, you can just declare it as:

Node() = default;

In trie.cpp you have the implementation of 3 classes. I usually break them out into a separate source file per class. Given how small these are, it's not a huge deal to put it all in one file. I would, however, keep all methods for a class together. You have several methods of Node, then 2 methods of NodePointerComp, then more methods of Node. It makes it a little hard to find things when examining the source. So I'd move all methods from a single class together into 1 section. You might also want to add either a comment break between them (just something like //----NodePointerComp methods----) or, if your compiler supports it, something like a #pragma mark NodePointerComp. In my IDE, when the editor sees #pragma mark <Name>, it adds <Name> to the pop-up menu with all the functions in it. That makes it really easy to navigate to those methods quickly.

Simplify

It looks like you're using the convention of a negative value representing whether a node is the end of a word or not. I originally thought that you were trying to define the last node in a branch, but I see from the comments I was mistaken. That's a good indication that the name is too confusing and the implementation too complex.

I'm not an expert on the C++ spec, but I thought that whether char was signed or not (when not explicitly specified) was implementation-dependent. Even if it's not, that's a tenuous way to determine the end of a word. I recommend a bool that says it's the end of a word. It would simplify the get_leaf() and set_leaf methods(). Also they should be renamed to is_word_end() and set_word_end().

Encapsulation

I'm a little uncomfortable with Node::children being public. That's an implementation detail, and I think it would be a good idea to hide that detail from users of the class. It would make the logic in Trie slightly less straightforward, but I think the tradeoff would be worth it in the long run. Right now, Trie can modify that variable and Node won't necessarily be aware of it. It also makes it more difficult to use in a multithreaded environment, should you need to do that. If it were private, you could ensure that it was never accessed outside of some sort of lock (or mutex, whatever) inside the class.

Answer 2

1. It might look the memory management works properly in your code. Well, not exactly. Your code is not exception-safe. A node is allocated with a new call in the add_word member-function. A pointer to it is added to a vector using push_back. If push_back fails with an exception, the memory leaks. The pointer isn't stored anywhere, so it'll never get deleted. There's no such problem if you use smart pointers.

2. Setting the value of the Node to a negative number is confusing. Moreover, char isn't guaranteed to be signed. An overflow of a signed value is well-defined, but it can break if the string has non-ascii characters.

3. How to fix it? Firstly, Let's do a simple thing and add a flag to indicate if some word ends in the Node (it shouldn't be called a leaf because it may not be a leaf). I'd call it is_word_ending or something like this. It's makes more sense than storing a negative value.

4. I think that keeping the value in a Node is quite confusing. There's no value for the root, is there? In fact, the letter marks an edge from Node to another. That's why I'd rather store a map or an unordered_map from a character to a pointer to a Node. It has a clear meaning: an edge marked by a specific letter. This design is closer to what a trie is from a theoretical point of view.

5. There's no reason to use raw pointers. You can use std::shared_ptr. It'll take care of memory clean up. It'll simplify your code and make it less error prone. So the Node can look like this:

    class Node {
        bool is_word_ending_ = false;
        std::unordered_map<char, std::shared_ptr<Node>> children_;
    public:
        // Indicates that a word ends in this Node.
        void set_word_ending();
        bool is_word_ending() const;
        // Returns a default shared_ptr or a pointer to the child if it exists.
        std::shared_ptr<Node> get_child(char letter) const;
        // Adds a child and returns a pointer to it.
        std::shared_ptr<Node> add_child(char letter);
    };
   

   This way the code becomes much simpler: there's no need for the NodePointerComp structure. There's no need to care about cleaning up the memory either.

6. I'd also recommend renaming some functions and variables: for instance, x is a very strange name for an iterator. find_suffix, surprisingly, can return more than one suffix.

7. You can make the trie more flexible by making the type of the alphabet a template parameter instead of using a fixed type char. It'll let it work with other types of strings.