0

I am working on implementing a templated heap class. It has been really rough so far. I am trying to display my heap but I am getting this error:

Undefined symbols for architecture x86_64:
  "operator<<(std::__1::basic_ostream<char, std::__1::char_traits<char> >&, Heap<int> const&)", 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)

I used template in my class so the implementation of my functions in inside the header file as well, here is the hpp file: (!): No need to read the whole file, just the ostream& operator<<().

/*
 Header file for Heap implemenetation
 */

#ifndef Heap_hpp
#define Heap_hpp

#include <stdio.h>
#include <vector>
#include <iterator>
#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.
    void perculateDown(int root);
    void perculateUp();
    
public:
    Heap();
    bool checkEmpty();
    void insert(elementType 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);
    
};

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

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

template <typename elementType>
void Heap<elementType>::insert(elementType iteam){
    auto it = mySize;//iterator
    //myVecrtor.insert(it, iteam);//insert after first element(dummy)
    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;
    }
}


#endif /* Heap_hpp */

I tried all my other functions to see if I had a silly mistake or something but all worked except this one: (!): ik the use of namespace std is a bad habbit but i am using just for testing

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

int main(int argc, const char * argv[]) {
    Heap<int> h;
    h.insert(5);
    h.getHeap();
    h.getMaxIndex();
    h.getMax();
    h.removeMax();
    h.removeAtIndex(1);
    h.getHeap();
    cout<<h;
    
}

I have no idea what's the problem, tho one thing I found very close to my problem is related to the namespace std, but didn't get anything out of it. Any help would be appreciated!

1
  • Are you aware that C++ already has heap functions? Commented Apr 15, 2022 at 3:07

1 Answer 1

2

The friend declaration for operator<< that you currently have is for a non-template operator<<.

There are 2 ways to solve this:

Method 1

To solve this replace that friend declaration with a declaration that has its own parameter clause so that you've a friend template declaration, inside the class with:

template<typename elementType>
class Heap{
    //other code as before
    public:
        template<typename U>
        friend std::ostream& operator<<(std::ostream &out, Heap<U> const &h);
    
};

Demo

Method 2

Here we can forward declare both the class template Heap and operator<<.

//forward declaration for Heap<> 
template<typename T> class Heap;

//forward declaration for operator<<
template<typename T> std::ostream& operator<<(std::ostream& os, Heap<T> const &h);

template<typename elementType>
class Heap{
  //other members as before
    
public:

    friend std::ostream& operator<<<elementType>(std::ostream &out, Heap<elementType> const &h);
    
};

Demo

Sign up to request clarification or add additional context in comments.

8 Comments

The friend declaration for operator<< that you currently have is for a non-template operator<< - provided Heap is a class with template, when will such operator work?
@TheDreamsWind See this live demo for working of such non-template operator<<.
I tried but then it wouldn;t let me use the private members of the class "h.mySize" and "h.myVector" nor see my public functions like h.removeAtIndex().
Note: Now it was able to locate it and call except I can't use the members as mentioned.
@Youssof.K. I've provided 2 live demos in my answer. Did you click on them and tried them? They work so you can't say that it doesn't work. You can match you code with those live demos and find out where the problem is. They are the exact copy of you code except that i have applied the solutions mentioned in my answer to them so that you can go line by line and match with your code and find the problem. Again, make sure that you're using std::ostream instead of ostream inside all header and source files. Demo1 and Demo2.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.