多态和泛型编程

在C++标准库中，存在两个截然不同但同等重要的使命。其一是提供某些具体数据类型或函数的坚固实现，这些类型和函数在许多不同的程序中都有用，但并未内置于核心语言语法中。这就是为什么标准库包含std::string、std::regex、std::filesystem::exists等。另一个使命是提供广泛使用的抽象算法（如排序、搜索、反转、整理等）的坚固实现。
本章将探讨以下主题：

• 具体（单态）函数，其行为不可参数化
• 通过基类、虚成员函数和继承实现的经典多态性
• 通过概念、要求和模型实现的泛型编程
• 每种方法的实际优点和缺点

具体单态函数

抽象算法与具体函数有何区别？最好通过示例来展示。我们来编写一个函数，将数组中的每个元素乘以2：

    class array_of_ints {
      int data[10] = {};
      public:
        int size() const { return 10; }
        int& at(int i) { return data[i]; }
    };

    void double_each_element(array_of_ints& arr)
    {
      for (int i=0; i < arr.size(); ++i) {
        arr.at(i) *= 2;
      }
    }

我们的函数 double_each_element 仅 适用于 array_of_int 类型的对象；传入不同类型的对象将不起作用（甚至无法编译）。我们称这类 double_each_element 的函数为 具体 或 单态 函数。我们称它们为 具体 ，因为对于我们的目的来说，它们不够 抽象。想象一下，如果C++标准库提供了一个仅适用于一种特定数据类型的具体排序例程，那将是多么痛苦！

经典多态函数

我们可以通过经典的面向对象（OO）编程技术提高算法的抽象层次，正如在Java和C#等语言中看到的那样。OO方法是确切决定我们希望哪些行为可自定义，然后将它们声明为 抽象基类 的公共虚成员函数：

    class container_of_ints {
      public:
      virtual int size() const = 0;
      virtual int& at(int) = 0;
    };

    class array_of_ints : public container_of_ints {
      int data[10] = {};
      public:
        int size() const override { return 10; }
        int& at(int i) override { return data[i]; }
    };

    class list_of_ints : public container_of_ints {
      struct node {
        int data;
        node *next;
      };
      node *head_ = nullptr;
      int size_ = 0;
      public:
       int size() const override { return size_; }
       int& at(int i) override {
        if (i >= size_) throw std::out_of_range("at");
        node *p = head_;
        for (int j=0; j < i; ++j) {
          p = p->next;
        }
        return p->data;
      }
      ~list_of_ints();
    };

    void double_each_element(container_of_ints& arr) 
    {
      for (int i=0; i < arr.size(); ++i) {
        arr.at(i) *= 2;
      } 
    }

    void test()
    {
      array_of_ints arr;
      double_each_element(arr);

      list_of_ints lst;
      double_each_element(lst);
    }

在测试中，对 double_each_element 的两种不同调用之所以能编译，是因为在经典的面向对象（OO）术语中，array_of_ints 是一个 container_of_ints（即它继承自 container_of_ints 并实现了相关的虚成员函数），而 list_of_ints 也 是一个 container_of_ints。然而，任何给定 container_of_ints 对象的行为都是由其动态类型决定的；也就是说，由与这个特定对象关联的函数指针表决定的。

由于我们现在可以在不直接编辑源代码的情况下参数化 double_each_element 函数的行为——只需传入不同动态类型的对象——我们说这个函数变得多态化了。

但是，这个多态函数仅能处理那些继承自基类 container_of_ints 的类型。例如，你不能将 std::vector<int> 传递给这个函数；如果你尝试，将会得到一个编译错误。经典多态性有用，但它并不能完全实现完全的泛型化。

经典（面向对象）多态的一个优点是，源代码仍与编译器生成的机器代码有一对一的对应关系。在机器代码层面，我们仍然只有一个 double_each_element 函数，带有一个签名和一个明确定义的入口点。例如，我们可以把 double_each_element 的地址当作函数指针。

使用模板的泛型编程

在现代C++中，编写完全泛型算法的典型方法是将算法实现为模板。我们仍然会根据公共成员函数 .size() 和 .at() 来实现函数模板，但我们不再要求参数 arr 是任何特定类型。因为我们的新函数将是一个模板，我们将告诉编译器：“我不在乎 arr 是什么类型。无论它是什么类型，只需生成一个全新的函数（即模板实例化），并将该类型作为其参数类型。”

    template<class ContainerModel>
    void double_each_element(ContainerModel& arr)
    {
      for (int i=0; i < arr.size(); ++i) {
        arr.at(i) *= 2;
      }
    }

    void test()
    {
      array_of_ints arr;
      double_each_element(arr);

      list_of_ints lst;
      double_each_element(lst);

      std::vector<int> vec = {1, 2, 3};
      double_each_element(vec);
    }

在大多数情况下，如果我们能准确地用文字描述出模板类型参数 ContainerModel 必须支持的操作集，将有助于我们设计更好的程序。这组操作，合在一起，在C++中被称为一个概念；在这个例子中，我们可能会说，Container 概念包括“有一个名为 size 的成员函数，它返回容器的大小作为一个 int（或类似于 int 的东西）；以及有一个名为 at 的成员函数，它接受一个 int 索引（或从 int 隐式转换的东西），并产生对容器中 索引 位置元素的非常量引用。”每当某个类 array_of_ints 正确提供了概念 Container 所需的操作，以致于 array_of_ints 可以与 double_each_element 一起使用时，我们说具体类 array_of_ints 是 Container 概念的一个模型。这就是为什么我在前面的示例中将模板类型参数命名为 ContainerModel 的原因。

更传统的做法是将模板类型参数本身命名为 Container，以后我也会这样做；我只是不想一开始就搞混 Container 概念与这个特定函数模板的特定模板类型参数之间的区别，后者恰好希望其参数是一个模拟 Container 概念的具体类。

当我们使用模板实现一个抽象算法，以便算法的行为可以在编译时由模拟适当概念的任何类型参数化时，我们说我们正在进行泛型编程。

请注意，我们对 Container 概念的描述并没有提到我们期望包含元素的类型是 int；并非巧合，我们发现我们现在甚至可以在不包含 int 的容器上使用我们的泛型 double_each_element 函数！

    std::vector<double> vecd = {1.0, 2.0, 3.0};
    double_each_element(vecd);

这种额外的泛型性是使用 C++ 模板进行泛型编程的一大好处，与经典多态相比。经典多态在稳定的接口签名后面隐藏了不同类的不同行为（例如，.at(i) 总是返回 int&），但一旦你开始处理变化的签名，经典多态就不再适合这项工作了。

泛型编程的另一个优点是它通过增加内联的机会提供了极高的速度。在经典多态的示例中，必须反复查询 container_of_int 对象的虚拟表以找到其特定虚拟 at 方法的地址，并且通常无法在编译时看穿虚拟分派。模板函数 double_each_element<array_of_int> 可以编译成对 array_of_int::at 的直接调用，甚至可以完全内联调用。

由于泛型编程使用模板可以轻松处理复杂的要求，并在处理类型时非常灵活——即使是像 int 这样的原始类型，经典多态也会失败——标准库使用模板来实现所有其算法和这些算法操作的容器。因此，标准库中的算法和容器部分通常被称为标准模板库或STL。

没错——严格来说，STL 只是 C++ 标准库的一小部分！然而，在本书中，就像在现实生活中一样，我们可能偶尔会用 STL 这个术语来指代标准库，反之亦然。

让我们在深入研究 STL 提供的标准泛型算法之前，再看几个手写的泛型算法。这里是一个计数函数模板，返回容器中元素的总数：

    template<class Container>
    int count(const Container& container)
    {
      int sum = 0;
      for (auto&& elt : container) {
        sum += 1;
      }
      return sum;
    }

这里是 count_if，它返回满足用户提供的谓词函数的元素数量：

    template<class Container, class Predicate>
    int count_if(const Container& container, Predicate pred) 
    { 
      int sum = 0;
      for (auto&& elt : container) {
        if (pred(elt)) {
            sum += 1;
        }
      }
      return sum;
    }

这些函数将像这样使用：

    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

    assert(count(v) == 8);

    int number_above =
      count_if(v, [](int e) { return e > 5; });
    int number_below =
      count_if(v, [](int e) { return e < 5; });

    assert(number_above == 2);
    assert(number_below == 5);

那个小小的表达式 pred(elt) 蕴含了极大的力量！我鼓励你尝试用经典多态重新实现 count_if 函数，只是为了感受整个过程在哪里崩溃。在现代 C++ 的语法糖下隐藏着许多变化的签名。例如，我们的 count_if 函数中的范围 for 循环语法被编译器转换（或“降低”）为以 container.begin() 和 container.end() 为基础的 for 循环，每个都需要返回一个迭代器，其类型取决于容器本身的类型。另一个例子，在泛型编程版本中，我们从不指定——我们也不需要指定——pred 是否通过值或引用接受其参数 elt。试试用虚拟的 bool operator() 来做那个！