Trie Data Structure Implementation in C++11 using Smart Pointers -- follow-up Link to my first question.

Link to my latest source code.

I followed @JDługosz recommendations. How does it look? Do you have any further recommendations? Is it better (if possible) to replace shared_ptr with unique_ptr? How could someone extend it to use the Unicode character set?

#pragma once

#include &lt;iostream&gt;
#include &lt;memory&gt;
#include &lt;string&gt;

namespace forest {
    class trie {
    private:
        struct Node {
            std::shared_ptr&lt;Node&gt; children[26];
            bool end = false;
        };
        std::shared_ptr&lt;Node&gt; root = std::make_shared&lt;Node&gt;();
    public:
        void insert(const std::string &amp; key) {
            std::shared_ptr&lt;Node&gt; n = root;
            for (auto c : key) {
                int index = c - 'a';
                auto&amp; slot = n-&gt;children[index];
                if (!slot) slot = std::make_shared&lt;Node&gt;();
                n = slot;
            }
            n-&gt;end = true;
        }
        bool search(const std::string &amp; key) {
            std::shared_ptr&lt;Node&gt; n = root;
            for (auto c : key) {
                int index = c - 'a';
                auto&amp; slot = n-&gt;children[index];
                if (!slot) return false;
                n = slot;
            }
            return n &amp;&amp; n-&gt;end;
        }
    };
}
Input sanitization

Your functions take a std::string as parameter, as such, they should be "well behaved" for any possible std::string passed to them. Note that well behaved does not mean that it has to "work", just that it should not break anything.

Specifically, what would happen if I passed the string "Hello" to that function? 'H' - 'a' is -25, ruh roh!

There's a few different ways to tackle this. 


You could convert all upper-case letters to lower case, but that does not fix punctuation marks, spaces and numbers. I also personally think that wether the trie is case-sensitive or not should be the user's problem, not the trie itself.
You could bail out of the function if a unhandled character is hit.
Just expand children to 256 instead of 26 so that all legal values of char are handled properly. Sure your trie is going to be 5 times as big, but that's a fairly minor detail since it grows logarithmically. 


edit: This last approach also makes the trie operate on raw data instead of characters, which makes it encoding-agnostic (which gives you your unicode support)

Avoid using shared_ptr unless absolutely necessary

shared pointers are clunky and heavy affairs. On top of this, using them sends a message to people reading the code: Ownership of the object is potentially shared between multiple owners, which is simply not the case here.

in your case, a std::unique_ptr&lt;&gt; is absolutely fine.

Your root does not need to be dynamically allocated

It's created at construction unconditionally, and destroyed at destruction unconditionally. On top of that, it does not make use of type erasure (polymorphism). As such, there's no reason for it not to be a normal member of trie.

std::shared_ptr&lt;Node&gt; root = std::make_shared&lt;Node&gt;();

becomes:

Node root;

This will require you to change your search and insert functions so that the first line becomes:

const Node* n = &amp;root;

But that's fine because that's preferable once you move to unique_ptr anyways.

Edit: On that note:

Raw pointers are not evil

std::shared_ptr&lt;Node&gt; n = root;

We tend to teach people that "you should never use raw pointers". But I find that extremely naive. The real rule is "You should never have raw pointers with ownership".

There is absolutely nothing wrong with using raw pointers as long as it's understood that:


The pointer only refers to the pointed object without owning it.
The lifetime of the pointer assignment to the object is fully enclosed by the lifetime of whatever DOES own the object.


In your code using shared_ptr, using the following would have been 100% ok, and much better in my opinion:

const Node* n = root.get();

Mark non-mutating functions as const.

Your search() member function should not alter the trie in any way, so you should mark it as const like this:

bool search(const std::string &amp; key) const {

There's a few subtle advantages for the compiler, but the main one is that if you goof up and accidentally do something that changes the trie, the compiler will tell you.

nitpick: private: is redundant here.

The namespace of a class is private by default. Fun fact: that's the only difference between a class and a struct.

nitpick: redundant null-checking

in your search function, when I read the last line:

return n &amp;&amp; n-&gt;end;

My impression was "Oh! n can be possibly null in certain cases", which led me to search for the scenario where that might be the case. It's misleading to the reader.

Defensive programming can be useful at times, but this is just excessive.