c++ - 〜10000キーが追加された後のunordered_mapのセグメンテーション違反

Question

unordered_mapに挿入しようとしたときにdatact=10736の場合、セグメンテーション違反が発生します（呼び出しが障害をスローするコメント行を参照）。修正の試みについては、以下を参照してください。

SIGSEGVがスローされると、hashtable_policy.h

入力：column1 = counts、column2=16文字列のデータファイル

目的：1置換の異なるシーケンスのすべてのカウントを合計することにより、16文字のシーケンスをクラスター化します。最初に見られるシーケンスは「起源」であり、それによってすべての1置換の友人が識別されます。

擬似コード：ファイル内の各行について：

読み取りカウント、読み取りシーケンス。
シーケンスkey_valueがハッシュ'location'（タイプunordered_map）に存在する場合は、現在のカウントを追加します。
それ以外の場合は、新しいkey_valueを作成し、ここでカウントを指すようにし、すべての1置換シーケンスをこのカウントも指すように割り当てます。

コード：

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <map>

#include "matrix.h"

using namespace std;

int nuc2num(char currchar)
{   // returns 0,1,2,3 for A,C,T,G respectively
    int outnum;

    if (currchar=='A')
    {
        outnum=0;
    }
    else if (currchar=='C')
    {
        outnum=1;
    }
    else if (currchar=='T')
    {
        outnum=2;
    }
    else
    {
        outnum=3;
    }
    return outnum;
}

int main(int argc, char* argv[])
{
    //command line arguments
    //  arg1=filename, arg2=barcode sequence length, arg3=#mismatches permitted

    //input handling
    //  file format: column 1 | column 2
    //               counts   | sequence    [int | string]

    string filename;
    string funnelstring;

    // define lookup matrix; rows=ACTG, cols = ACTG without row element
    Matrix <char> sub_lookup(4,3);
    sub_lookup[0][0] = 'C';
    sub_lookup[0][1] = 'T';
    sub_lookup[0][2] = 'G';
    sub_lookup[1][0] = 'A';
    sub_lookup[1][1] = 'T';
    sub_lookup[1][2] = 'G';
    sub_lookup[2][0] = 'A';
    sub_lookup[2][1] = 'C';
    sub_lookup[2][2] = 'G';
    sub_lookup[3][0] = 'A';
    sub_lookup[3][1] = 'C';
    sub_lookup[3][2] = 'T';

    int L,k;

    int j=0;

    const int buffersize=10000;
    int currentsize=buffersize;

    int datact=0;
    int currchar;

    vector <unsigned int> ctarr(buffersize);
    vector <string> seqarr(buffersize);

    filename=argv[1];
    L=atoi(argv[2]);
    k=atoi(argv[3]);

    unsigned int sct;
    int substrlen;
    string sequence,textct;
    ifstream seqfile (filename.c_str());

    //map <string,unsigned int*> location;
    unordered_map <string,unsigned int*> location;

    if (seqfile.is_open())
    {
        getline(seqfile,textct,'\n');
        while (textct != "")
        {
            sct=atoi(textct.c_str());
            substrlen=textct.length();
            //cout << textct << endl;
            sequence=textct.substr(substrlen-L,L);
            //cout << sequence << endl;

            //is there an associated guy?
            if (location.find(sequence) != location.end()) //just asks whether this key has been assigned
            {   //there's a value in the region
                *location[sequence]+=sct;
            }
            else
            {   //no value in region, make a footprint
                ctarr[datact]=sct;
                seqarr[datact]=sequence;
                location[sequence]=&ctarr[datact]; //assign current key to point to data count


                //assign k substitution "funnel" region to point to this count as well
                for (j=0; j<L; j++)
                {
                    funnelstring=sequence;
                    currchar = nuc2num(sequence[j]);

                    if (datact==10736 && j==13)
                    {
                        cout << "here" << endl;
                        cout << sequence << endl;
                    }

                    for (k=0; k<3; k++)
                    {
                        funnelstring[j]=sub_lookup[currchar][k];

//                    if (datact==10736 && j==13)
//                    {
//                        cout << funnelstring << endl;
//                        cout << location.max_size() << " | " << location.size() << endl;
//                        string asdf;
//                        asdf="AAAAAAAAAAAAAAAA";
//                        location[asdf]=&ctarr[datact]; //still segfaults
//                    }

                        if (location.find(funnelstring) == location.end()) // asks whether this key has been assigned
                        {   //this region is not assigned to another funnel
                            location[funnelstring]=&ctarr[datact]; //LINE THAT CAUSES SIGSEGV
                        }
                    }
                }
                datact++;
                cout << datact << endl;
                if (datact>=currentsize)
                {
                    ctarr.resize(currentsize+buffersize);
                    seqarr.resize(currentsize+buffersize);
                    currentsize+=buffersize;
                }
            }

            getline(seqfile,textct,'\n');
         }
        seqfile.close();
    }

探検。

どのキーが追加されるかは関係ありません。いつdatact==10736、j=13どのキーが（unordered_map）の場所に追加されると、SIGSEGVになります。
問題のコード行（上記のコメントでマークされている）は、何度も前に呼び出され、正しく動作します。
unordered_mapをmapに交換すると、同じイベントが発生しますが、datactの数が異なります（より多くなります）。まだ低い（datact== 16-35千の間）。
このコードをほぼ正確に書き直しますが、ランダムに生成された16文字のシーケンスを使用すると、私が知る限り、完全に機能します（200,000までのdatactのsegfaultはなく、それ以上のテストは行われませんでした）。
（4）のコードでは、10000前後に再ハッシュが行われているように見えますが、これは関連しているか、偶然である可能性があります。

必要に応じて、読み取ったデータファイルを投稿できます。

編集：解決済み、の代わりにunordered_map <string,unsigned int*> location、unordered_map <string,unsigned int> location（value_typeはint *の代わりにintです）に置き換えられました。これで、value_typeはctarr[]にインデックスを保持します。正常に動作します。ありがとう！

score 5 · Accepted Answer

を呼び出すと、要素へのポインタvectorが無効になる場合がありますvector::resize()。これは、新しいサイズに適合する連続したメモリブロックを見つけるために、データ全体を移動する必要がある場合があるためです。つまり、を呼び出すとすぐにresize、すべてのlocationデータが突然役に立たないゴミになります。

可能な解決策：

必要な要素のインデックスを、ポインターではなくその値としてlocation格納します。ctarr(これは確かにプログラムのセマンティクスを変更しません。)
ポインタの代わりにlocation実際の値を保存しましょう。unsigned intプログラムロジックと、このデータの変更方法とアクセス方法によっては、これが望ましくない場合があります。

また、segfault はで発生しますが、このバグは(または)hashtable_policy.hの実装とは何の関係もないことに注意してください - ;-)のリファレンスを読まなかったのは完全にあなたの責任です: http://www.cplusplus.com/reference/ vector/vector/resize/ (セクション「イテレータの有効性」)unordered_mapvectorvector::resize()

あなたのコードについて私が気付いたもう 1 つのことは、要素operator[]へのアクセスにを使用していることです。vectorこれにより、範囲外のチェックが無効になります。私のコードであなたのようなエラーに遭遇した場合 (エラーコードから離れた場所で発生するため、追跡するのが難しい)、私の最初の行動は交換することoperator[]ですvector::at()(実際、私は常に最初からat()切り替え、証明できる場合にのみ切り替えます)。境界チェックがこの特定の目的のパフォーマンスのボトルネックであるという合理的な疑いの余地はありません)。これは問題の解決にはなりませんが、多くの場合、間違いを見つけるのに非常に役立ちます。

c++ - 〜10000キーが追加された後のunordered_mapのセグメンテーション違反

1 に答える 1

Related

Reference