0

I am trying to create a templated heap class. I worked out everything and no problem has been giving to me until I tried to create an instance of my object in my main to test it out.

Here is the hpp file:

/*
 Header file for Heap implemenetation
 */

#ifndef Heap_hpp
#define Heap_hpp

#include <stdio.h>
#include <vector>
#include <string>
#include <iostream>



template<typename elementType>
class Heap{
private:
    std::vector<elementType> myVecrtor;
    int mySize = 1; //The minimum size is 1 since the first element is a dummy.
    
public:
    Heap();//
    bool checkEmpty();//
    void insert(int iteam);//
    int getSize();//
    std::vector<elementType> getHeap();//
    elementType getMax();//
    int getMaxIndex();//
    void removeMax();//
    void removeAtIndex(int index);//
    friend std::ostream& operator<<(std::ostream &out, Heap const &h);//
    void perculateDown(int root);//
    void perculateUp();//
};

#endif /* Heap_hpp */

And here is the cpp file: (no need to read it anything other than the constructor function)

#include "Heap.hpp"

template <typename elementType>
Heap<elementType>::Heap(){
}

//I don't think you need more to read everything beside the constructor method.

template <typename elementType>
bool Heap<elementType>::checkEmpty(){
    if(mySize > 1)
        return true;
    else
        return false;
}

template <typename elementType>
void Heap<elementType>::insert(int iteam){
    if(mySize == 0){
        myVecrtor.push_back(NULL);
    }
    myVecrtor.push_back(iteam);
    mySize++;
    perculateUp();
}

template <typename elementType>
std::vector<elementType> Heap<elementType>::getHeap(){
    return  myVecrtor;
}

template <typename elementType>
elementType Heap<elementType>::getMax(){
    return myVecrtor[getMaxIndex()];
}

template <typename elementType>
int Heap<elementType>::getMaxIndex(){
    int maxIndex = 1;
    elementType max = myVecrtor[maxIndex];
    for(int i = 0; i < myVecrtor.size(); i++){
        if(max < myVecrtor[i])
            maxIndex = i;
    }
    return maxIndex;
}

template <typename elementType>
void Heap<elementType>::removeMax(){
    int maxIndex = getMaxIndex();
    myVecrtor[maxIndex] = myVecrtor[mySize];
    mySize--;
    perculateDown(maxIndex);
}

template <typename elementType>
void Heap<elementType>::removeAtIndex(int index){
    myVecrtor[index] = myVecrtor[mySize];
    mySize--;
    perculateDown(index);
}

template <typename elementType>
std::ostream& operator<<(std::ostream &out, const Heap<elementType> &h){//it is giving me the error here
    out<<"\t\tHeap:";
    for(int i = 0; i < h.mySize; i++){
        out<<h.myVecrtor.at(i);
    }
    return out;
}

template <typename elementType>
void Heap<elementType>::perculateUp(){
    int loc = mySize - 1;
    int parent = loc /2;
    while(parent >= 1 && myVecrtor[loc] > myVecrtor[parent]){
        elementType temp = myVecrtor[parent];
        myVecrtor[parent] = myVecrtor[loc];
        myVecrtor[loc] = temp;
        loc = parent;
        parent = loc / 2;
    }
}

template <typename elementType>
void Heap<elementType>::perculateDown(int root){
    int r = root, c = r*2;
    while (r < mySize - 1) {
        if(c < mySize && myVecrtor[c] < myVecrtor[c+1])
            c++;
        if(myVecrtor[r] < myVecrtor[c]){
            elementType temp = myVecrtor[r];
            myVecrtor[r] = myVecrtor[c];
            myVecrtor[c] = temp;
            r = c;
            c *= 2;
        }
        else
            break;
    }
}

I was simply testing the creation of the object in my main:

#include <vector>
#include "Heap.hpp"
#include <ostream>
using namespace std;

int main(int argc, const char * argv[]) {
    Heap<int> Hello;
/* the problem occurs here:
    Undefined symbols for architecture x86_64:
      "Heap<int>::Heap()", referenced from:
          _main in main.o
    ld: symbol(s) not found for architecture x86_64
    clang: error: linker command failed with exit code 1 (use -v to see invocation)*/
}

Am i doing something wrong or did I miss anything by any chance? Any suggestion would be helpful.

  • Template classes must have their method definitions in the header file or have explicit specializations in the header file. The linker can't find the definitions this way. – vikAy Apr 14 '22 at 22:53
  • @vikAy I didn't understand. Did you mean I should create explicitly a Heap? – Youssof. K. Apr 15 '22 at 00:04
  • Move the definitions of the functions from the cpp file into the header file or do ``` Heap::Heap(); Heap::checkEmpty(); ... ``` declarations in the header. I recommend you the first approach, because the second is not standard for classes e.g. what will happen if I want to use Heap, Heap, Heap, etc.. – vikAy Apr 15 '22 at 09:27
  • Yes moving the cpp file function into the hpp file made the trick. – Youssof. K. Apr 15 '22 at 13:28

0 Answers0