死亡程序：使用向量集矢量

-1

在我的算法中，我需要保留（3個字節）擴展ASCII字符的所有組合。以下是我的代碼但是當我運行這段代碼時，程序在終端發生最後一步時會死亡（BigVector.pushback）。爲什麼這樣，以及在我的情況下可以選擇什麼？死亡程序：使用向量集矢量

vector<set<vector<int> > > BigVector; 
set<vector<int> > SmallSet; 


    for(int k=0; k <256; k++) 
    { 
     for(int j=0; j <256; j++) 
     {  

      for(int m=0; m <256; m++) 
      { 
        vector<int> temp; 
       temp.push_back(k); 
       temp.push_back(j); 
       temp.push_back(m); 
       SmallSet.insert(temp); 
      } 
     } 


    } 

    BigVector.push_back(SmallSet);

PS：我要保持ASCII字符這樣的： {{（A，B，C），（A，B，d），......（Z，Z，Z ）}}

來源

2014-02-18 Xara

有多大你的籌碼？ – Johnsyweb

這是算法類嗎？如果是這樣，你應該重新考慮這個數據結構，因爲它非常低效。 – Potatoswatter

@Patatoswatter我必須做一個大集合，其中包含子集。每個子集可能包含一個或多個像這樣的集合（a，b，c）等。這就是爲什麼我使用這個數據結構。你能給我一些建議嗎？ – Xara

請注意，256^3 = 16,777,216。這是巨大的，尤其是當你使用矢量和設置！

因爲您只需要記錄256 = 2^8的信息，您可以將其存儲在char（一個字節）中。您可以將每個組合存儲在三個字符的一個元組中。內存現在爲16,777,216/1024/1024 = 16 MB。在我的電腦上，它在秒完成。

如果您接受C++ 11，我會建議使用std::array，而不是在我的舊代碼中編寫像Info這樣的輔助結構。

使用std :: array的C++ 11代碼。

vector<array<char,3>> bs; 
.... for loop 
    array<char,3> temp; 
    temp[0]=k; temp[1]=j; temp[2]=m; 
    bs.push_back(temp);

使用自制結構的C++ 98代碼。

struct Info{ 
    char chrs[3]; 
    Info (char c1, char c2, char c3):chrs({c1,c2,c3}){} 
}; 

int main() { 
    vector<Info> bs; 
    for (int k = 0; k < 256; k++) { 
     for (int j = 0; j < 256; j++) { 
      for (int m = 0; m < 256; m++) { 
       bs.push_back(Info(k,j,m)); 
      } 
     } 
    } 
    return 0; 
}

使用組合的方法。（您可以爲Info編寫包裝方法）。

// Suppose s[256] contains the 256 extended chars. 
for(auto b : bs){ 
    cout<< s[b.chrs[0]] << " " << s[b.chrs[1]] << " "<< s[b.chrs[2]] << endl; 
}

來源

2014-02-18 11:02:47

你可以請我給我一些替代品的數據結構在我的情況.. – Xara

@Zara我添加了我的解決方案。請嘗試一下，看它是否正常。 :-) –

@Zara使用C++ 11數組更新代碼。 –

第一：你的例子不符合實際的代碼。您正在創建（{（a，a，a），...，（z，z，z）}）

如前所述，您將擁有16'777'216個不同的向量。由於矢量對象，每個矢量將保存3個字符，通常約爲20個字節[1]。此外，典型的矢量實現將爲未來的push_back保留內存。

您可以通過初始化過程中指定正確的大小或使用儲備（）來避免這種：

vector<int> temp(3);

（容量（）告訴你的矢量的「真實」的大小）

的push_back使得您正在推送的對象的副本[2]，這可能會導致內存過大，從而導致程序崩潰。

16'777'216 *（3個字符+ 20開銷）* 2個拷貝=〜736MiB。
（這裏假定矢量已經用正確的大小初始化了！）

請參閱[2]以獲得複製問題的可能解決方案。

我同意Potatoswatter：你的數據結構是非常低效的。

[1] What is the overhead cost of an empty vector?
[2] Is std::vector copying the objects with a push_back?

來源

2014-02-18 11:29:45 close2

死亡程序：使用向量集矢量

回答

相關問題