向量中的 C++ 更改对象不起作用
C++ changing object in vector doesn't work
我想使用向量来存储节点来实现一个 trie,但不知何故我的插入方法不起作用。我已经设法使用不同的实现构建了 trie 数据结构,但我想了解为什么我当前的实现不起作用。
有效(不是 childs/references 的基于索引的存储):
struct Trie {
struct Trie *references[26];
bool end; //It is true if node represents end of word.
};
不起作用(childs/references 的基于索引的存储):
struct node {
int references[26] = {0};
bool end;
};
由于插入功能错误,它不起作用。
void insert_word(string s){
node *current_node = &trie[0];
// current_node->references[4] = 9999 WORKS! Node in Trie is UPDATED
for(int i=0;i<s.size();i++){
print_trie();
int letter_num = static_cast<int>(tolower(s[i])) - static_cast<int>('a');
int next_index = current_node->references[letter_num];
cout << "letter num: " << letter_num << " next index: " << next_index << endl;
if(next_index == 0){
node new_node;
trie.push_back(new_node);
current_node->references[letter_num] = trie.size()-1; // DOESN'T WORK! Node in Trie is NOT UPDATED
cout << "new value: ";
for(auto c:current_node->references)
cout << c << " ";
cout << endl;
cout << "in for" << endl;
print_trie();
current_node = &trie.back();
} else{
current_node = &trie[next_index];
}
}
current_node->end = true;
}
问题是,当我访问 current_node
作为对 trie 向量对象的引用时,我更改了它的值。 trie 向量中的 object/node 并不总是更新。它在第二行工作,但在更远的地方它以某种方式停止工作。我想明白为什么。
这是我为简化问题而编写的简短调试程序。这里似乎一切正常。
n1.references[0] = 1;
n2.references[0] = 2;
n3.references[0] = 3;
trie.push_back(n1);
trie.push_back(n2);
trie.push_back(n3);
node *n = &trie[0];
n->references[0] = 10; // Tree is updated properly
n = &trie[1];
n->references[0] = 11; // Tree is updated properly
你能帮我理解为什么插入功能不能正常工作吗?
编辑:最小工作示例
#include <vector>
#include <string>
#include <iostream>
using namespace std;
struct node
{
int num_words;
int references [26] = {0};
bool end;
};
vector<node> trie;
int n;
void print_trie(){
cout << "#### NEW PRINT TRIE ##### " << endl;
for(int i=0;i<trie.size();i++){
cout << "node " << i << ": ";
for(int j=0;j<26;j++)
cout << trie[i].references[j] << " ";
cout << endl;
}
}
void insert_word(string s){
node *current_node = &trie[0];
// current_node->references[4] = 9999 WORKS! Node in Trie is UPDATED
for(int i=0;i<s.size();i++){
print_trie();
int letter_num = static_cast<int>(tolower(s[i])) - static_cast<int>('a');
int next_index = current_node->references[letter_num];
cout << "letter num: " << letter_num << " next index: " << next_index << endl;
if(next_index == 0){
node new_node;
trie.push_back(new_node);
current_node->references[letter_num] = trie.size()-1; // DOESN'T WORK! Node in Trie is NOT UPDATED
cout << "new reference value of node: ";
for(auto c:current_node->references)
cout << c << " ";
cout << endl;
current_node = &(trie[trie.size()-1]);
} else{
current_node = &trie[next_index];
}
}
current_node->end = true;
}
int main()
{
node root;
trie.push_back(root);
insert_word("hallohallo");
return 0;
}
只要 std::vector<T>
进行大小调整操作,所有迭代器和指向元素的指针都会 无效 。以您的 mcve 为例,说明 rails 发生的地方,请考虑标记的行:
void insert_word(string s){
node *current_node = &trie[0]; // **HERE
for(int i=0;i<s.size();i++){
print_trie();
int letter_num = static_cast<int>(tolower(s[i])) - static_cast<int>('a');
int next_index = current_node->references[letter_num];
cout << "letter num: " << letter_num << " next index: " << next_index << endl;
if(next_index == 0){
node new_node;
trie.push_back(new_node); //** RESIZE
current_node->references[letter_num] = trie.size()-1;
cout << "new reference value of node: ";
for(auto c:current_node->references)
cout << c << " ";
cout << endl;
current_node = &(trie[trie.size()-1]); // **HERE
} else{
current_node = &trie[next_index]; // **HERE
}
}
current_node->end = true;
}
在每个标有 // **HERE
的位置中,您存储了一个指向向量中托管的对象的指针。但是一旦达到容量,标有 // **RESIZE
的行可以(并且将)通过 copy/move/etc 调整整个向量的大小。这意味着 current_node
不再指向有效对象,它是一个悬空指针,但您的代码 none-the-wiser 并进入 未定义行为 。
有几种方法可以解决这个问题。如果您提前知道它,您可以 reserve
从一开始就拥有容量,但为了获得更强大的解决方案,不要使用指针作为开始。如果您通过 index 而不是指针枚举,您的解决方案将变为以下内容:
void insert_word(std::string s)
{
size_t idx = 0;
for(int i=0;i<s.size();i++){
print_trie();
int letter_num = static_cast<int>(tolower(s[i])) - static_cast<int>('a');
size_t next_index = trie[idx].references[letter_num];
std::cout << "letter num: " << letter_num << " next index: " << next_index << std::endl;
if(next_index == 0){
trie.emplace_back();
trie[idx].references[letter_num] = trie.size()-1;
std::cout << "new reference value of node: ";
for(auto c : trie[idx].references)
std::cout << c << ' ';
std::cout << std::endl;
idx = trie.size()-1;
} else{
idx = next_index;
}
}
trie[idx].end = true;
}
请注意 current_node
的所有实例是如何被 trie[idx]
替换的。更改 "current node" 现在只是更改 idx
的值的问题,即使基础向量调整大小时也是相关的。
这可能是由于类型不匹配导致的 int
已分配 size_t
尝试... = (int)trie.size()-1
#include <vector>
#include <iostream>
using namespace std;
struct node{
int num_words;
int references [26] = {}; //........... int
bool end;
};
vector<node> trie;
int n;
void print_trie(){
cout << "#### NEW PRINT TRIE ##### " << endl;
for(int i=0;i<trie.size();i++){
cout << "node " << i << ": ";
for(int j=0;j<26;j++)
cout << trie[i].references[j] << " ";
cout << endl;
}
}
void insert_word(const string& s){
node *current_node = &trie[0];
// current_node->references[4] = 9999 WORKS! Node in Trie is UPDATED
for(int i=0;i<s.size();i++){
print_trie();
int letter_num = int(tolower(s[i]) - 'a');
int next_index = current_node->references[letter_num];
cout << "letter num: " << letter_num << " next index: " << next_index << endl;
if(next_index == 0){
node new_node;
trie.push_back(new_node);
current_node->references[letter_num] = (int)trie.size()-1; //....size_t DOESN'T WORK! Node in Trie is NOT UPDATED
cout << "new reference value of node: ";
for(auto c:current_node->references)
cout << c << " ";
cout << endl;
current_node = &(trie[trie.size()-1]);
} else{
current_node = &trie[next_index];
}
}
current_node->end = true;
}
int main()
{
node root;
trie.push_back(root);
insert_word("hallohallo");
return 0;
}
我想使用向量来存储节点来实现一个 trie,但不知何故我的插入方法不起作用。我已经设法使用不同的实现构建了 trie 数据结构,但我想了解为什么我当前的实现不起作用。
有效(不是 childs/references 的基于索引的存储):
struct Trie {
struct Trie *references[26];
bool end; //It is true if node represents end of word.
};
不起作用(childs/references 的基于索引的存储):
struct node {
int references[26] = {0};
bool end;
};
由于插入功能错误,它不起作用。
void insert_word(string s){
node *current_node = &trie[0];
// current_node->references[4] = 9999 WORKS! Node in Trie is UPDATED
for(int i=0;i<s.size();i++){
print_trie();
int letter_num = static_cast<int>(tolower(s[i])) - static_cast<int>('a');
int next_index = current_node->references[letter_num];
cout << "letter num: " << letter_num << " next index: " << next_index << endl;
if(next_index == 0){
node new_node;
trie.push_back(new_node);
current_node->references[letter_num] = trie.size()-1; // DOESN'T WORK! Node in Trie is NOT UPDATED
cout << "new value: ";
for(auto c:current_node->references)
cout << c << " ";
cout << endl;
cout << "in for" << endl;
print_trie();
current_node = &trie.back();
} else{
current_node = &trie[next_index];
}
}
current_node->end = true;
}
问题是,当我访问 current_node
作为对 trie 向量对象的引用时,我更改了它的值。 trie 向量中的 object/node 并不总是更新。它在第二行工作,但在更远的地方它以某种方式停止工作。我想明白为什么。
这是我为简化问题而编写的简短调试程序。这里似乎一切正常。
n1.references[0] = 1;
n2.references[0] = 2;
n3.references[0] = 3;
trie.push_back(n1);
trie.push_back(n2);
trie.push_back(n3);
node *n = &trie[0];
n->references[0] = 10; // Tree is updated properly
n = &trie[1];
n->references[0] = 11; // Tree is updated properly
你能帮我理解为什么插入功能不能正常工作吗?
编辑:最小工作示例
#include <vector>
#include <string>
#include <iostream>
using namespace std;
struct node
{
int num_words;
int references [26] = {0};
bool end;
};
vector<node> trie;
int n;
void print_trie(){
cout << "#### NEW PRINT TRIE ##### " << endl;
for(int i=0;i<trie.size();i++){
cout << "node " << i << ": ";
for(int j=0;j<26;j++)
cout << trie[i].references[j] << " ";
cout << endl;
}
}
void insert_word(string s){
node *current_node = &trie[0];
// current_node->references[4] = 9999 WORKS! Node in Trie is UPDATED
for(int i=0;i<s.size();i++){
print_trie();
int letter_num = static_cast<int>(tolower(s[i])) - static_cast<int>('a');
int next_index = current_node->references[letter_num];
cout << "letter num: " << letter_num << " next index: " << next_index << endl;
if(next_index == 0){
node new_node;
trie.push_back(new_node);
current_node->references[letter_num] = trie.size()-1; // DOESN'T WORK! Node in Trie is NOT UPDATED
cout << "new reference value of node: ";
for(auto c:current_node->references)
cout << c << " ";
cout << endl;
current_node = &(trie[trie.size()-1]);
} else{
current_node = &trie[next_index];
}
}
current_node->end = true;
}
int main()
{
node root;
trie.push_back(root);
insert_word("hallohallo");
return 0;
}
只要 std::vector<T>
进行大小调整操作,所有迭代器和指向元素的指针都会 无效 。以您的 mcve 为例,说明 rails 发生的地方,请考虑标记的行:
void insert_word(string s){
node *current_node = &trie[0]; // **HERE
for(int i=0;i<s.size();i++){
print_trie();
int letter_num = static_cast<int>(tolower(s[i])) - static_cast<int>('a');
int next_index = current_node->references[letter_num];
cout << "letter num: " << letter_num << " next index: " << next_index << endl;
if(next_index == 0){
node new_node;
trie.push_back(new_node); //** RESIZE
current_node->references[letter_num] = trie.size()-1;
cout << "new reference value of node: ";
for(auto c:current_node->references)
cout << c << " ";
cout << endl;
current_node = &(trie[trie.size()-1]); // **HERE
} else{
current_node = &trie[next_index]; // **HERE
}
}
current_node->end = true;
}
在每个标有 // **HERE
的位置中,您存储了一个指向向量中托管的对象的指针。但是一旦达到容量,标有 // **RESIZE
的行可以(并且将)通过 copy/move/etc 调整整个向量的大小。这意味着 current_node
不再指向有效对象,它是一个悬空指针,但您的代码 none-the-wiser 并进入 未定义行为 。
有几种方法可以解决这个问题。如果您提前知道它,您可以 reserve
从一开始就拥有容量,但为了获得更强大的解决方案,不要使用指针作为开始。如果您通过 index 而不是指针枚举,您的解决方案将变为以下内容:
void insert_word(std::string s)
{
size_t idx = 0;
for(int i=0;i<s.size();i++){
print_trie();
int letter_num = static_cast<int>(tolower(s[i])) - static_cast<int>('a');
size_t next_index = trie[idx].references[letter_num];
std::cout << "letter num: " << letter_num << " next index: " << next_index << std::endl;
if(next_index == 0){
trie.emplace_back();
trie[idx].references[letter_num] = trie.size()-1;
std::cout << "new reference value of node: ";
for(auto c : trie[idx].references)
std::cout << c << ' ';
std::cout << std::endl;
idx = trie.size()-1;
} else{
idx = next_index;
}
}
trie[idx].end = true;
}
请注意 current_node
的所有实例是如何被 trie[idx]
替换的。更改 "current node" 现在只是更改 idx
的值的问题,即使基础向量调整大小时也是相关的。
这可能是由于类型不匹配导致的 int
已分配 size_t
尝试... = (int)trie.size()-1
#include <vector>
#include <iostream>
using namespace std;
struct node{
int num_words;
int references [26] = {}; //........... int
bool end;
};
vector<node> trie;
int n;
void print_trie(){
cout << "#### NEW PRINT TRIE ##### " << endl;
for(int i=0;i<trie.size();i++){
cout << "node " << i << ": ";
for(int j=0;j<26;j++)
cout << trie[i].references[j] << " ";
cout << endl;
}
}
void insert_word(const string& s){
node *current_node = &trie[0];
// current_node->references[4] = 9999 WORKS! Node in Trie is UPDATED
for(int i=0;i<s.size();i++){
print_trie();
int letter_num = int(tolower(s[i]) - 'a');
int next_index = current_node->references[letter_num];
cout << "letter num: " << letter_num << " next index: " << next_index << endl;
if(next_index == 0){
node new_node;
trie.push_back(new_node);
current_node->references[letter_num] = (int)trie.size()-1; //....size_t DOESN'T WORK! Node in Trie is NOT UPDATED
cout << "new reference value of node: ";
for(auto c:current_node->references)
cout << c << " ";
cout << endl;
current_node = &(trie[trie.size()-1]);
} else{
current_node = &trie[next_index];
}
}
current_node->end = true;
}
int main()
{
node root;
trie.push_back(root);
insert_word("hallohallo");
return 0;
}