0

I am trying to implement a priority queue with an unsorted array and hit a wall when I received a Segmentation fault:11. I used gdb and got the error:

Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: KERN_INVALID_ADDRESS at address: 0x0000000000000000
0x00000001000017fa in Item<std::string>::setKey (this=0x0, k=3) at PriorityQueueArray.h:27
27      void setKey(const int k) { key = k; }
(gdb) backtrace
#0  0x00000001000017fa in Item<std::string>::setKey (this=0x0, k=3) at PriorityQueueArray.h:27
#1  0x0000000100001b58 in PriorityQueueArray<std::string>::insertItem (this=0x7fff5fbffb00, k=3, x=@0x7fff5fbffaf8) at PriorityQueueArray.h:48
#2  0x0000000100001430 in main () at PriorityQueue.cpp:50

My code is: `

//
//  PriorityQueueArray.h
//  Assignment5
//
//  Created by Danielle Crowley on 4/2/13.
//  Copyright (c) 2013 Danielle Crowley. All rights reserved.
//

#ifndef Assignment5_PriorityQueueArray_h
#define Assignment5_PriorityQueueArray_h
#include <vector>
using namespace std;


//item class
template<typename ElemType>
class Item {
private:
    int key;
    ElemType elem;
    Item *loc;

public:
    Item(const int k=0, const ElemType& e=ElemType()): key(k), elem(e) { } //constructor
    const int getKey() const { return key; }
    const ElemType& getElem() const { return elem; }
    void setKey(const int k) { key = k; }
    void setElem(const ElemType& e) { elem = e; }

};

template <typename ElemType>
class PriorityQueueArray{
protected:
    typedef Item<ElemType> Item;
public:
    vector<Item> A;
    PriorityQueueArray(){}
    int size() const {return A.size();}
    bool isEmpty() const{
        if(A.size() == 0)
            return true;
        else
            return false;
    }
    void insertItem(int k, const ElemType& x){
        if(A.size()==0){
            A[0].setKey(k);
            A[0].setElem(x);
        }
        else{
            A[size() - 1].setKey(k);
            A[size() - 1].setElem(x);
        }
    }

    int removeMin(){
        int comparisons = 0;

        if(isEmpty()) {}//throw (EmptyArray);

        else{
            int temp;
            int i;
            int min = A[0].getKey();
            for(i = 1; i!= A.size(); i++){
                comparisons++;
                if(A[i].getKey() < min){
                    min = A[i].getKey();
                    temp = i;
                }
            }
            A[A.size()-1] = A[temp];
        }
        return comparisons;
    }

    const ElemType& minElement(){

        if(isEmpty()) {}//throw (EmptyArray);

        else{
            int temp;
            int i;
            int min = A[0].getKey();
            for(i = 1; i!= A.size(); i++){
                if(A[i].getKey() < min){
                    min = A[i].getKey();
                    temp = i;
                }
            }
            return A[temp].getElem();
        }
    }
    int minKey(){
        int i;
        int min = A[0].getKey();
        for(i = 1; i!= A.size(); i++){
            int next = A[i].getKey();
            if(next < min)
                min = A[i].getKey();
        }
        return min; 
    }


};



#endif

If there is anyway someone could help me out I would really appreciate it!!!

2
Contributors
1
Reply
7
Views
3 Years
Discussion Span
Last Post by deceptikon
0

You're trying to use the subscript operator on an empty vector. A vector is not an array, and you need to take care go make sure that there's enough room before indexing one. Consider something like this instead:

void insertItem(int k, const ElemType& x){
    A.push_back(Item(k, x));
}
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.