c++ - 仅由非常大的随机输入引起的分段故障核心在出队前转储到 pqueue 堆中

Question

你好，我正在关注斯坦福大学的 CS106b 编程抽象，这是一门用 C++ 和 PQueue 分配(优先级队列)(基于堆的实现)教授的编程类(class)，当从 pqueue 中取出东西时，我有这种段错误核心转储行为我在其中查询了大量随机性质的条目，它所需的确切数量因运行而异，它可以是 10000 到 70000 之间的任何条目，如果我将排序的输入排队，则不会出现问题，例如lupe 计数器，它甚至可以是 10000000 个条目。我花了几个小时试图找到错误，但我找不到它我的猜测是我必须在内存管理方面做错事但是我使用的 PQueue::doubleCapacity() 方法基于工作 vector 类中的一个方法，我认为入队和出队方法很好，因为 pqueue 对于仍然相当大的条目(小于 10000)可以正常工作。这不是那种可以轻易用谷歌搜索的问题，所以请帮助下面的代码。该代码使用了 CS106 库中的一些类，可以在 http://sourceforge.net/projects/progabstrlib/ 找到但我希望它足够简单，这样您就不需要编译它来告诉我我做错了什么。

如果这很重要，我正在使用 g++ 在 Ubuntu 12.04 上工作

/*
 * File: pqueue.h
 */

#ifndef _pqueue_h
#define _pqueue_h

#include "genlib.h"
#include "vector.h"
#include "disallowcopy.h"

class PQueue
{
  public:
    PQueue();
    ~PQueue();
    bool isEmpty();
    int size();
    void enqueue(int newElem);
    int dequeueMax();
    /*
     * needed for assigment puprposses there are three more PQueue implementation
     * so it is needed to compare memory speed trade of.
     */
    int bytesUsed();
    string implementationName();
    void printDebuggingInfo();
    bool printDebugToFile(string fileName);

  private:
    template <typename Type>
void PrintArry(Type arr[], int size);
DISALLOW_COPYING(PQueue)
static const int START_SIZE = 2;
int* entries;
int _capacity_, _size_;
void doubleCapacity();
void halfCapacity();
void swap(int& one, int &two);
};
#endif

// ---------------------------------------------------------------------------------------------
/*
 * File: pqheap.cpp
 * --    ----------------
 */

//#include "pqueue.h"  // commented out so i can compile this whole file at once
#include "genlib.h"
#include <iostream>
#include <sstream>
#include <fstream>

PQueue::PQueue()
{
    entries = new int[START_SIZE];
    _capacity_ = START_SIZE;
    _size_ =  0;
    /*
     * i am not using first cell so i want to know what should be in it this is because of
     * the fact that in the way in which i have implemented heap based PQueue the acuall values
     * are stored form number 1 and not 0; so child of value x can be reach by multiplying
     * the index of it by two adding 1 for the second child;
     */
    entries[_size_] = -888;
}

PQueue::~PQueue()
{
    if (entries != NULL) delete[] entries;
}

bool PQueue::isEmpty()
{
    return (_size_ == 0);
}

int PQueue::size()
{
    return _size_;
}

/*
 * the heap enqueuing works by adding new value to the end of the array and bubrling it up to the
 * wright position by compare with its parent and swap if necesery.
 */
void PQueue::enqueue(int newValue)
{
    int curValPos = ++_size_;
    if(_size_ == _capacity_)
        doubleCapacity();
    entries[curValPos] = newValue;

    // bubbling value up to its proper position;
    while(curValPos > 1)
    {
        int parentPos = curValPos/2;
        if(newValue < entries[parentPos])
            break;
        else
        {
            swap(entries[curValPos], entries[parentPos]);
            curValPos = parentPos;
        }
    }
}

/*
 * dequeuing is done by taking the highest value ( value from index 1 ) and then to repare the
 * queue last value is copied to the first position and then buubled down till it reaches
 * its proper position, it is done by comparison with children of the current position and
 * swaping while nesessery.
 */
int PQueue::dequeueMax()
{
    if (isEmpty())
        Error("Tried to dequeue max from an empty pqueue!");
    if(_capacity_ > (_size_*2)+10)
        halfCapacity();
    int curPos = 1;
    int maxValue = entries[curPos];
    //cout << maxValue << "|" ;
    entries[curPos] = entries[_size_];

    _size_ -= 1;
    int biggerChild = 0;

    while(biggerChild < _size_)
    {
        biggerChild = curPos*2;
        if(entries[biggerChild] < entries[biggerChild+1])
            biggerChild += 1; // the second child is bigger than the first
        // if the bigger child is smaller than newVal or if the current
        // position does not have children
        if(entries[curPos] >= entries[biggerChild] || biggerChild > _size_)
            break;
        else
        {
            swap(entries[curPos], entries[biggerChild]);
            curPos = biggerChild;
        }
    }
    return maxValue;
}

int PQueue::bytesUsed()
{
    cout << endl << "______________________ " << endl;
    cout << "SIZE OF THIS = " << sizeof(*this) << endl;
    cout << "SIZE OF ENTRIES = " << sizeof(*entries) << endl;
    cout << "______________________ " << endl;
    return sizeof(*this) + sizeof(int)*_size_;
}


string PQueue::implementationName()
{
    return "( heap )";
}

void PQueue::printDebuggingInfo()
{
    cout << "------------------ START DEBUG INFO ------------------" << endl;
    cout << "Pqueue contains " << _size_ << " entries" << endl;
    for (int i = 1; i <= _size_; i++)
        cout << entries[i] << " ";
    cout << endl << endl;

    /*
     * the print out is helpful only for the top few nodes and children.
     */
    int numInCurRow = 1 , numInPrewRow = 1;
        for (int i = 1; i <= _size_; i++)
        {
            cout << entries[i] << "|";
            numInCurRow--;
            if(numInCurRow == 0)
            {
                cout << endl;
                numInPrewRow *= 2;
                numInCurRow = numInPrewRow;
            }
        }
    cout << endl;
    cout << "------------------ END DEBUG INFO ------------------" << endl;
}

bool PQueue::printDebugToFile(string fileName)
{
    ofstream outFile;
    string str = fileName;
    outFile.open(str.c_str());
    if(outFile.fail())
    {
        cout << "WriteVectorToFile could not open file " + fileName << endl;
        return false;
    }
    outFile << "------------------ START DEBUG INFO ------------------" << endl;
    outFile << "Pqueue contains " << _size_ << " entries" << endl;
    for (int i = 1; i <= _size_; i++)
        outFile << entries[i] << " ";
    outFile << endl << endl;

    int numInCurRow = 1 , numInPrewRow = 1;
        for (int i = 1; i <= _size_; i++)
        {
            outFile << entries[i] << "|";
            numInCurRow--;
            if(numInCurRow == 0)
            {
                outFile << endl;
                numInPrewRow *= 2;
                numInCurRow = numInPrewRow;
            }
        }
        outFile << endl;
        outFile << "------------------ END DEBUG INFO ------------------" << endl;

        outFile.close();
    return true;

}

void PQueue::doubleCapacity()
{
    _capacity_ *= 2;
    int* biggerArry = new int[_capacity_];
    cout << "resizing capacity from " << _capacity_/2 << "  new capacity = " << _capacity_ << endl;
    for(int i = 0; i <= _size_; i++)
        biggerArry[i] = entries[i];
    delete[] entries;
    entries = biggerArry;

}

/*
 *
 */
void PQueue::halfCapacity()
{
    _capacity_ /= 2;
    int* halfArry = new int[_capacity_];
    cout << endl <<" downsizing capacity from " << _capacity_*2 << "  new capacity = " << _capacity_ << endl;
    for(int i = 0; i < _capacity_; i++)
        halfArry[i] = entries[i];
    delete[] entries;
    entries = halfArry;
}


void PQueue::swap(int &one, int &two)
{
    int tmp = one;
    one = two;
    two = tmp;
}

//---------------------------------------------------------------------------------------------

/*
 * main.cpp the driver
 */

/* File: main.cpp
 * --------------
 * Simple main module for PQueue assignment.
 */

//#include "pqheap.cpp"  // commented out so i can compile this whole file at once
#include <iostream>
#include "genlib.h"
#include "simpio.h"
#include "random.h"
#include <ctime>
#include <fstream>
#include "vector.h"
using namespace std;

/*
 * auxiliary functions
 */
string iToS(int x);
int sToI(string str);

bool ReadVectorFromFile(Vector<int> &v, string fileName);

template <typename Type>
bool WriteVectorToFile(Vector<Type> v, string fileName);



int main()
{
    Randomize();
    PQueue pq;

    while(true)
    {

        cout << "how big queue do we want to work with ? "+pq.implementationName() << endl;
        int y, x = GetInteger();
        Vector <int> v;

        /*
         * "1000000.vec" file contains 1000000 unsorted integers with no repetitions,
         * use of it produces the same segmentation fault core dumped it is cometed out for now
         */
        //ReadVectorFromFile(v,"1000000.vec");

        double start = double(clock())/1000000;
        for(int i = 0; i < x; i++)
        {
            pq.enqueue(RandomInteger(0,i));
        }

        double stop = double(clock())/1000000;
        cout << "time needed for enqueue of size "<< x << " = " << stop-start << endl;

        //v.clear();
        pq.printDebugToFile("debug."+ iToS(x)+ ".debug");

        /*
         * it seems that even dequeung a few values from the top produces the error
         */
        cout << "how much to dequeue ?" << endl;
        y = GetInteger();
        start = double(clock())/1000000;
        for(int i = 0; i < y; i++)
        {
            //pq.printDebuggingInfo();
            v.add(pq.dequeueMax());
        }
        stop = double(clock())/1000000;
        cout << "time needed for dequeue "+iToS(y)+" elements from PQ of size "<< x << " = " << stop-start << endl;

        WriteVectorToFile(v, "QUEUE_" + iToS(x) + ".test");
    }

    return (0);
}

//---------------------------------------------------------------------------------

string iToS(int x)
{
    ostringstream convert;
    convert << x;
    return convert.str();
}

int sToI(string str)
{
    istringstream converter(str);
    int n;
    converter >> n;
    return n;
}

bool ReadVectorFromFile(Vector<int> &v, string fileName)
{
    ifstream inFile;
    inFile.open(fileName.c_str());
    if(inFile.fail())
    {
        cout << " ReadVectorFromFile could not read from the file " + fileName << endl;
        return false;
    }
    string line;
    while(true)
    {
        getline(inFile, line);
        if(inFile.fail())
            break;
        v.add(sToI(line));
    }
    inFile.close();
    return true;
}

template <typename Longboard>
bool WriteVectorToFile(Vector<Longboard> v, string fileName)
{
    ofstream outFile;
    string str = fileName;
    outFile.open(str.c_str());
    if(outFile.fail())
    {
        cout << "WriteVectorToFile could not open file " + fileName << endl;
        return false;
    }
    for(int i = 0; i < v.size(); i++)
    {
        outFile << v[i];
        outFile << endl;
    }
    outFile.close();
    return true;
}

Answer 1

乍一看，您对 <= _size_ 的使用看起来很可疑。好像_size_表示队列中元素的个数，[0, _capacity]。因此，最后一个元素的索引应该是_size_ - 1。

不过请记住，您必须确保检查 isEmpty()在你索引之前 [_size_-1] , 以防万一_size_为 0。