C++でのアドレス衝突問題

vector_memory_location_conflict.md

何が起きたか

CKYアルゴリズムをC++で書いていた際に、std::vector<vector> cky という２次元vectorを用意し cky.numberというメンバに 数値を代入していたところ、ある座標が同じメモリアドレスをさしていたことが判明。

具体的には、

0x7fa877c02dd0 0x7fa877c02e38 0x7fa877c02ea0 0x7fa877c02f08 0x7fa877c02f70 0x7fa877c02fd8 0x7fa877c03040 
0x7fa877c02ea8 0x7fa877c02f10 0x7fa877c02f78 0x7fa877c02fe0 0x7fa877c03048 0x7fa877c030b0 
0x7fa877c02fe0 0x7fa877c03048 0x7fa877c030b0 0x7fa877c03118 0x7fa877c03180 
0x7fa877c03118 0x7fa877c03180 0x7fa877c031e8 0x7fa877c03250 
0x7fa877c03250 0x7fa877c032b8 0x7fa877c03320 
0x7fa877c03388 0x7fa877c033f0 
0x7fa877c034c0 

&cky[2][2].number 0x7fa877c02fe0
&cky[3][3].number 0x7fa877c03118
&cky[4][4].number 0x7fa877c03250
&cky[1][4].number 0x7fa877c02fe0
&cky[2][5].number 0x7fa877c03118
&cky[5][6].number 0x7fa877c03250

と &cky[2][2].numberと&cky[1][4].numberが0x7fa877c02fe0を
&cky[3][3].numberと&cky[2][5].numberが0x7fa877c03118を
&cky[4][4].numberと&cky[5][6].numberが0x7fa877c03250を

さしていることが判明。

どの様にstd::vector<vector> ckyの領域を確保していたか

構造体Ckyのメンバの初期値をそれぞれ与え、それをcky_initとして宣言し、それをcky_size分、確保することで実現。

vector<string> wordClass;
vector<pair<string, int> > first;
vector<pair<string, int> > second;
wordClass.push_back("");
first.push_back(make_pair("", 0));
second.push_back(make_pair("", 0));
Cky cky_init = (Cky){-1, "", wordClass, first, second};
vector<Cky> cky_vecotr;
// 初期化用のCkyを用意
cky_vecotr.push_back((Cky){0, "", wordClass, first, second});
vector<vector<Cky> > cky(cky_size, cky_vecotr);

何が悪かったのか

std::vectorのコンストラクタで, Nx0のサイズを指定していた為。

どの様にして改善したか

改善1

内側のstd::vecotorのサイズを指定する

vector<vector<Cky> > cky(cky_size, vector<Cky>(cky_size));

改善後のメモリアドレス

0x7f8ec0820600 0x7f8ec0820668 0x7f8ec08206d0 0x7f8ec0820738 0x7f8ec08207a0 0x7f8ec0820808 0x7f8ec0820870 
0x7f8ec0839e68 0x7f8ec0839ed0 0x7f8ec0839f38 0x7f8ec0839fa0 0x7f8ec083a008 0x7f8ec083a070 
0x7f8ec08536d0 0x7f8ec0853738 0x7f8ec08537a0 0x7f8ec0853808 0x7f8ec0853870 
0x7f8ec086cf38 0x7f8ec086cfa0 0x7f8ec086d008 0x7f8ec086d070 
0x7f8ec08867a0 0x7f8ec0886808 0x7f8ec0886870 
0x7f8ec08a0008 0x7f8ec08a0070 
0x7f8ec08b9870 

&cky[2][2].number0x7f8ec08536d0
&cky[3][3].number0x7f8ec086cf38
&cky[4][4].number0x7f8ec08867a0
&cky[1][4].number0x7f8ec0839fa0
&cky[2][5].number0x7f8ec0853808
&cky[5][6].number0x7f8ec086d070

改善2

push_backを使用することで、cky_size * cky_size分を逐次末尾へ追加することで実現

for(i = 0; i < cky_size; i++){
  for(j = 0; j < cky_size; j++){
    cky.push_back(cky_vecotr);
   }
 }

###　改善後のメモリアドレス

0x7fee41c02ed0 0x7fee41c02f38 0x7fee41c02fa0 0x7fee41c03008 0x7fee41c03070 0x7fee41c030d8 0x7fee41c03140 
0x7fee41c02ff8 0x7fee41c03060 0x7fee41c030c8 0x7fee41c03130 0x7fee41c03198 0x7fee41c03200 
0x7fee41c03190 0x7fee41c031f8 0x7fee41c03260 0x7fee41c032c8 0x7fee41c03330 
0x7fee41c032a8 0x7fee41c03310 0x7fee41c03378 0x7fee41c033e0 
0x7fee41c034a0 0x7fee41c03508 0x7fee41c03570 
0x7fee41c035d8 0x7fee41c03640 
0x7fee41c036f0 
&cky[2][2].number0x7fee41c03190
&cky[3][3].number0x7fee41c032a8
&cky[4][4].number0x7fee41c034a0
&cky[1][4].number0x7fee41c03130
&cky[2][5].number0x7fee41c032c8
&cky[5][6].number0x7fee41c033e0

と、衝突していない事がわかった

参考

C++のvectorまとめ https://qiita.com/ysuzuki19/items/df872d91c9c89cc31aee#2%E6%AC%A1%E5%85%83%E9%85%8D%E5%88%97-2