Trie Data Structure Implementation in C++11 using Smart Pointers

Question

This implementation is part of my open source project forest.

I wrote the following header file to implement a trie data structure that supports inserting and searching strings consisting of 26 lower-case letters of the English alphabet. I am looking forward to hearing your opinion about this implementation and any suggestions/fixes you may have.

/**
 * @file trie.h
 */

#ifndef TRIE_H
#define TRIE_H

#include <iostream>
#include <string>
#include <memory>

#define ALPHABET_SIZE 26

/**
 * @brief The forest library namespace
 */
namespace forest {
  namespace trie {
    /**
     * @brief trie node struct
     */
    struct node {
      std::shared_ptr<node> children[ALPHABET_SIZE];
      bool end;
      /**
       * @brief Constructor of a trie node
       */
      node() {
        this->end = false; 
        for (int i = 0; i < ALPHABET_SIZE; i++) {
          this->children[i] = NULL;
        }
      }
    };
    /**
     * @brief trie class
     */
    class tree {
    private:
      std::shared_ptr<node> root;
    public:
      tree() {
              root = std::make_shared<node>();
      }
      /**
       * @brief Inserts the given key into the trie
       * @param key The key to be inserted
       * @return void
       */
      void insert(const std::string &key) {
        std::shared_ptr<node> n = root;
        for (int i = 0; i < key.length(); i++) {
          int index = key[i] - 'a';
          if (n->children[index] == nullptr) {
            n->children[index] = std::make_shared<node>();
          }
          n = n->children[index];
        }
        n->end = true;
      }
      /**
       * @brief Searches for the given key in the trie
       * @param key The key to be inserted
       * @return true if key exists in the trie and false otherwise
       */
      const bool search(const std::string &key) {
        std::shared_ptr<node> n = root;
        for (int i = 0; i < key.length(); i++) {
          int index = key[i] - 'a';
          if (n->children[index] == nullptr) {
            return false;
          }
          n = n->children[index];
        }
        return (n != nullptr && n->end == true);
      }
    };
  }
}

#endif

Answer 1

Your include guard might clash with another file. After all, you used an outer namespace because the name is not unique enough; the same is true for the header. Suggest you use a UUID for that, and also #pragma once . (Personally, I chose to use the pragma only with the idea that if I ever need guards they can be mechanically generated, all correctly. But all the major platforms take the pragma so I never needed guards.)

---

#define ALPHABET_SIZE 26

Noooo… Don’t use #define for simple constants, especially in a header file!

---

Let’s look at your node constructor:

(and what's with all the this-> on every member access?)

this->end = false;

You should not be assigning initial values in the constructor. You should initialize things. Here, you can simply use an inline initializer on the data member declaration, and be done with it.

// data member
bool end = false;

Continuing with the node constructor:

for (int i = 0; i < ALPHABET_SIZE; i++) {
      this->children[i] = NULL;

Wow! Lots to go over here.

First, don’t use NULL. Not ever! If you are writing in C++11, it is dead and should be forgotten about.

Second, don’t write legacy for loops to go over a collection. Use the range-for form instead.

for (auto el : children)
    el.reset();

Third, don’t write loops at all if you can use algorithms.

std::fill (std::begin(children), std::end(children), nullptr);

but I don’t like the need to give two separate points like that when I just want the whole thing. The std algorithms are behind in this respect. But, we have Boost as a proving ground for library stuff that we want to add to the standard or simply make commonly used: (see doc page)

boost::fill (children, nullptr);

But… just don't! A shared_ptr is automatically initialized to the empty state, which means the constructor is already doing this before the body of your code is run!

So, add the inline initializer for end, and then delete the entire constructor.

---

Now look at the constructor for tree.

Same thing: don’t assign in the body, but initialize members. The inline member init will work fine here.

// data member of tree
std::shared_ptr<node> root = std::make_shared<node>();

and then delete the whole tree() constructor function.

---

tree::insert

In C++ (unlike C) the style is to put the * or & of the type with the type, not the name being defined. So write string& name not string &name.

Use auto (almost everywhere).

auto n = root;

For the for loop, the same comments as before. Stop thinking of index numbers into an array or other collection that then need to be subscripted. Rather, think about iterator positions in any kind of collection, or constructs that do the traversal and just give you a reference to the item to work on.

So, no i.

for (auto ch : key) {

Don’t compare pointers (or smart pointers) against null. They have a truth value that works for this directly.

Remember you can make a reference (an alias) to any part of your data, so don’t repeat children[index] three times.

auto& slot = n->children[index];
if (!slot)  slot = make_shared<node>();
n= slot;

---

Similar for search.
Returning a const bool doesn’t do anything; just return bool.
At the end of that function, testing against true is just silly. It is already a bool! What value does it hold? true.

Also, not explicitly testing against nullptr here helps you see how the idiom works well for guarding the real test:

return n && n->end;

Oh, and don’t put redundant parenthesis around return values.

---

BTW, your algorithm and approach is quite sound. It’s only the C++ language fluency and idioms that I commented on.

Answer 2

Use of shared_ptr

Be wary of std::shared_ptr if you're not sharing the data. Shared pointers are not free, compared to std::unique_ptr and raw pointers copying a shared pointer is fairly expensive. Usually you will want to use a shared_ptr when you are expressing shared ownership of the data. The nodes are never exposed to the outside of your trie, using unique_ptr should be sufficient here.

Given std::unique_ptr<Node> root and using std::vector<std::unique_ptr<Node>> children in the node you'd rewrite your loop to something like this:

    node* n = root.get();
    for (int i = 0; i < key.length(); i++) {
      int index = key[i] - 'a';
      if (n->children[index] == nullptr) {
        n->children[index] = std::make_unique<node>();
      }
      n = n->children[index].get();
    }

Warnings

Compiling with -Wall on shows two warnings both with regard to key.length() which returns size_t and not int.

ALPHABET_SIZE

Ass @JDługosz said, don't #define that, you are putting that into global scope, you can use a local member variable in the trie structure that is where it's being used. If you need it out side, make it public, you can also make it static then it becomes accessible as Trie::Alphabet_Size.

Depending on your target language, confining yourself to ASCII characters might not be a very future proof way to implement this datastructure.

Comments

It's nice to attempt documentation, but look at what some of your documentation says:

  ...
  /**
  * @brief trie node struct
  */
  struct node {
  ...

It's mainly repeating what the code already says, the only word in that documentation block that adds any kind of information is trie and it's really implied by the namespace. Saying nothing would probably been better here. Try say something that the code doesn't express.

Naming

Your trie is named tree well technically it's named trie::tree, while you alread have a namespace forest why not just call it trie, it will save generations of programmers from having to type another namespace label, and it will let people write using forest::trie and not mistake it with the tree you would have to put under forest::redblack::tree if you keep your naming scheme going.