添加~10000个键后,unordered_map中的分段错误

Question

当datact = 10736尝试插入unordered_map时,会发生分段错误(请参阅调用行,该调用行将调用该错误).请参阅下面的尝试修复.

当抛出SIGSEGV时,它指向我的第764行 hashtable_policy.h

INPUT:数据文件,其中column1 = count,column2 = 16个字符的字符串

目的:通过将1-替换不同序列的所有计数加在一起来聚类16个字符的序列.看到的第一个序列是"起源",通过它来识别其所有的1个替换朋友.

PSEUDOCODE:对于文件中的每一行:

1. 读取计数,读取序列.

2. 如果序列key_value存在于散列'location'(类型unordered_map)中,则添加当前计数;

3. 否则创建一个新的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();
    }

探索.

1. 不要紧添加什么键,当datact==10736和j=13,任意键添加到一个SIGSEGV(unordered_map)定位结果.
2. 有问题的代码行(由上面的注释标记)之前被调用很多次,并且运行正常.
3. 为地图交换unordered_map会导致同一事件,但数据类别不同(更高).仍然很低(datact= = 16-35千).
4. 几乎完全重写这段代码,但随机生成的16个字符的序列完美无缺,据我所知(没有高达200,000的数据段的段错误,没有测试更高).
5. 在(4)的代码中,看起来确实存在大约10000的重新散列,这可能是相关的或巧合的.

如果需要,我可以发布读取的数据文件.

编辑:解决 而不是unordered_map <string,unsigned int*> location,替换为unordered_map <string,unsigned int> location(value_type是int而不是int*).现在value_type保存ctarr []中的索引.运行很好.谢谢!

Answer 1

vector调用时,元素的指针可以无效vector::resize().这是因为可能必须移动整个数据以便找到适合新大小的连续内存块.换句话说:一旦你打电话resize,你的所有location数据都会突然变成无用的垃圾.

可能的解决方案:

• 让我们location将所需元素的索引存储ctarr为其值而不是指针.(这肯定不会改变你程序的语义.)
• 让我们location存储实际unsigned int 值而不是指针.根据您的程序逻辑以及更改和访问此数据的方式,这可能不是您想要的.

另请注意,虽然发生了段hashtable_policy.h错误,但这个错误与unordered_map(或vector)的实现无关- 完全没有阅读参考文献的错误;-) vector::resize():http://www.cplusplus.com/reference/ vector/vector/resize /("Iterator validity"部分)

我注意到你的代码的另一件事是你operator[]用来访问你的vector元素.这会禁用越界检查.如果我在我的代码遇到像你的错误来了(很难,因为它从我的错误码远的地方发生追溯),我的首要行动将是交换operator[]的vector::at()(实际上,我总是先从at()只有开关,如果我能证明毫无疑问,边界检查是这个特定目的的性能瓶颈).这对您的问题没有帮助,但通常是发现错误的宝贵帮助.