I was implementing a Trie for Google Kickstart earlier today and the code is malfunctioning in a very strange way. I have no idea why this is happening. I narrowed down the problem in a few hours.
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
struct node{
int ends=0;
int child[26]={0};
};
vector<node> trie;
int makenode(){
trie.push_back(node());
int x=(int)trie.size() - 1;
cout<<x<<" ";
return x;
}
void insert(string &s,int root=0,int pos=0){
if(pos==(int)(s.size())){
trie[root].ends++;
return;
}
int next=s[pos]-'A';
if(!trie[root].child[next]){
// trie.push_back(node()); trie[root].child[next]=(int)trie.size()-1; //THIS LINE WORKS FINE
trie[root].child[next]=makenode();
cout<<trie[root].child[next]<<"\n";
}
insert(s,trie[root].child[next],pos+1);
}
int main(){
trie.clear();
trie.push_back(node());
string s;
cin>>s;
insert(s);
return 0;
}
The function makenode() returns x. When I print x, the values are fine but after returning the values are getting changed.
One would expect the above code to print the same integers per line but the values aren't same.
These are the values of x before and after returning from the function makenode().
Does anybody have any idea why this is happening?
(I have noticed that only the values 1,2,4,8,16,32,etc are wrong)
It's undefined behavior: you take a reference to
trie[root]
before executingmakenode()
. The function pushes back to a vector, which can then reallocate. Then the reference you've just taken becomes invalid, so you're writing to some freed memory.Oh right! That must be it! Should I reserve extra memory for the vector to avoid this undefined behaviour?
That is precisely the problem. You can see it in detail by compiling your program with
g++ -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG
and then noting the following lines on running the executable:It explicitly states that there was an attempt to reference a pointer after it was freed.
With this compilation flags you can mostly avoid such undefined behavior in C++ :)
IMO you should rather avoid this pattern at all costs, it's going to hurt you when you least expect it. The line you commented out is fine, you could also do something like
int node = makenode; trie[root].child[next] = node;
.(But yes, reserving the memory probably would help you in this case.)
As far as I remember in c++17, order of evaluation for assignment operator is forced to be rtl, So just upgrading your compiler may help
You're right. It's working normally on C++ 17. Thanks!
On a side note, Kickstart didn't support c++17, was giving CE when trying to use c++17 only features.
I forgot that GCJ switched to format where they compile code themselves.
PS: It's funny how Google promotes using pre-release clang inside but can't provide 3years old standard
Tbh neither does Atcoder (gcc5 only), while CF just moved on from gcc7 32-bit. Not to mention other languages with highly outdated compilers. The absolute state of compilers on OJ systems.
One usable feature is fold expression even in C++14.