Trie Data Structure Implementation in C++11 using Smart Pointers 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 &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;memory&gt;

#define ALPHABET_SIZE 26

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

#endif
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-&gt; on every member access?)

this-&gt;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 &lt; ALPHABET_SIZE; i++) {
      this-&gt;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&lt;node&gt; root = std::make_shared&lt;node&gt;();


and then delete the whole tree() constructor function.



tree::insert

In C++ (unlike C) the style is to put the * or &amp; of the type with the type, not the name being defined.  So write string&amp; name not string &amp;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&amp; slot = n-&gt;children[index];
if (!slot)  slot = make_shared&lt;node&gt;();
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 &amp;&amp; n-&gt;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.