Not an exhaustive review but a few remarks about
struct TrieNode
You are using an std::vector<T>, although its size is fixed at 26. Consider using an std::array<T, 26> instead. This reduces calls to allocate dynamic memory. Also, your loops like
for (int i = 0; i < 26; ++i) {
if (root->children[i]) {
//do something
}
}
are then guaranteed to not cause undefined behaviour due to illegal access. Additionally, since every node has at most one parent, there is no reason to use std::shared_ptr, go for std::unique_ptr instead.
26 as the size of your alphabet is a magic number (explanation on wikipedia , stackoverflow ), although a rather obvious one. Nonetheless, you could name it, e.g. declare a
static constexpr size_t alphabet_size = 26;
One could consider a handy using for later on (std::shared_ptr<TrieNode> is repeated quite often in your code) as well as default values, which altogether results in something along the lines of
class Trie {
private:
static constexpr size_t alphabet_size = 26;
struct TrieNode {
bool isEndOfWord = false;
std::array<std::unique_ptr<TrieNode>, alphabet_size> children = {};
};
using TrieNodePtr = std::unique_ptr<TrieNode>;
};
Not an exhaustive review but a few remarks about
struct TrieNode
You are using an std::vector<T>, although its size is fixed at 26. Consider using an std::array<T, 26> instead. This reduces calls to allocate dynamic memory. Also, your loops like
for (int i = 0; i < 26; ++i) {
if (root->children[i]) {
//do something
}
}
are then guaranteed to not cause undefined behaviour due to illegal access. Additionally, since every node has at most one parent, there is no reason to use std::shared_ptr, go for std::unique_ptr instead.
26 as the size of your alphabet is a magic number, although a rather obvious one. Nonetheless, you could name it, e.g. declare a
static constexpr size_t alphabet_size = 26;
One could consider a handy using for later on (std::shared_ptr<TrieNode> is repeated quite often in your code) as well as default values, which altogether results in something along the lines of
class Trie {
private:
static constexpr size_t alphabet_size = 26;
struct TrieNode {
bool isEndOfWord = false;
std::array<std::unique_ptr<TrieNode>, alphabet_size> children = {};
};
using TrieNodePtr = std::unique_ptr<TrieNode>;
};
Not an exhaustive review but a few remarks about
struct TrieNode
You are using an std::vector<T>, although its size is fixed at 26. Consider using an std::array<T, 26> instead. This reduces calls to allocate dynamic memory. Also, your loops like
for (int i = 0; i < 26; ++i) {
if (root->children[i]) {
//do something
}
}
are then guaranteed to not cause undefined behaviour due to illegal access. Additionally, since every node has at most one parent, there is no reason to use std::shared_ptr, go for std::unique_ptr instead.
26 as the size of your alphabet is a magic number (explanation on wikipedia , stackoverflow ), although a rather obvious one. Nonetheless, you could name it, e.g. declare a
static constexpr size_t alphabet_size = 26;
One could consider a handy using for later on (std::shared_ptr<TrieNode> is repeated quite often in your code) as well as default values, which altogether results in something along the lines of
class Trie {
private:
static constexpr size_t alphabet_size = 26;
struct TrieNode {
bool isEndOfWord = false;
std::array<std::unique_ptr<TrieNode>, alphabet_size> children = {};
};
using TrieNodePtr = std::unique_ptr<TrieNode>;
};
Not an exhaustive review but a few remarks about
struct TrieNode
You are using an std::vector<T>, although its size is fixed at 26. Consider using an std::array<T, 26> instead. This reduces calls to allocate dynamic memory. Also, your loops like
for (int i = 0; i < 26; ++i) {
if (root->children[i]) {
//do something
}
}
are then guaranteed to not cause undefined behaviour due to illegal access. Additionally, since every node has at most one parent, there is no reason to use std::shared_ptr, go for std::unique_ptr instead.
26 as the size of your alphabet is a magic number, although a rather obvious one. Nonetheless, you could name it, e.g. declare a
static constexpr size_t alphabet_size = 26;
One could consider a handy using for later on (std::shared_ptr<TrieNode> is repeated quite often in your code) as well as default values, which altogether results in something along the lines of
class Trie {
private:
static constexpr size_t alphabet_size = 26;
struct TrieNode {
bool isEndOfWord = false;
std::array<std::unique_ptr<TrieNode>, alphabet_size> children = {};
};
using TrieNodePtr = std::unique_ptr<TrieNode>;
};