I am getting a problem with my code. https://godbolt.org/z/9hdWrdPnG. Its a normal Trie implementation where I have used std::array to store indices of nodes into a std::vector which increases as new node elements are stored. There is a strange behaviour when I don't reserve memory for vector of arrays in Trie constructor. As the capacity of vector changes, the array object would be moved inside new allocated space of vector, but the contents of array gets messed up. I am not sure its a problem with the code I implemented, or just behaviour of the containers in the library that I am overlooking. I know that std::array move constructors are different wrt other containers move constructors, but I am not sure what would be right behaviour here.
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <string>
#include <iomanip>
using namespace std;
class Trie {
struct Node {
Node() : child{}, words{0} {
fill_n(child.begin(), 26, -1);
}
void print(ostream& oss) {
for(auto&& x : child) oss << setw(2) << x << ' ';
oss << words << endl;
}
array<int,26> child{};
int words{0};
};
vector<Node> data{};
Node root{};
public:
Trie() : data{}, root{}{
//data.reserve(32);
}
void print(ostream& oss = cerr) {
root.print(oss);
for(auto&& nd : data) nd.print(oss);
}
void insert(string word) {
Node* node = &root;
for (auto&& w : word) {
int& i = node->child[w-'a'];
if (i == -1) {
cerr << "cap: (" << data.capacity();
data.emplace_back(Node{});
cerr << '/' << data.capacity() << ")\n";
i = data.size() - 1;
}
node = &data[i];
}
++node->words;
}
bool search(string word) {
Node* node = &root;
for (auto&& w : word) {
int& i = node->child[w - 'a'];
if (i == -1)
return false;
else {
node = &data[i];
}
}
return node->words > 0;
}
bool startsWith(string prefix) {
Node* node = &root;
for (auto&& w : prefix) {
int& i = node->child[w - 'a'];
if (i == -1)
return false;
else {
node = &data[i];
}
}
return true;
}
};
int main() {
Trie obj;
obj.insert("abcdefghijklmnopqrstuvwxyz");
cerr << obj.search("abcd") << ", " << obj.startsWith("abcd") << endl;
obj.print();
return 0;
}