2
\$\begingroup\$

Here is a simple C++ 11 trie for insertion and membership testing:

#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <string.h>

class TrieNode{
  //TrieNodes can also be used as tries
public:
  std::map<char, TrieNode> children;
  bool isLeaf;

  bool isContained(char * string){
    if (strlen(string)==0){
      return isLeaf;
     }

    char searchChar = *string; //the next char we are looking at

    if (children.find(searchChar) == children.end()){
      return false;
    }

    /*search for everything but the first char from the string in the trie
      for the first char*/
    return (children[searchChar].isContained(1+string));
  }

  void insertString(char * string){
    if (strlen(string) == 0){
      //If an empty string has been parsed then this node is the end of a string
      isLeaf = true;
      return;
    }

    char searchChar = *string;

    if (children.find(searchChar) == children.end()){
      //Create a new trie for the first character of our string
      TrieNode newNode;
      children[searchChar] = newNode;
    }

    children[searchChar].insertString(string+1);
  }
};

int main(){
  //Sample main function
  TrieNode myTrie;
  printf("hello in trie = %d\n",myTrie.isContained((char *) "hello"));
  myTrie.insertString((char *) "hello");
  printf("hello in trie = %d\n",myTrie.isContained((char *) "hello"));
  return 0;
}

I am relatively new to C++ (I have been muddling around with it for maybe a year now) so am wondering whether I may have either accidentally given my code nasal demons and/or accidentally wasted a lot of memory.

\$\endgroup\$
  • \$\begingroup\$ Why the c++11 tag? I can't spot any c++11 specific feature used. Also your code is a weird mix of c and c++. \$\endgroup\$ – πάντα ῥεῖ Apr 8 '17 at 17:29
  • \$\begingroup\$ Panta Rhei is right about the code. Also casting away constness from string literal is straight undefined behavior (I guess compiler refused to compile the code, thus the cast is applied). I would suggest reading a book like C++ Primer or Accelerated C++. And of course, Effective C++ and Effective Modern C++. C++ tries to leave behind C and keeps it for compatibility reasons mostly. \$\endgroup\$ – Incomputable Apr 8 '17 at 23:01
1
\$\begingroup\$

A couple of thoughts.

  1. Maybe a distinction between Trie and TrieNode might make sense. So TrieNode can be defined as an inner struct within an outer class Trie.
  2. There is no compelling reason to use a char* string representation rather than using string.
  3. unordered_map would do just as well as a map, and possibly be faster.

  4. You can consider iterating using a while loop instead of recursion in isContained.

\$\endgroup\$
1
\$\begingroup\$

I have to say there is a lot room for improvement:

  1. Use C++ features like std::string. There is no reason for you to put char* into the mix.

  2. Rethink your data structures. You want to build a trie. That trie consists of nodes. So I would generally expect one object that is a node and one that is a trie responsible for creating and storing the nodes as well as traversing the trie.

  3. Your choice of a map is a rather bad one. You want to compare simple characters one at a time, for which the (unordered_)map is an overkill. Simply create a std::vector of the trieNodes that represent the respective characters and you are fine.

  4. It is correct, that you only insert, if the first char is not found, but make this more explicit.

So lets put that together.

#include <memory>
#include <string>
#include <vector>
// The trie node only has the character it represents and a 
// number of children that come after it
struct MyTrieNode {
    MyTrieNode(const char c) : character(c) {}

    const char character;
    std::vector<MyTrieNode*> children
}
// The actual trie only stores smart pointers to the nodes and the root.
// Furthermore, it is responsible for generation of nodes and search after words
class MyTrie {
public:    

    // Construct with a rootNode that holds no character
    MyTrie() {
        nodes.emplace_back(std::make_unique('\0'));
        rootNode = nodes.back().get();
    }

    // Add a child to a node, only if it is not already there
    MyTrieNode* AddChild(MyTrieNode* node, const char& c) {
        // First search for an existing node
        for (const MyTrieNode* childNode : node->children) {
            if (childNode->character == c) {
                return childNode;  
            }
        }
        // Character not already found so add a new child
        nodes.emplace_back(std::make_unique(c));
        node->children.emplace_back(nodes.back().get());
        return node->children.back();
    }

    // Add a std::string by traversing its characters
    void AddString(const std::string& newString) {
        for (const char& c : newString) {
            AddChild(rootNode, c);
        }
    }

    // Search for a given character in the children of a node or return nullptr
    MyTrieNode* findChild(MyTrieNode* node, const char& c) {
        for (const MyTrieNode* childNode : node->children) {
            if (childNode->character == c) {
                return childNode;  
            }
        }
        return nullptr;
    }

    // Search for a word. Once findChild returns nullptr we can return early as that word is not found
    bool findString(const std::String& word) {
        MyTrieNode* current = rootNode;
        for (const char& c : word) {
            current = findChild(current, c);
            if (current == nullptr) {
                return false;
            }
        }
        return true;
    }
private:
    MyTrieNode* rootNode;
    std::vector<std::unique_ptr<MyTrieNode>> nodes;
}
\$\endgroup\$
  • \$\begingroup\$ Btw you can always use findChild in AddChild, however i no not like the temporary that you need there \$\endgroup\$ – miscco May 11 '17 at 6:34

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.