清华大学C++进阶讲义：第10章 泛型程序设计与C++标准模板库.pdf

### 清华大学C++进阶讲义：第10章 泛型程序设计与C++标准模板库 #### 泛型程序设计的基本概念 在计算机科学领域中，泛型程序设计是一种允许开发者编写能够处理多种数据类型的代码的技术。这种编程方式的核心在于编写不依赖于具体数据类型的程序，从而使得同样的代码可以适用于多种不同的数据类型，极大地提高了代码的复用性和灵活性。C++中的模板机制为实现泛型程序设计提供了强有力的支持。 #### 关键概念与术语 在泛型程序设计中，常常会遇到一些重要的概念和术语，它们是理解这一领域的基石： 1. **概念**：概念是用来界定具备一定功能的数据类型的一种方式。例如，“可以比大小的所有数据类型”被抽象为`Comparable`概念；而“具有公有的复制构造函数并可以用‘=’赋值的数据类型”则被称为`Assignable`概念。更进一步地，“可以比大小、具有公有的复制构造函数并可以用‘=’赋值的所有数据类型”被抽象为`Sortable`概念。 2. **模型**：模型是指符合某一概念的数据类型。例如，`int`类型是`Comparable`概念的一个模型。值得注意的是，并非所有数据类型都能成为某些概念的模型，比如静态数组类型就不是`Assignable`概念的模型，因为不能使用赋值运算符给整个静态数组赋值。 3. **概念作为模板参数**：在STL中，经常使用概念来命名模板参数，这有助于清晰地表达模板的适用范围。例如，一个插入排序函数模板可能这样定义：`template<class Sortable>` `void insertionSort(Sortable a[], int n);` 这里`Sortable`就是一个概念，它指代了一组满足特定条件的数据类型。 #### C++标准模板库(STL) C++标准模板库(STL)是一系列高效的数据结构和算法的集合，它为C++程序员提供了一个强大的工具箱。STL的设计哲学强调泛型程序设计，并围绕几个核心组件构建： 1. **容器**：容器是用来存储数据的对象。STL提供了多种容器类型，如`vector`、`list`、`set`、`map`等，每种容器都有其独特的特性和应用场景。例如，`vector`是一种动态数组，适合于需要频繁随机访问的场景；`list`则是一种双向链表，适合于频繁插入和删除操作。 2. **迭代器**：迭代器是泛化版本的指针，用于遍历容器中的元素。它们提供了访问容器内元素的能力，而无需暴露容器的具体实现细节。迭代器的存在使得各种容器可以共享相同的算法，增强了代码的可重用性。 3. **函数对象**：函数对象是一种行为类似函数的对象，它们通过重载函数调用运算符（即括号运算符）来实现。函数对象可以作为参数传递给算法，使算法更加灵活多变。 4. **算法**：STL中包含了大量预定义的算法，如排序、查找、复制等，这些算法通常接受迭代器作为参数，可以方便地应用于不同的容器。 #### STL的基本组件间的关系 - **迭代器作为算法和容器之间的桥梁**：迭代器充当了算法和容器之间的中间层，算法通过迭代器间接操作容器内的元素，这样即使容器内部实现发生变化也不会影响到算法本身。 - **函数对象作为算法的参数**：函数对象可以被传递给算法作为参数，这样可以定制算法的行为。例如，可以在排序算法中传入自定义的比较函数对象，以改变排序的标准。 #### 总结 通过上述讨论可以看出，C++中的泛型程序设计与标准模板库是紧密相连的。泛型程序设计的核心思想是编写不依赖于具体数据类型的代码，而STL正是基于这一思想构建的一系列高效的数据结构和算法。通过掌握泛型程序设计和STL的相关知识，开发者可以写出更加灵活、高效且易于维护的代码。