C++ STL 优先级队列插入 bad_alloc 异常

Question

我正在开发一个查询处理器，它从内存中读取一长串文档 ID 并查找匹配的 ID。当它找到一个时，它会创建一个包含 docid(一个 int)和文档的等级(一个 double )的 DOC 结构，并将其推送到一个优先级队列中。我的问题是，当搜索的单词列表很长时，当我尝试将 DOC 插入队列时，出现以下异常: QueryProcessor.exe 中 0x7c812afb 处的未处理异常:Microsoft C++ 异常:内存位置 0x0012ee88 处的 std::bad_alloc..

当单词有一个短列表时，它工作正常。我尝试在我的代码中的几个地方将 DOC 插入队列，它们都工作到某一行；之后，我收到上述错误。我完全不知道出了什么问题，因为读入的最长列表小于 1 MB，并且我释放了分配的所有内存。为什么当我尝试将 DOC 推送到有能力容纳它的队列时突然出现 bad_alloc 异常(我使用了一个保留了足够空间的 vector 作为优先级队列的底层数据结构)？

我知道在不查看所有代码的情况下几乎不可能回答这样的问题，但是在这里发布太长了。我正在尽我所能，并焦急地希望有人能给我一个答案，因为我束手无策。

NextGEQ 函数逐 block 读取 docids 的压缩 block 列表。也就是说，如果它发现 block 中的 lastdocid(在一个单独的列表中)比传入的 docid 大，它会解压缩 block 并搜索直到找到正确的。每个列表都以关于列表的元数据开始，其中包含每个压缩 block 的长度和 block 中的最后一个 docid。 data.iquery 指向元数据的开头； data.metapointer 指向函数当前在元数据中的任何位置； data.blockpointer 指向未压缩 docid block 的开头，如果有的话。如果它看到它已经解压，它就会搜索。下面，当我第一次调用该函数时，它解压了一个 block 并找到了 docid；之后插入队列。第二次，甚至不需要解压；也就是说，没有分配新内存，但在那之后，插入队列会出现 bad_alloc 错误。

编辑:我进一步清理了我的代码，以便它可以编译。我还添加了 OpenList() 和 NextGEQ 函数，尽管后者很长，因为我认为问题是由其中某处的堆损坏引起的。非常感谢!

struct DOC{

    long int docid;
    long double rank;

public:
    DOC()
    {
        docid = 0;
        rank = 0.0;
    }

    DOC(int num, double ranking)
    {
        docid = num;
        rank = ranking;

    }

     bool operator>( const DOC & d ) const {
       return rank > d.rank;
    }

      bool operator<( const DOC & d ) const {
       return rank < d.rank;
    }
    };

struct listnode{

int* metapointer;
int* blockpointer;
int docposition;
int frequency;
int numberdocs;
int* iquery;
listnode* nextnode;

};

void QUERYMANAGER::SubmitQuery(char *query){

    listnode* startlist;

        vector<DOC> docvec;
        docvec.reserve(20);
        DOC doct;


    //create a priority queue to use as a min-heap to store the documents and rankings;


        priority_queue<DOC, vector<DOC>,std::greater<DOC>> q(docvec.begin(), docvec.end());

        q.push(doct);

    //do some processing here; startlist is a pointer to a listnode struct that starts the   //linked list

        //point the linked list start pointer to the node returned by the OpenList method

        startlist = &OpenList(value);
        listnode* minpointer;
        q.push(doct);


        //start by finding the first docid in the shortest list
            int i = 0;
            q.push(doct);
            num = NextGEQ(0, *startlist);
            q.push(doct);
            while(num != -1)
               {

            q.push(doct);

    //the is where the problem starts - every previous q.push(doct) works; the one after
    //NextGEQ(num +1, *startlist) gives the bad_alloc error

            num = NextGEQ(num + 1, *startlist);

         //this is where the exception is thrown
            q.push(doct);               
        }

    }



//takes a word and returns a listnode struct with a pointer to the beginning of the list
//and metadata about the list 
listnode QUERYMANAGER::OpenList(char* word)
{
    long int numdocs;

    //create a new node in the linked list and initialize its variables


    listnode n;
    n.iquery = cache -> GetiList(word, &numdocs);
    n.docposition = 0;
    n.frequency = 0;
    n.numberdocs = numdocs;

   //an int pointer to point to where in the metadata you are
    n.metapointer = n.iquery;
    n.nextnode = NULL;
  //an int pointer to point to the uncompressed block of data, if there is one
    n.blockpointer = NULL;



    return n;


}


int QUERYMANAGER::NextGEQ(int value, listnode& data)
{
     int lengthdocids;
     int lengthfreqs; 
     int lengthpos;
     int* temp;
     int lastdocid;


     lastdocid = *(data.metapointer + 2);

while(true)
{

         //if it's not the first chunk in the list, the blockpointer will be pointing to the 
        //most recently opened block and docpos to the current position in the block
    if( data.blockpointer && lastdocid >= value)
    {

            //if the last docid in the chunk is >= the docid we're looking for,
            //go through the chunk to look for a match


        //the last docid in the block is in lastdocid; keep going until you hit it
        while(*(data.blockpointer + data.docposition) <= lastdocid)
        {
            //compare each docid with the docid passed in; if it's greater than or equal to it, return a pointer to the docid
             if(*(data.blockpointer + data.docposition ) >= value)
             {

                 //return the next greater than or equal docid
                 return *(data.blockpointer + data.docposition);
             }
             else
             {
                 ++data.docposition;
             }
        }

        //read through the whole block; couldn't find matching docid; increment metapointer to the next block;
        //free the block's memory

        data.metapointer += 3;
        lastdocid = *(data.metapointer + 3);
        free(data.blockpointer);
        data.blockpointer = NULL;
    }


        //reached the end of a block; check the metadata to find where the next block begins and ends and whether 
        //the last docid in the block is smaller or larger than the value being searched for


        //first make sure that you haven't reached the end of the list
            //if the last docid in the chunk is still smaller than the value passed in, move the metadata pointer
           //to the beginning of the next chunk's metadata; read in the new metadata


            while(true)
         //  while(*(metapointers[index]) != 0 )
           {
               if(lastdocid < value && *(data.metapointer) !=0)
               {
               data.metapointer += 3;
               lastdocid = *(data.metapointer + 2);
               }


           else if(*(data.metapointer) == 0)
           {
               return -1;
             }

           else
               //we must have hit a chunk whose lastdocid is >= value; read it in
           {
                //read in the metadata
           //the length of the chunk of docid's is cumulative, so subtract the end of the last chunk 
           //from the end of this chunk to get the length

               //find the end of the metadata


                temp = data.metapointer;

            while(*temp != 0)
            {
                temp += 3;
            }
                temp += 2;
    //temp is now pointing to the beginning of the list of compressed data; use the location of metapointer
    //to calculate where to start reading and how much to read

         //if it's the first chunk in the list,the corresponding metapointer is pointing to the beginning of the query
        //so the number of bytes of docid's is just the first integer in the metadata
                if(  data.metapointer == data.iquery)
                {
                    lengthdocids = *data.metapointer;

                }

                else
                {
                    //start reading from the offset of the end of the last chunk (saved in metapointers[index] - 3)
                    //plus 1 = the beginning of this chunk

                    lengthdocids = *(data.metapointer) - (*(data.metapointer - 3));
                    temp += (*(data.metapointer - 3)) / sizeof(int); 

                   }


           //allocate memory for an array of integers - the block of docid's uncompressed
           int* docblock = (int*)malloc(lengthdocids * 5 );

           //decompress docid's into the block of memory allocated
            s9decompress((int*)temp, lengthdocids /4, (int*) docblock, true);

            //set the blockpointer to point to the beginning of the block
            //and docpositions[index] to 0
            data.blockpointer = docblock;
            data.docposition = 0;
            break;

                }

           } 

}
}

非常感谢，bsg。

Answer 1

QUERYMANAGER::OpenList 按值返回列表节点。在 startlist = &OpenList(value); 中，您然后继续获取返回的临时对象的地址。当临时文件消失时，您可能可以访问数据一段时间，然后它会被覆盖。能不能在栈上声明一个非指针的listnode startlist，直接给它赋返回值？然后删除其他用途前面的 *，看看是否能解决问题。