C++ 中带有 <class Comparable> 的模板

Question

我正在尝试比较算法。我不熟悉 C++。我想创建一个主程序，我将在其中包含下面的代码作为 header。我不完全明白 "template class Comparable" 是什么。

#include <vector>
using namespace std;

template <class Comparable> 
void SelectionSort(vector<Comparable> & nums, int low, int high)
{
    for (int i = low; i <= high-1; i++) {
        int indexOfMin = i;                     // traverse the list to
        for (int j = i+1; j <= high; j++) {     // find the index of the
            if (nums[j] < nums[indexOfMin]) {   // next smallest item
                indexOfMin = j;
            }
        }

        Comparable temp = nums[i];              // swap the next smallest
        nums[i] = nums[indexOfMin];             // item into its correct
        nums[indexOfMin] = temp;                // position
    }
}

template <class Comparable> void SelectionSort(vector<Comparable> & nums) 
{
    SelectionSort(nums, 0, nums.size()-1);
}

Answer 1

你的主要排序函数看起来像这样（暂时删除 "template" 部分）：

void SelectionSort(vector<Comparable> & nums) 
{
    SelectionSort(nums, 0, nums.size()-1);
}

看起来像是作用于 Comparables 向量的普通排序函数。但什么是 Comparable？想象一下，如果 "Comparable" 只不过是 "int" 的别名（不是，但想象一下）。然后你会得到这个：

void SelectionSort(vector<int> & nums) 
{
    SelectionSort(nums, 0, nums.size()-1);
}

这是普通的C++代码。它声明并定义了一个对整数向量进行排序的函数。非常简单。

Comparable 没有这样的标准含义。这是您问题中的代码发明的术语。它由文本 template <class Comparable> 声明，与声明变量的方式大致相同。它有点像 "type variable"。普通变量表示许多值中的一个；类型变量代表许多类型中的一种。

template <class Comparable> void SelectionSort(vector<Comparable> & nums) 
{
    SelectionSort(nums, 0, nums.size()-1);
}

此代码声明 Comparable 不会自动为 int、float 或 std::string，而是可以是任何类型。要使用此函数，您必须在调用该函数时指定所需的类型。你可以明确地做到这一点：

std::vector<int> someints;
SelectionSort<int>(someints);

（这将使 "Comparable" 意味着 "int" 毕竟，在那个调用中。）

或者您可以省略那个额外的规范并希望编译器能够解决：

std::vector<int> someints;
SelectionSort(someints);

并且您可以根据需要为不同的类型使用相同的模板；就一次使用而言，它在任何意义上都不是 "spent"：

std::vector<int> someints, moreints;
std::vector<float> somefloats;
SelectionSort(someints);
SelectionSort(somefloats);
SelectionSort(moreints);

为了像这样一个简单的目的，您可以想象 SelectionSort 是一个适用于多种类型的函数，而不仅仅是一种。但实际上它不是一个函数。它是一整套潜在函数，其中一些可能由编译器实例化。上面的代码调用了 SelectionSort 三次，但只有两个 Comparable 类型，因此它在幕后创建了两个实际函数。

我一直在谈论 Comparable 作为一个变量，但它不能在模板实例中变化。你不能在 SelectionSort<int> 之内做 Comparable=float 之类的事情。它因模板的一个实例而异，而不是在一个实例内。当模板被实例化为一个真正的函数时，Comparable 被替换为为其指定的类型，然后被遗忘；该函数不 "know" 它是模板的一个实例。它只是一个名称中恰好有尖括号的函数。我觉得。

确实有一些非常强大、复杂、mind-bending 的事情可以用模板来完成。但是您可能不需要为您的目的了解太多。

不过，还有一个更重要的基本点是还有模板类。 std::vector本身就是其中之一。它们的工作方式与 SelectionSort 等模板函数大致相似：header <vector> 只为所有类型声明一次向量模板，但是你可以说 std::vector<int> 然后再说 std::vector<SomeClassIMade> 等等，从而自动实例化两个（或更多）实际类。所有这些类将像 C++ 向量一样工作，但每个都只知道如何处理自己指定的元素类型，而不会理解任何其他元素。

C++ 中带有 <class Comparable> 的模板

Templates with <class Comparable> in C++

c++

algorithm

class

selection-sort