C++ 未定义对(函数)的引用

Question

我正在使用单个头文件为一堆排序算法声明一堆子例程。当我尝试从我的 main.cpp 文件调用它们时，出现错误。我很困惑为什么，因为我已经在头文件中正确声明了我的函数，并且我已经在相应的 .cpp 文件中定义了它们。我已将头文件包含在我的两个 .cpp 文件中。这是我的代码:

排序算法.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;
    }
}

排序算法.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

模板只能在头文件中实现。至于为什么，看这里Why can templates only be implemented in the header file?