Trie Implementation in C++11

Question

I implemented a Trie in C++11, but I am not sure if my usage of struct and std::unique_ptr, and std::unordered_map are correct and idiomatic. Therefore, I hope someone could provide constructive criticism on my code.

My Trie implementation has three simple methods:

void Trie::Insert(const std::string&  word);
bool Trie::StartsWithPrefix(const std::string& prefix);
bool Trie::IsACompleteWord(const std::string& word);

Code

// tries.h
#ifndef TRIE_H_
#define TRIE_H_

#include <vector>
#include <string>
#include <unordered_map>


class Trie {
 public:
  // Trie Constructor
  Trie();
  explicit Trie(std::vector<std::string>);

  // Trie Operations
  void Insert(const std::string&  word);
  bool StartsWithPrefix(const std::string& prefix);
  bool IsACompleteWord(const std::string& word);

 private:
  struct Node {
    bool end_of_word;
    std::unordered_map<char, std::unique_ptr<Node>> children;
    Node(): end_of_word(false) {}
  };
  std::unique_ptr<Node> root;
};

/// ===========================
/// Tries Implementation
/// ===========================

Trie::Trie() {
  root = std::unique_ptr<Node>(new Node());
}

Trie::Trie(std::vector<std::string> words) {
  root = std::unique_ptr<Node>(new Node());
  for (auto w : words)
    Insert(w);
}

void Trie::Insert(const std::string&  word) {
  if (word.empty()) return;
  auto it = root.get();
  for (const char & key : word) {
    int found = it->children.count(key);
    if (!found)
      it->children.emplace(key, std::unique_ptr<Node>(new Node()));
    it = it->children[key].get();
  }
  it->end_of_word = true;
}


bool Trie::StartsWithPrefix(const std::string& prefix) {
  auto it = root.get();
  for (const char & key : prefix) {
    auto found = it->children.count(key);
    if (!found)
      return false;
    it = it->children[key].get();
  }
  return true;
}


bool Trie::IsACompleteWord(const std::string& word) {
  auto it = root.get();
  for (const char & key : word) {
    auto found = it->children.count(key);
    if (!found)
      return false;
    it = it->children[key].get();
  }
  return (it->end_of_word) ? true : false;
}

#endif // TRIE_H_

Test

#define CATCH_CONFIG_MAIN
#include "catch2/catch.hpp"
#include "trie.h"


SCENARIO("Trie operations", "[trie]") {
  GIVEN("A Trie Data Structure") {    

    Trie trie({"hello", "test"});

    REQUIRE(trie.StartsWithPrefix("hell") == true);
    REQUIRE(trie.StartsWithPrefix("helli") == false);
    REQUIRE(trie.StartsWithPrefix("test") == true);
    REQUIRE(trie.StartsWithPrefix("ab") == false);

    trie.Insert("ab");
    REQUIRE(trie.StartsWithPrefix("ab") == true);

    REQUIRE(trie.IsACompleteWord("ab") == true);
    REQUIRE(trie.IsACompleteWord("hell") == false);
  }
}

Answer 1

    bool end_of_word;
    Node(): end_of_word(false) {}

This would be probably more idiomatic simply written as

    bool end_of_word = false;

Next,

    explicit Trie(std::vector<std::string>);

is probably more idiomatic written as

    template<typename Itr> Trie(Itr begin, Itr end);

Next,

    std::unique_ptr<Node> root;

Why is it allocated on heap? It's a private member owned by this object, by putting it on heap you simply get some (noticeable) dereference overhead, and that's all.

Same goes for branches: there's no point in keeping child Nodes on heap, std::unordered_map<char, Node> is quite sufficient for a tree, with no additional overhead.

Trie::Trie() {
  root = std::unique_ptr<Node>(new Node());
}

Trie::Trie(std::vector<std::string> words) {
  root = std::unique_ptr<Node>(new Node());

Irrespective of what's said above about root's type, such initializations are better put in initialization lists:

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

And if you upgrade to C++14, recall that make_unique is the new new

Trie::Trie(std::vector<std::string> words)
  : root(std::make_unique<Node>())
{

Next,

  for (const char & key : word) {

char type is small enough to be bound by value. Scalar and small POD types, when passed by reference, can create unnecessary overhead so it is better written as

  for (char key : word) {

(or even

  for (auto key : word) {

which makes perfect sense if you ever decide to make character type a parameter to your Trie.)

    auto found = it->children.count(key);
    if (!found)
      return false;
    it = it->children[key].get();

In C++, even with unordered containers, it is better done as

    auto where = it->children.find(key);
    if (where == it->children.end()) return false;
    it = where->second.get();

And similarly for Insert().

Which, by the way, I would declare as

  Trie &Insert(const std::string &);

But that is more like a personal preference.

How about adding a method that searches for all the elements whose keys start with a given prefix, and returns them either as a subnode, or a fresh container, like list or vector?

And the final boss: define an iterator type for your trie.