Why am I getting the error 'undefined reference to `MinHeap::insert(char, int)`'

Question

I am currently trying to implement a min heap, however, I am running into an issue. I am having difficulty determining why my code is not linking properly when I compile it. The files, commands, and error are as follows:

min_heap.h

#ifndef MIN_HEAP_H
#define MIN_HEAP_H

#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
struct HeapNode {
  HeapNode(const T data, const int key) : data(data), key(key) {}
  bool operator<(const HeapNode<T>& rhs) {return this->key < rhs.key;}
  bool operator<=(const HeapNode<T>& rhs) {return this->key <= rhs.key;}

  T data;
  int key;
};

template <typename T>
class MinHeap {
  public:
    MinHeap() {};
    ~MinHeap() {};

    void insert(const T data, const int key);
    T extract_min();
    T peek() const;
    int size() const;

  private:
    vector<HeapNode<T>> heap;
};

#endif

min_heap.cpp

#include <iostream>
#include "min_heap.h"
using namespace std;

template <typename T>
void MinHeap<T>::insert(const T data, const int key){
    cout << "Insertion." << endl;
    if(this->heap.size() == 0){
        cout << "adding first node" << endl;
        this->heap.push_back(new HeapNode<T>(data, key));
    }else{
        cout << "not first node." << endl;
        this->heap.push_back(new HeapNode<T>(data, key));
        int currentIndex = this->heap.size() - 1;
        while(((currentIndex - 1) / 2) >= 0){
            if(this->heap[(currentIndex - 1) / 2] > this->heap[currentIndex]){
                swap(this->heap[currentIndex], this->heap[(currentIndex - 1) / 2]);
                currentIndex = ((currentIndex - 1) / 2);
            }else{
                break;
            } 
        }
    }
}


template <typename T>
T MinHeap<T>::extract_min(){                          
  T data;
    data = NULL;
   return data;
}

template<typename T>
T MinHeap<T>::peek() const{
    T data;
    if(this->heap.size() == 0){
        cout << "size: 0" << endl;
        data = NULL;
    }else{
        cout << "something in there" << endl;
        data = this->heap[0];
    }

    return data;
}

template<typename T>
int MinHeap<T>::size() const { 
    return this->heap.size();
};

customMain.cpp

#include <iostream>
#include "min_heap.h"
using namespace std;

int main(){
    MinHeap<char> heap = MinHeap<char>();

    const char data = 'a';
    const int key = 7;
    heap.insert(data, key);

    return 0;
}

I am compiling the files above with the following

g++ -c min_heap.cpp
g++ -c customMain.cpp
g++ min_heap.o customMain.o

The error:

customMain.o:customMain.cpp:(.text+0x41): undefined reference to `MinHeap<char>::insert(char, int)'
collect2.exe: error: ld returned 1 exit status

Any help would be greatly appreciated!

Answer 1

Two options.

1) Move the template implementations out of the cpp file, and put them in the header. The compiler, when compiling main.cpp, cannot see the code it needs to generate the specialisation for char, so you end up being left with an unresolved external. Moving the code to the header will solve the issue (almost all template code resides in header files)

2) You can export specialisations from the cpp file, but then the types are locked down in advance (i.e. you can only use the exported types), which kinda reduces the flexibility and whole point of using templates. That's why 99.99% of people choose option 1, 99.99% of the time.

// export specialisations for char, short, int, and float
template class MinHeap<char>;
template class MinHeap<short>;
template class MinHeap<int>;
template class MinHeap<float>;