C++ undefined reference to (functions)

Question

I'm using a single header file to declare a bunch of subroutines to a bunch of sorting algorithms. When I try to call them from my main.cpp file, I get the error. I'm confused why because I have declared my functions correctly in the header file and I've defined them in the corresponding .cpp file. I've included the header file in both my .cpp files. Here is my code:

SortingAlgorithms.cpp

#include "SortingAlgorithms.h"
#include <cstdlib>
#include <iostream>
#include <vector>
#include <time.h>
#include <string>

using namespace std;

int listSize;
string listType;

int checkType(string listType)
{
    if (listType == "int" || listType == "Int" || listType == "integer" || listType == "Integer")
    {
        return 1;
    } 
    else if (listType == "doub" || listType == "Doub" || listType == "double" || listType == "Double")
    {
        return 2;
    }
    else if (listType == "char" || listType == "Char" || listType == "character" || listType == "Character")
    {
        return 3;
    }
    else if (listType == "string" || listType == "String" || listType == "str" || listType == "Str")
    {
        return 4;
    }
}

template <typename E>
vector<E> generateList(string listType)
{   
    vector<E> list;
    if (checkType(listType) == 1)
    {
        for (int i = 0; i < listSize; i++)
        {
            int random = rand() % 10001;
            list.push_back(random);
        }
    } 
    else if (checkType(listType) == 2)
    {
        for (int i = 0; i < listSize; i++)
        {
            double random = (10000 * (double)rand() / (double)RAND_MAX);
            list.push_back(random);
        }
    }
    else if (checkType(listType) == 3)
    {
        for (int i = 0; i < listSize; i++)
        {
            char random = alphabet[rand() % (sizeof(alphabet) - 1)];
            list.push_back(random);
        }
    }
    else if (checkType(listType) == 4)
    {
        /*
        string str;
        for (int i = 0; i < listSize; i++)
        {
            int randomChar = rand() % (26 + 26 + 10);
            if (randomChar < 26)
                str += 'a' + randomChar;
            else if (randomChar < 26 + 26)
                str += 'A' + randomChar - 26;
            else
                str += '0' + randomChar - 26 - 26;
        }
        list.push_back(str);
         */
    }
    else
    {
        cout << "Invalid type\n";
        exit(0);
    }

    return list;
}

template <typename E>
void printVector(vector<E>& list, string listType)
{
    typename vector<E>::iterator it;
    for (it = list.begin(); it != list.end(); it++)
        cout << *it << " ";
}

template <typename E>
void insertionSort(vector<E>& list)
{
    E i, j, tmp;

    for (i = 1; i < list.size(); i++)
    {
        j = i;
        tmp = list[i];
        while (j > 0 && tmp < list[j-1])
        {
            list[j] = list[j-1];
            j--;
        }
        list[j] = tmp;
    }
}

template <typename E>
vector<E> merge(vector<E>& list, vector<E>& left, vector<E>& right)
{
    vector<E> result;
    unsigned left_it = 0, right_it = 0;

    while(left_it < left.size() && right_it < right.size())
    {
        if(left[left_it] < right[right_it])
        {
            result.push_back(left[left_it]);
            left_it++;
        }
        else
        {
            result.push_back(right[right_it]);
            right_it++;
        }
    }

    while(left_it < left.size())
    {
        result.push_back(left[left_it]);
        left_it++;
    }

    while(right_it < right.size())
    {
        result.push_back(right[right_it]);
        right_it++;
    }
    list = result;              
    return list;
}

template <typename E>
vector<E> mergeSort(vector<E>& list)
{
    if(list.size() == 1)
    {
        return list;
    }

    typename vector<E>::iterator middle = list.begin() + (list.size() / 2);

    vector<E> left(list.begin(), middle);
    vector<E> right(middle, list.end());

    left = mergeSort(left);
    right = mergeSort(right);

    return merge<E>(list, left, right);
}

template <typename E>
void shiftRight(vector<E>& list, int low, int high)
{
    int root = low;
    while ((root*2)+1 <= high)
    {
        int leftChild = (root * 2) + 1;
        int rightChild = leftChild + 1;
        int swapIndex = root;
        if (list[swapIndex] < list[leftChild])
        {
            swapIndex = leftChild;
        }
        if ((rightChild <= high) && (list[swapIndex] < list[rightChild]))
        {
            swapIndex = rightChild;
        }
        if (swapIndex != root)
        {
            double tmp = list[root];
            list[root] = list[swapIndex];
            list[swapIndex] = tmp;
            root = swapIndex;
        }
        else
        {
            break;
        }
    }
    return;
}

template <typename E>
void heapify(vector<E>& list, int low, int high)
{
    int midIndex = (high - low - 1)/2;
    while (midIndex >= 0)
    {
        shiftRight(list, midIndex, high);
        midIndex--;
    }
    return;
}

template <typename E>
void heapSort(vector<E>& list, int size)
{
    heapify(list, 0, size - 1);
    int high = size - 1;
    while (high > 0)
    {
        double tmp = list[high];
        list[high] = list[0];
        list[0] = tmp;
        high--;
        shiftRight(list, 0, high);
    }
    return;
}

template <typename E>
int pivot(vector<E>& list, int first, int last) 
{
    int p = first;
    E pivotElement = list[first];

    for(int i = first+1 ; i <= last ; i++)
    {
        if(list[i] <= pivotElement)
        {
            p++;
            E temp = list[i];
            list[i] = list[p];
            list[p] = temp;
        }
    }

    E temp = list[p];
    list[p] = list[first];
    list[first] = temp;

    return p;
}

template <typename E>
void quickSort(vector<E>& list, int first, int last) 
{
    E pivotElement;

    if(first < last)
    {
        pivotElement = pivot(list, first, last);
        quickSort(list, first, pivotElement-1);
        quickSort(list, pivotElement+1, last);
    }
}
template <typename E>
bool sort()
{
    vector<E> list;
    int again = 0;

    cout << "How many items do you want to sort? (0 to quit)\n";
    cin >> listSize;
    if (listSize == 0)
        exit(0);
    else if (listSize < 0) {
        cout << "Invalid input.\n";
        exit(0);
    }

    int sort = 0;
    cout << "Which sorting algorithm would you like to use?\n";
    cout << " 1 for Insertion Sort\n 2 for Merge Sort\n 3 for Heapsort\n 4 for Quicksort\n";
    cin >> sort;
    cout << "\n";

    printVector(list, listType);    
    cout << "\n\n";

    if (sort == 1)
        insertionSort(list);
    else if (sort == 2)
        mergeSort(list);
    else if (sort == 3)
        heapSort(list, listSize);
    else if (sort == 4)
        quickSort(list, 0, listSize - 1);
    else {
        cout << "Invalid command\n";
        exit(0);
    }

    printVector(list, listType);
    cout << "\n\n";

    while (again == 0) {
        cout << "Would you like to go again? (1 for yes, 2 for no)\n";
        cin >> again;
        if (again == 1)
            return true;
        else if (again == 2)
            return false;
    }
}

SortingAlgorithms.h

#ifndef SORTING_ALGORITHMS_H_
#define SORTING_ALGORITHMS_H_

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

using namespace std;

static const char alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "abcdefghijklmnopqrstuvwxyz";

int checkType(string listType);

template <typename E>
vector<E> generateList(string listType);

template <typename E>
void printVector(vector<E>& list, string listType);

template <typename E>
void insertionSort(vector<E>& list);

template <typename E>
vector<E> merge(vector<E>& list, vector<E>& left, vector<E>& right);

template <typename E>
vector<E> mergeSort(vector<E>& list);

template <typename E>
void shiftRight(vector<E>& list, int low, int high);

template <typename E>
void heapify(vector<E>& list, int low, int high);

template <typename E>
void heapSort(vector<E>& list, int size);

template <typename E>
int pivot(vector<E>& list, int first, int last) ;

template <typename E>
void quickSort(vector<E>& list, int first, int last);

template <typename E>
bool sort();

#endif

main.cpp

#include "SortingAlgorithms.h"
#include <cstdlib>
#include <iostream>
#include <vector>
#include <time.h>
#include <string>

using namespace std;

int listSize;
string listType = "int";

int main(int argc, char** argv) {
    srand(time(0));
    vector<int> list = generateList<int>(listType);

    printVector(list, listType);
    cout << "\n\n";
    insertionSort(list);

    printVector(list, listType);
}

Answer 1

Templates can only be implemented in the header file. For the reason why, see here Why can templates only be implemented in the header file?