12 | 编译期多态：泛型编程和模板入门

你好，我是吴咏炜。

相信你对多态这个面向对象的特性应该是很熟悉了。我们今天来讲一个非常 C++ 的话题，编译期多态及其相关的 C++ 概念。

面向对象和多态

在面向对象的开发里，最基本的一个特性就是“多态” [1]——用相同的代码得到不同结果。以我们在[第 1 讲] 提到过的 shape 类为例，它可能会定义一些通用的功能，然后在子类里进行实现或覆盖：

class shape {
public:
  …
  virtual void draw(const position&) = 0;
};

上面的类定义意味着所有的子类必须实现 draw 函数，所以可以认为 shape 是定义了一个接口（按 Java 的概念）。在面向对象的设计里，接口抽象了一些基本的行为，实现类里则去具体实现这些功能。当我们有着接口类的指针或引用时，我们实际可以唤起具体的实现类里的逻辑。比如，在一个绘图程序里，我们可以在用户选择一种形状时，把形状赋给一个 shape 的（智能）指针，在用户点击绘图区域时，执行 draw 操作。根据指针指向的形状不同，实际绘制出的可能是圆，可能是三角形，也可能是其他形状。

但这种面向对象的方式，并不是唯一一种实现多态的方式。在很多动态类型语言里，有所谓的“鸭子”类型 [2]：

如果一只鸟走起来像鸭子、游起泳来像鸭子、叫起来也像鸭子，那么这只鸟就可以被当作鸭子。

在这样的语言里，你可以不需要继承来实现 circle、triangle 等类，然后可以直接在这个类型的变量上调用 draw 方法。如果这个类型的对象没有 draw 方法，你就会在执行到 draw() 语句的时候得到一个错误（或异常）。

鸭子类型使得开发者可以不使用继承体系来灵活地实现一些“约定”，尤其是使得混合不同来源、使用不同对象继承体系的代码成为可能。唯一的要求只是，这些不同的对象有“共通”的成员函数。这些成员函数应当有相同的名字和相同结构的参数（并不要求参数类型相同）。

听起来很抽象？我们来看一下 C++ 中的具体例子。

容器类的共性

容器类是有很多共性的。其中，一个最最普遍的共性就是，容器类都有 begin 和 end 成员函数——这使得通用地遍历一个容器成为可能。容器类不必继承一个共同的 Container 基类，而我们仍然可以写出通用的遍历容器的代码，如使用基于范围的循环。

大部分容器是有 size 成员函数的，在“泛型”编程中，我们同样可以取得一个容器的大小，而不要求容器继承一个叫 SizeableContainer 的基类。

很多容器具有 push_back 成员函数，可以在尾部插入数据。同样，我们不需要一个叫 BackPushableContainer 的基类。在这个例子里，push_back 函数的参数显然是都不一样的，但明显，所有的 push_back 函数都只接收一个参数。

我们可以清晰看到的是，虽然 C++ 的标准容器没有对象继承关系，但彼此之间有着很多的同构性。这些同构性很难用继承体系来表达，也完全不必要用继承来表达。C++ 的模板，已经足够表达这些鸭子类型。

当然，作为一种静态类型语言，C++ 是不会在运行时才报告“没找到 draw 方法”这类问题的。这类错误可以在编译时直接捕获，更精确地来说，是在模板实例化的过程中。

下面我们通过几个例子，来完整地看一下模板的定义、实例化和特化。

C++ 模板

定义模板

学过算法的同学应该都知道求最大公约数的辗转相除法，代码大致如下：

int my_gcd(int a, int b)
{
  while (b != 0) {
    int r = a % b;
    a = b;
    b = r;
  }
  return a;
}

这里只有一个小小的问题，C++ 的整数类型可不止 int 一种啊。为了让这个算法对像长整型这样的类型也生效，我们需要把它定义成一个模板：

template <typename E>
E my_gcd(E a, E b)
{
  while (b != E(0)) {
    E r = a % b;
    a = b;
    b = r;
  }
  return a;
}

这个代码里，基本上就是把 int 替换成了模板参数 E，并在函数的开头添加了模板的声明。我们对于“整数”这只鸭子的要求实际上是：

可以通过常量 0 来构造
可以拷贝（构造和赋值）
可以作不等于的比较
可以进行取余数的操作

对于标准的 int、long、long long 等类型及其对应的无符号类型，以上代码都能正常工作，并能得到正确的结果。

至于类模板的例子，我们可以直接参考[第 2 讲] 中的智能指针，这儿就不再重复了。

实例化模板

不管是类模板还是函数模板，编译器在看到其定义时只能做最基本的语法检查，真正的类型检查要在实例化（instantiation）的时候才能做。一般而言，这也是编译器会报错的时候。

对于我们上面 my_gcd 的情况，如果提供的是一般的整数类型，那是不会有问题的。但如果我们提供一些其他类型的时候，就有可能出问题了。以 CLN，一个高精度数字库为例（注：我并不是推荐大家使用这个库），如果我们使用它的 cl_I 高精度整数类型来调用 my_gcd 的话，出错信息大致如下：

其原因是，虽然它的整数类 cl_I 设计得很像普通的整数，但这个类的对象不支持 % 运算符。出错的第 20 行是我们调用 my_gcd 的位置，而第 9 行是函数模板定义中执行取余数操作的位置。

实例化失败的话，编译当然就出错退出了。如果成功的话，模板的实例就产生了。在整个的编译过程中，可能产生多个这样的（相同）实例，但最后链接时，会只剩下一个实例。这也是为什么 C++ 会有一个单一定义的规则：如果不同的编译单元看到不同的定义的话，那链接时使用哪个定义是不确定的，结果就可能会让人吃惊。

模板还可以显式实例化和外部实例化。如果我们在调用 my_gcd 之前进行显式实例化——即，使用 template 关键字并给出完整的类型来声明函数：

template cln::cl_I
  my_gcd(cln::cl_I, cln::cl_I);

那出错信息中的第二行就会显示要求实例化的位置。如果在显式实例化的形式之前加上 extern 的话，编译器就会认为这个模板已经在其他某个地方实例化，从而不再产生其定义（但代码用到的内联函数仍可能会导致实例化的发生，这个会随编译器和优化选项不同而变化）。在我们这个例子里，就意味着不会产生上面的编译错误信息了。当然，我们仍然会在链接时得到错误，因为我们并没有真正实例化这个模板。

类似的，当我们在使用 vector<int> 这样的表达式时，我们就在隐式地实例化 vector<int>。我们同样也可以选择用 template class vector<int>; 来显式实例化，或使用 extern template class vector<int>; 来告诉编译器不需要实例化。显式实例化和外部实例化通常在大型项目中可以用来集中模板的实例化，从而加速编译过程——不需要在每个用到模板的地方都进行实例化了——但这种方式有额外的管理开销，如果实例化了不必要实例化的模板的话，反而会导致可执行文件变大。因而，显式实例化和外部实例化应当谨慎使用。

特化模板

如果遇到像前面 CLN 那样的情况，我们需要使用的模板参数类型，不能完全满足模板的要求，应该怎么办？

我们实际上有好几个选择：

添加代码，让那个类型支持所需要的操作（对成员函数无效）。
对于函数模板，可以直接针对那个类型进行重载。
对于类模板和函数模板，可以针对那个类型进行特化。

对于 cln::cl_I 不支持 % 运算符这种情况，恰好上面的三种方法我们都可以用。

一、添加 operator% 的实现：

cln::cl_I
operator%(const cln::cl_I& lhs,
          const cln::cl_I& rhs)
{
  return mod(lhs, rhs);
}

在这个例子，这可能是最简单的解决方案了。但在很多情况下，尤其是对对象的成员函数有要求的情况下，这个方法不可行。

二、针对 cl_I 进行重载：

为通用起见，我不直接使用 cl_I 的 mod 函数，而用 my_mod 把 my_gcd 改造如下：

template <typename E>
E my_gcd(E a, E b)
{
  while (b != E(0)) {
    E r = my_mod(a, b);
    a = b;
    b = r;
  }
  return a;
}

然后，一般情况的 my_mod 显然就是：

template <typename E>
E my_mod(const E& lhs,
         const E& rhs)
{
  return lhs % rhs;
}

最后，针对 cl_I 类，我们可以重载（overload）：

cln::cl_I
my_mod(const cln::cl_I& lhs,
       const cln::cl_I& rhs)
{
  return mod(lhs, rhs);
}

三、针对 cl_I 进行特化：

同二类似，但我们提供的不是一个重载，而是特化（specialization）：

template <>
cln::cl_I my_mod<cln::cl_I>(
  const cln::cl_I& lhs,
  const cln::cl_I& rhs)
{
  return mod(lhs, rhs);
}

这个例子比较简单，特化和重载在行为上没有本质的区别。就一般而言，特化是一种更通用的技巧，最主要的原因是特化可以用在类模板和函数模板上，而重载只能用于函数。

不过，我只是展示了一种可能性而已。通用而言，Herb Sutter 给出了明确的建议：对函数使用重载，对类模板进行特化 [3]。

展示特化的更好的例子是 C++11 之前的静态断言。使用特化技巧可以大致实现 static_assert 的功能：

template <bool>
struct compile_time_error;
template <>
struct compile_time_error<true> {};

#define STATIC_ASSERT(Expr, Msg)   \
  {                                \
    compile_time_error<bool(Expr)> \
      ERROR_##_Msg;                \
    (void)ERROR_##_Msg;            \
  }

上面首先声明了一个 struct 模板，然后仅对 true 的情况进行了特化，产生了一个 struct 的定义。这样。如果遇到 compile_time_error<false> 的情况——也就是下面静态断言里的 Expr 不为真的情况——编译就会失败报错，因为 compile_time_error<false> 从来就没有被定义过。

“动态”多态和“静态”多态的对比

我前面描述了面向对象的“动态”多态，也描述了 C++ 里基于泛型编程的“静态”多态。需要看到的是，两者解决的实际上是不太一样的问题。“动态”多态解决的是运行时的行为变化——就如我前面提到的，选择了一个形状之后，再选择在某个地方绘制这个形状——这个是无法在编译时确定的。“静态”多态或者“泛型”——解决的是很不同的问题，让适用于不同类型的“同构”算法可以用同一套代码来实现，实际上强调的是对代码的复用。C++ 里提供了很多标准算法，都一样只作出了基本的约定，然后对任何满足约定的类型都可以工作。以排序为例，C++ 里的标准 sort 算法（以两参数的重载为例）只要求：

参数满足随机访问迭代器的要求。
迭代器指向的对象之间可以使用 < 来比较大小，满足严格弱序关系。
迭代器指向的对象可以被移动。

它的性能超出 C 的 qsort，因为编译器可以内联（inline）对象的比较操作；而在 C 里面比较只能通过一个额外的函数调用来实现。此外，C 的 qsort 函数要求数组指向的内容是可按比特复制的，C++ 的 sort 则要求迭代器指向的内容是可移动的，可适用于更广的情况。

C++ 里目前有大量这样的泛型算法。随便列举几个：

sort：排序
reverse：反转
count：计数
find：查找
max：最大值
min：最小值
minmax：最小值和最大值
next_permutation：下一个排列
gcd：最大公约数
lcm：最小公倍数
等等

内容小结

本讲我们对模板、泛型编程和静态多态做了最基本的描述，并和动态多态做了一定的比较。如果你不熟悉模板和泛型编程的话，应该在本讲之后已经对其有了初步的了解，我们可以在下面几讲中进行更深入的讨论。

课后思考

请你在课后读一下参考资料，了解一下各种不同的多态，然后想一想：

C++ 支持几种不同形式的多态？
为什么并非所有的语言都支持这些不同的多态方式？

欢迎你留言与我分享你的看法。

参考资料

[1] Wikipedia, “Polymorphism”. https://en.wikipedia.org/wiki/Polymorphism_(computer_science)

[1a] 维基百科, “多态”. https://zh.wikipedia.org/zh-cn/多型_(计算机科学)

[2] Wikipedia, “Duck typing”. https://en.wikipedia.org/wiki/Duck_typing

[2a] 维基百科, “鸭子类型”. https://zh.wikipedia.org/zh-cn/鸭子类型

[3] Herb Sutter, “Why not specialize function templates?”. http://www.gotw.ca/publications/mill17.htm

精选留言

Geek_077da0

2019-12-23 10:26:57

老师您好，看到这一讲想问一个一直想问的问题。我是一个在校学生，目前学完了c++的基本语法知识并且看了一些相关的书籍，但平时能自己动手写代码的机会只有刷leetcode的时候，想请问一下老师，在去公司实习之前，有没有什么项目适合初学者练练手的。不然感觉自己看了这么多理论终究只是在纸上谈兵。

作者回复

可以尝试把平时用 Python、Bash 写的小工具改成用 C++。使用现代 C++，这种处理也不会太麻烦。

还有就是小的网络应用、数据处理应用等等。Leetcode 是考算法的，对语言技巧是没啥帮助。

2019-12-23 20:39:25
Jason

2020-01-14 16:30:58

老师，在参考资料3中，针对模板重载解析的例子
//
template <class T> // //（a）与
void f（T）之前相同的旧基础模板；

template <> // //（c）显式专业化，这一次（a）
void f <>（int *）;

template <class T> // //（b）第二个基本模板，重载（a）
void f（T *）;

// ...

int * p;
f（p）;

是否针对int*的全特化在(a)的后面，就是属于(a)的基础模板的全特化，在(b)后面就是(b)的全特化。所以int*全特化放置的位置不同，导致了模板裁决时，因为选取了不同的基础模板而导致了不同的结果。是这样吗？

作者回复

是的，这是个大坑，所以Herb建议对函数用重载就行了，不会有惊讶的行为。

2020-01-14 19:32:15
panda

2020-01-05 14:22:09

第一题通过查阅资料，c++的多态性分专用多态和通用多态，专用多态又分重载多态和强制多态，通用多态又分包含多态和参数多态。
重载多态：函数重载和操作符重载。
强制多态：使一个变量类型加以变化让其符合函数操作的要求。
如：double a = 1.0;
int b = 2;
double c = a + b;
此时b会强制转换成double再进行+操作。
包含多态：虚函数重构。
参数多态：课程里的函数模板。
第二题，对各语言了解太浅，需老师给出解答。

作者回复

思考题有些是没有固定答案的，就是希望大家去思考一下。多态的分类也有很多种。包含多态、参数多态和重载多态都是常见的提法，但强制多态这个说法我不熟，查了一下才确定有这种说法，感觉和一般的多态这个词的理解还是有点差异的……

就这第二题而言，也是希望大家去比较学习过的其他语言。这基本上取决于语言本身在类型方面的特性。

以 Python 为例，它是动态类型的语言。所以它不会有真正的静态多态。但和静态类型的面向对象语言（如 Java）不同，它的运行期多态不需要继承。没有参数化多态初看是个缺陷，但由于 Python 的动态参数系统允许默认参数和可变参数，并没有什么参数化多态能做得到而 Python 做不到的事。

2020-01-05 19:58:39
geek

2021-03-06 22:05:10

老师，静态断言示例中：
template <bool>
struct compile_time_error;
此处模板参数是bool和是typename T这种有什么区别吗？
另外
compile_time_error<bool(Expr)> \
ERROR_##_Msg; \
这里我理解在条件为真时，是不是会定义一个名字为ERROR__MSG的对象？但用nm在.o文件中没看到。
最后
(void)ERROR_##_Msg;这句有啥作用啊？去掉之前和之后，似乎没啥区别。

作者回复

模板参数可以是值（写出类型名）或者类型（写typename）。这个例子里参数是个bool值。

临时变量不会产生一个全局的符号，在nm里都看不到的。

(void)这行的作用是抑制编译器的变量未使用告警。这是常见的显式告诉编译器不要对变量未使用进行告警的方式。

2021-03-08 18:55:02
Jason

2020-01-16 17:30:42

老师，在c++的多态中，有没有一种方式可以通过基类的指针获取实际子类的类型呢？比如我定义的两个protobuf的类型里都有user_id的字段，在代码中为了通用（不想每个类型写一个函数），反射出来传递给外围都是pb的基类指针，因为要设置子类的成员就必须要强制类型转换，但是这种情况下又拿不到子类的实际类型去做转换。decltype(基类)得到的还是基类类型

作者回复

decltype 得到的是编译期的类型。你需要的是运行期的类型，C++ 里挺有争议（跟异常类似）的功能——RTTI。（还是要强调一句，你应该考虑是否用虚函数可以达到你需要的功能。很多项目，如 Google 的，会禁用 RTTI。）

你可以用 dynamic_cast 来转换成你需要的指针类型，如果类型不对，会得到空指针。你也可以用 typeid 直接来获取对象的实际类型。下面的代码演示一下（需要 Boost；没有安装 Boost 请自行调整，也只是不能输出友好类名而已）：

#include <iostream>
#include <typeinfo>
#include <boost/core/demangle.hpp>

using namespace std;
using boost::core::demangle;

class shape {
public:
virtual ~shape() {}
};

class circle : public shape {
};

int main()
{
shape* ptr = new circle();
auto& type = typeid(*ptr);
cout << type.name() << endl;
cout << demangle(type.name()) << endl;
cout << boolalpha;
cout << (type == typeid(shape) ? "is shape\n" : "");
cout << (type == typeid(circle) ? "is circle\n" : "");
delete ptr;
}

在 GCC 下的输出：

6circle
circle
is circle

2020-01-16 22:49:14
陈舸

2020-02-11 13:58:41

看到编译期多态，我以为会讲一讲利用模板做static_cast<T*>(this)->implementation()的技巧。这种方法可以在编译期决定要实际调用的函数是哪一个，就可以不用虚函数了。64位平台下对于小型的类可以节省不少空间。

作者回复

这个可以用 SFINAE（第 14 讲）或 if constexpr（第 15 讲）做到。

2020-02-11 15:13:48
EncodedStar

2020-01-03 11:54:32

1.C++ 支持2种吧，静态多态和动态多态，静态多态它在编译器，通过函数重载，用算符重载的方式被调用者使用，动态多态也叫运行时多态，它可以通过虚函数和继承来实现，实现是，编译器会将进程运行过程中动态绑定
2.支持多态的语言一般是面向对象的语言，所以并非所有的都有。

作者回复

还不够全面。可以读读参考资料。

2020-01-03 19:13:56
总统老唐

2019-12-24 12:05:47

吴老师，学完这一课，有 3 点疑问：
1，你提到的方法一，“添加代码，让那个类型支持所需要的操作（对成员函数无效）”，这里说“对成员函数无效”是具体指的什么情况？
2，实现static_assert功能时，定义 struct 模板如下: template<bool> struct compile_time_error, 和常见的模板定义头部 template <typename T> 的格式看起来不一样，常见的这种格式中参数类型是未定的，但是compile_time_error这个模板，参数明确指定是 bool 型，这是模板的另一种形式么？
3，我尝试做了以下实验
template <typename T>
T addData(T a, T b)
{
return a + b;
}

double addData(double a, double b)
{
return (int)a + (int)b;
}

template <>
double addData(double a, double b)
{
return (int)a + (int)b;
}
当我调用 addData(1.5, 2.5)时，发现调用的是针对double的重载函数，而不是模板针对double 的特化，这是为什么？

作者回复

1. 一般而言，不应该去修改别人的类。容易出问题。所以不能添加成员函数。

2. 模板参数可以是类型，也可以是常数表达式，包括整数类型常数、枚举、指针、引用。

3. 重载比特化优先。一般而言，函数特化是不推荐的。具体看参考资料 3。

2019-12-24 18:11:09
转遍世界

2023-12-29 11:59:27

还有个问题: 三、针对 cl_I 进行特化：这里全局模板类特化里调用了mod，这个mod是cln::cl_I的成员函数吗？能类外直接调用？

作者回复

mod 是 cln 名空间里的独立函数。因为有 ADL，编译器能找到它，而不需要我们写 cln::mod。

2023-12-31 10:13:03
转遍世界

2023-12-29 11:53:25

老师我有个疑问:
二、针对 cl_I 进行重载：这里。
类的成员函数能重载全局模板函数吗，不在同一个作用域啊。

作者回复

对，可以的。全局函数对名空间里的对象进行重载，完全没有问题。当然，放在名空间里，用 ADL 来找到也是可以的。但修改“别人”的名空间通常不那么好。

2023-12-31 10:08:22
陈宣羽

2022-05-27 08:34:45

不是纯虚函数子类一定要实现吗，虚函数没这个要求吧

作者回复

不需要。我也没这么说过吧。

另外，纯虚函数只是防止你产生没有实现该函数的类的对象而已。子类不实现纯虚函数也没什么不可以——可以放孙子类里面去。

2022-05-27 13:26:34
水月

2022-03-14 16:44:56

Python是个弱类型的语言，而且也是动态“编译”，一些函数重载的行为好像都被包装进解释器了。继承多态倒是挺常见的，也经常override重写一些方法，或者比较懒的时候直接就给加一些长命令参数给调用脚本时区分用。Python的类有个有意思的内容是，里面除了最常用的实例方法之外，允许定义static_method和class_method，这些不进行实例化就能使用的类方法目前我还没从C++了解到，可能是其他的实现逻辑？

作者回复

我一般把 Python 当作强类型的动态类型语言。类型强弱不是非黑即白，而且 Python 的类型还是相当强的，基本没有容易误导的默认转换。

C++ 里也有静态成员函数，但没有直接对应于 classmethod 的东西。C++ 不是动态类型语言，类型不是运行时可以动态传递的对象。模板的参数可以模拟 classmethod，但绑定是在编译时而非运行时。

2022-03-19 12:55:41
HiganFish

2021-05-26 15:39:00

特设多态：根据参数不同实际表现不同（函数重载或运算符重载）
参数多态：参数多态允许函数或数据类型被一般性的书写（泛型）
子类型：（多态）
多态-变量多态：基类型的变量（对于C++是引用或指针）可以被赋值基类型对象，也可以被赋值派生类型的对象。
多态-函数多态：平时说的调用子类函数的多态
miyan

2020-11-01 18:37:34

老师我想问个问题:用模板编程的时候，传入的类型是不定的，这时我想调试，想输出这个类型的名字，比如我传进了 circle 类，想输出“circle”字符串，如果用typeid().name()得到的不是"circle"字符串，这种情况该怎么实现呢

作者回复

可以看第24讲。

2020-11-02 08:23:42
十斗簸箕

2020-07-30 11:11:47

老师好，最近遇到个问题，还请多多指教，代码如下
#include <type_traits>

class TemplateTest {
public:
template <typename T>
void Test(T &result) {
if (std::is_same<T, int>::value)
T = GetInt();
else if (std::is_same<T, double>::value)
T = GetDouble;
else if (std::is_same<T, std::string>::value)
T = GetString();
}

private:
int GetInt() {
return 123;
}

double GetDouble() {
return 123.456;
}

std::string GetString() {
return "string";
}
};

void main() {
TemplateTest tt;
int v1;
tt.Test(v1);

std::string v2;
tt.Test(v2);
}
目的是想用Test接口根据不同类型来调用内部实现函数，但在vs2015环境编译不过，不知何故？或者是我这种用法存在一些问题，如果有好的实现方式希望指正，谢谢~

作者回复

你的代码里有很多错误：

应该是 int main()
GetDouble 后面漏了 ()
漏包含 <string>
“T =”需要改成“result =”

按你的写法，用 C++17 的 if constexpr（if 不行，不同类型的赋值会出问题）可以编译过。

但是，你为什么用模板呢？似乎用重载直接就可以解决问题：

void Test(int& result)
{
result = GetInt();
}
void Test(double& result)
{
result = GetDouble();
}
void Test(std::string& result)
{
result = GetInt();
}

2020-07-31 00:18:00
万林

2020-06-02 09:37:42

老师你好，我看到单例的模块定义类似下面的代码，放在一个头文件中，其他类通过继承实现单例，实现代码重用。我有一点不太明白，这个静态变量定义在头文件中，会不会在编译期就有多份定义了呢？难道是在链接的时候只选择一份吗？还有老师提倡这种单例的实现方式吗？

template<class T>
class CSingleton
{
public:
static T* Instance()
{
if (!m_pInstance)
{
}
return m_pInstance;
};

private:
static T* m_pInstance;
};

//静态变量定义
template<class T> T* CSingleton<T>::m_pInstance = NULL;

作者回复

模板都是有特殊性的。函数如果不inline的话，正常情况下也不能放头文件里，否则就会有多个定义；但函数模板编译器同样会特殊处理。最后链接后只有一个实例化的结果存在。

不管是否inline，所有编译单元看到的定义必须是完全相同的，否则，仍然可能会有意外发生。

2020-06-02 10:50:05
范闲

2020-01-10 16:15:11

多态:
类的话是基于虚继承衍生出来的
函数的话是基于函数重载衍生出来的

不支持所有的多态方式:应该和语言的设计理念和哲学相关。

作者回复

可以看看其他的一些读者评论。

2020-01-10 22:43:33
花晨少年

2019-12-29 12:49:14

参数满足随机访问迭代器的要求。
———
是因为sort 是个复合排序，主体是使用快速排序，而快排貌似是有随机访问的需求吗

作者回复

sort不一定是快速排序，但通用的高性能排序算法一般都要求随机访问。sort解决的是通用情况。list::sort 则解决一种不能随机访问的特殊情况。

2019-12-30 10:50:08
lyfei

2019-12-24 19:28:09

老师您好，就是我对容器共性这一块有点疑惑：
比如老师讲的容器中的共性：begin, end等，但是又提到" C++ 的标准容器没有对象继承关系"；那对于不同的容器来说，vector, map, list等都得各自去实现自己的begin, end方法吗？
那既然不同的容器有着诸多的共性，为什么C++里不用继承呢？
谢谢老师的回复

作者回复

想一想：

为什么要继承？继承的话，能带来什么好处？

2019-12-24 20:07:32
Scott

2019-12-24 13:41:24

请问前几讲中最后的问题的答案可以公布一下吗？

作者回复

具体一点吧。哪一题你特别想知道又没有正确的回答？😎

2019-12-24 18:15:06