未処理の例外.. Microsoft C++の例外：メモリ位置のstd :: bad_alloc

Question

大文字の（mainvect）のstruct infoオブジェクト（約8million要素）が重複しています。 pid、およびuid。

struct info 
{ 
    int pid; 
    string uid; 

} 

私は別のベクトルを有する各PIDとmainvectにおけるその発生vect1のサイズが420K要素

struct pidInfo 
{ 
    int pid; 
    int numofoccurence; 
} 

である（検索特定の指標ではない全ての主VECTそのヘルプ）の情報を含む（ vect1）

mainvectにunqiue要素を格納する場合は、vect2にしてください。

. 
. 
// sort mainvect based on pid 
sort(mainvect.begin(), mainvect.end(), sortByPId()); 

int start = 0; 
int end = 0; 
vector <string> temp; // to store uids with a specific pid 

for (int i = 0; i < vect1.size(); i++) 
{ 
    end = end + vect1[i].numofoccurence; 

    for (int j = start; j < end; j++) 
    { 
     temp.push_back(mainvect[j].uid); 
    } 

    start = start + vect1[i].numofoccurence; 

    // remove duplicate uid 
    sort(temp.begin(), temp.end()); 
    temp.erase(unique(temp.begin(), temp.end()), temp.end()); 

    // push remaining unique uids 
    for (int k = 0; k < temp.size(); k++) 
    { 
     info obb; 
     obb.pid = vect1[i].pid; 
     obb.uid = temp[k]; 
     vect2.push_back(obb); 
    } 

    // empty the temp vector to use in next i iteration 
    temp.erase(temp.begin(), temp.end()); 

} 
. 
. 

しかし、私は、コードを実行すると、次の図

Answer 1

に示すように、それはあなたが、メモリが不足している私に例外を与えました。あなたができることはいくつかあります：

1. Windowsでは32ビットプログラムをビルドしています。これは、使用可能なRAMが2 GBであることを意味します。これは、物理メモリの量がマシン上にあることを表しています。 64ビットアーキテクチャ用のプログラムをビルドして、必要なすべてのRAMにアクセスできるようにする必要があります。これを行うには、プラットフォームをx64に設定して、プロジェクトの新しい構成を作成する必要があります。
2. メモリを使用するのに賢明でなければなりません。あなたができる最も簡単なことは、大きなベクトルの場合はをstd::dequeuに置き換えることです。

std::vectorの問題は、それが大きくなるたびに新しいメモリチャンクを割り当ててすべてのデータをコピーすることです。使用しているMSVCの実装は、毎回1.5倍のベクトルで成長します。したがって、ベクトルが1 GBのメモリを使用する場合、次にサイズを変更すると1.5 GBのメモリが割り当てられ、サイズ変更中は2.5 GBのRAMが割り当てられます。

std::dequeの実装では通常、小さなチャンクでメモリが割り当てられるため、サイズ変更の問題は少なくなります。

もう1つ注目すべきことはstd::stringです。 MSVC実装はSSO (Small-String-Optimization)を使用します。 Every instance of std :: string` afairはx86上で32バイト必要です。あなたの800万要素ベクトルのすべての要素は、この記憶を無駄にしているかもしれません。

あなたのプログラムに費やしたい時間に応じて、memory-mapped filesについて知りたいことがあります。

Answer 2

私は実際にアルゴリズムの問​​題があると思います。各反復では、ソートして固有の要素のみをベクトルtempに残します。しかし、このアプローチでは、繰り返しごとにvect2に重複が追加されます。ですから、vect2にもユニークな要素だけを並べ替えて残すべきです。実際にはtempとvect2の代わりにstd::setを利用するほうがよいでしょう。

GUIDなどの固定長形式のものがある場合は、uidのためのより良い記憶域を利用することをお勧めします。

Answer 3

上記の状態では、メモリが不足しています。本当にたくさんの要素がある場合は、sqliteのような小さなデータベースを調べるのが賢明かもしれません。

しかし、質問はC++標準コンテナに関するものなので、あなたは少し問題に近づいています。あなたは多くの不必要な並べ替えやループを行っています。あなたのアルゴリズムは少なくともO（n^3）

std :: mapのような、すでにソートされたコンテナのどれかを使用してみませんか？あなたはそうのようなリストをdeduplciateことができます。

は

std::vector<info> input; 

// copy into map 
std::map<int, info> tmp; 
for (info& i : mainvect) { 
    tmp[i.pid] = i; 
} 

// copy back out 
std::vector<info> output(tmp.size()); 
std::transform(tmp.begin(), tmp.end(), output.begin(), [] (const std::pair<int, info>& p) { 
    return p.second; 
}); 

コードクリーナーは、それはO（N + LN（N））で動作しているだけではなく。または、2番目のステップをスキップし、最初にstd :: mapまたはstd :: setを使用してデータを取得します。

また、膨大な数の項目を処理する場合、std :: vectorを使用したくない場合もあります。重要な問題は、ベクトルのメモリが1つの連続したメモリである必要があることです。デキューまたはリストを使用することができます。