I would be very grateful to get some thoughts on this toy-implementation of a trie that I wrote to practice my C++.
Some questions I have:
- Is my
createmember function idiomatic? What's the standard way avoid duplicated copy in the copy-constructor and assignment operator? - Is there a way that I could avoid using the virtual function
get_word? It seems safer to use a virtual function (to avoid accessing undefined memory), but it I don't see why I shouldn't be able to lookup the address wherethis->wordcould reside.
General tips are appreciated, not just answers to these questions.
Thanks!
#include <unordered_map>
#include <string>
#include <iostream>
#include <stdexcept>
class TrieNode {
public:
std::unordered_map<char, TrieNode*> children;
TrieNode() {}
TrieNode(TrieNode const& trie_node) { create(trie_node); };
TrieNode& operator=(TrieNode const& rhs) {
if (&rhs != this) {
children.clear();
create(rhs);
}
return *this;
}
virtual ~TrieNode() {
for (auto const& it: children) {
delete it.second;
}
}
void create(TrieNode const&);
virtual std::string const& get_word() const { throw std::domain_error("get_word() called on non-terminal node."); };
};
class TerminalTrieNode: public TrieNode {
// terminal nodes represent full words
// they are pointed to by edges with key '\0'
public:
std::string word;
std::string const& get_word() const {return word;}
TerminalTrieNode(std::string word): word(word) {}
TerminalTrieNode(TrieNode const* terminal_trie_node) {
create(*terminal_trie_node);
word = terminal_trie_node->get_word();
}
};
void TrieNode::create(TrieNode const& trie_node) {
for (auto const& it: trie_node.children) {
if (it.first != '\0')
children[it.first] = new TrieNode(*it.second);
else
children[it.first] = new TerminalTrieNode(it.second);
}
}
class Trie {
private:
TrieNode root;
void apply_all(TrieNode const* node, void (function(std::string const&))) const {
// helper function for prefix_apply
// applies the given function to every word in the trie below the given word
auto it = node->children.find('\0');
if (it != node->children.end()) {
function(it->second->get_word());
}
for (auto const& c_it: node->children)
apply_all(c_it.second, function);
}
public:
void insert(std::string const& word) {
// add a new word to the trie
TrieNode* node = &root;
for (char const c: word) {
if (!node->children[c])
node->children[c] = new TrieNode();
node = node->children[c];
}
//mark as a terminal node
node->children['\0'] = new TerminalTrieNode(word);
}
bool contains(std::string const& word) const{
// set-membership test
TrieNode const* node = &root;
for (char const c: word) {
auto it = node->children.find(c);
if (it == node->children.end()) return false;
node = it->second;
}
return node->children.find('\0') != node->children.end();
}
void prefix_apply(std::string const& prefix, void (function(std::string const&))) const {
// Apply the given function to every word in the trie that has the given prefix
TrieNode const* node = &root;
for (char const c: prefix) {
auto it = node->children.find(c);
if (it == node->children.end()) return;
node = it->second;
}
apply_all(node, function);
}
};
int main(int argc, char** argv) {
Trie trie;
trie.insert("apple");
trie.insert("app");
trie.insert("apl");
trie.insert("back");
trie.insert("appl");
Trie new_trie = trie;
new_trie.prefix_apply("app", [](std::string const& s) {std::cout << s << '\n';});
}
static_cast<TerminalTrieNode*>(_)->wordworks. \$\endgroup\$