6
\$\begingroup\$

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);
  }
}
\$\endgroup\$
  • \$\begingroup\$ Out of curiosity. Any reason you are limited to C++11? \$\endgroup\$ – brug Dec 3 '18 at 15:51
  • \$\begingroup\$ Dear bruglesco, thank you for your interest in my post. I decided to write C++11 (and not C++14 or C++17) because I am not sure if my code is even considered "modern" C++. During college, instructors only provide us C++98 so I would like to learn on my own modern C++. Eventually, I would love to write in the latest C++. \$\endgroup\$ – Dat Nguyen Dec 3 '18 at 19:31
7
\$\begingroup\$
    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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ about std::make_unique the OP tagged the question c++11. \$\endgroup\$ – Calak Dec 3 '18 at 17:28
  • 1
    \$\begingroup\$ @Calak Thank you for fixing my typo. @bilpll. Thank you very much for providing feedback. I appreciate it. The reason I decided to allocate root on heap over stack because I thought it was a proper way to do so. Also, thank you for sharing the website abseil.io, it is truly great! \$\endgroup\$ – Dat Nguyen Dec 3 '18 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.