lundi 2 octobre 2017

Google test - Expression: vector subscript out of range

I'm doing an assignment for school, where we have to implement different functions for a heap. Using Google Test to test the program, it gives me the following error.

My code is as follows, as a template of the class MinHeap:

    void insert(const T& x)
    {
        heap.push_back(x);
        percolateUp(heap.size());
    }

    void remove()
    {
        heap[0] = heap.back();
        heap.pop_back();
        percolateDown(0);
    }

    bool isEmpty() const
    {   
        return heap.empty();
    }

    T peek() const
    {

        if (heap.empty())
        {
            throw exception("Heap is empty");
        }
        return heap[0];
    }

private:

    void percolateUp(size_t i)
    {
        if (i != 0)
        {
            if (heap[i] < heap[parent(i)])
            {
                swap(i, parent(i));
                percolateUp(parent(i));
            }
        }
    }

    void percolateDown(size_t i)
    {
        if (!heap.empty())
        {
            if (heap[i] > heap[smallest(i)])
            {
                swap(i, smallest(i));
                percolateDown(smallest(i));
            }

        }
    }

    size_t smallest(size_t i) const // returns index of smallest of i and its parents
    {
        size_t small = i;

        if (left(i)  < heap.size() &&
            heap[i]> heap[left(i)])
            small = left(i);

        if (right(i) < heap.size() &&
            heap[i]> heap[right(i)] &&
            heap[right(i)]< heap[left(i)])
            small = right(i);

        return small;
    }

    void swap(size_t x, size_t y)
    {
        T temp = heap[x];
        heap[x] = heap[y];
        heap[y] = temp;
    }

    size_t parent(size_t i) const { return (i - 1) / 2; }
    size_t left(size_t i)   const { return 2 * i + 1; }
    size_t right(size_t i)  const { return 2 * i + 2; }

    vector<T> heap;
};

I'm then testing the code using a Google Test .cpp file provided by my professor.

Aucun commentaire:

Enregistrer un commentaire