如何用CppUnit测试基于模板的array<int,N>归并排序函数？

问题根源 #

C++模板采用编译期实例化机制：模板函数的实现代码必须在调用它的编译单元（.cpp文件）中可见，编译器才能生成对应类型/大小的模板实例。

你将模板函数的实现放在了mergeSortByMyself.cpp中，测试代码testing.cpp仅包含头文件的声明。编译测试代码时，编译器无法生成size_t=12（测试中用到的数组大小）对应的模板实例，导致链接阶段找不到函数定义。

而单独运行main时能正常工作，是因为main所在的编译单元在编译时能看到模板实现，自动实例化了需要的版本。

解决方案 #

有两种常用修复方式：

方法1：将模板实现移到头文件中 #

直接把mergeSortByMyself.cpp里的所有模板函数实现，迁移到mergeSortModel.h（注意统一文件名：你的头文件代码写的是mergeModel.h，但实现/测试文件引用的是mergeSortModel.h，需保持一致）中，和声明放在一起。

修改后的mergeSortModel.h示例：

#pragma once
#include <bits/stdc++.h>
using namespace std;

template<typename Iterator>
void print(Iterator list){
    for(auto item: list ){
        cout << item << " ";
    }
    cout << endl;
}

template<size_t M, size_t P>
array<int,M+P> merge(array<int,M>& arr1, array<int,P>& arr2){
    cout << "Merge starts here......."<<endl;
    int i = 0, j = 0, k = 0;
    array<int,arr1.size()+arr2.size()> joined;
    cout << "a1: " << arr1.size() << " a2: "<< arr2.size() << " a3: "<<joined.size()<< endl;
    for(k = 0; k < joined.size(); k++){
        if(i < arr1.size() && j < arr2.size() && arr1[i] < arr2[j]){
            joined[k] = arr1[i];
            i++;
        }else if( i < arr1.size() && j < arr2.size() &&  arr1[i] > arr2[j]){
            joined[k] = arr2[j];
            j++;
        }else{
            break;
        }
    }
    
    if(i == arr1.size()){
        for(; k < joined.size();k++  ){
            joined[k] = arr2[j];
            j++;
        }
    }
    if(j == arr2.size()){
        for(; k < joined.size(); k++){
            joined[k] = arr1[i];
            i++;
        }
    }
    cout << "joined ";
    print(joined);  
    return joined;
}

template<size_t N>
array<int,N> mergeSortByMyself(array<int,N>& list){
    if(list.size() <= 1){
        return list;
    }
    const int firstPart = (const int)list.size()/2;
    array<int, firstPart> leftArr;
    int i;
    for(i=0; i < firstPart; i++){
        leftArr[i] = list[i];
    }
    array<int,list.size() - firstPart> rightArr;
    for(i=firstPart; i < list.size(); i++){
        rightArr[i-firstPart] = list[i];
    }
    print(list);
    print(leftArr);
    print(rightArr);

    leftArr = mergeSortByMyself(leftArr);
    rightArr = mergeSortByMyself(rightArr);

    array<int,list.size()> joined;
    if(leftArr[leftArr.size() -1] > rightArr[0]){
        joined = merge(leftArr,rightArr);
    }else{
        int y = 0;
        for(int g = 0; g < joined.size(); g++){
            if(y < leftArr.size()){
                joined[g] = leftArr[y];
            }else{
                joined[g] = rightArr[y-leftArr.size()];
            }
            y++;
        }
    }
    return joined;
}

之后删除mergeSortByMyself.cpp，保持原编译命令即可：

g++ testing.cpp -lcppunit -o test

方法2：显式实例化模板 #

若不想移动实现代码，可在mergeSortByMyself.cpp末尾显式实例化测试需要的所有模板版本：

// 在mergeSortByMyself.cpp最后添加
template array<int,12> mergeSortByMyself(array<int,12>&);
template array<int,6> mergeSortByMyself(array<int,6>&);
template array<int,3> mergeSortByMyself(array<int,3>&);
template array<int,1> mergeSortByMyself(array<int,1>&);
template array<int,6+6> merge(array<int,6>&, array<int,6>&);
template array<int,3+3> merge(array<int,3>&, array<int,3>&);
template void print(array<int,12>&);
template void print(array<int,6>&);
// 其他用到的模板实例都需要显式声明

这种方法灵活性差，每次测试不同大小的数组都需手动添加对应实例。

额外修复点 #

测试代码中的断言逻辑错误：当前断言是将排序后的数组和原始未排序数组比较，应改为和你的归并排序结果比较：

// 原错误代码
CPPUNIT_ASSERT(toStr(tosort)==toStr(tosort_test));
// 修改为
CPPUNIT_ASSERT(toStr(tosort)==toStr(sorted));

内容的提问来源于stack exchange，提问作者matt