【C++学习笔记】泛型程序设计及STL的结构

墨蓝 2022-08-30 11:41 20阅读 0赞

### 文章目录 ###

*  0x00 前言
 *  0x01 泛型程序设计的基本概念
 *  0x02 STL简介
 *   *  1 容器（container）
     *  2 迭代器（iterator）
     *  3 函数对象（function object）
     *  4 算法（argorithm）

# 0x00 前言 #

文章中的文字可能存在语法错误以及标点错误，请谅解；

如果在文章中发现代码错误或其它问题请告知，感谢！

本文档为个人边学习边记录的C++笔记，非教程，**笔记中会存在引用他人文章内容的部分**，被引用的原文不会被特殊标记出来，但会在参考文档中给出原文链接。

# 0x01 泛型程序设计的基本概念 #

泛型程序设计（Generic Programming），就是不编写依赖与具体数据类型的程序。C++中，模板是泛型程序设计的主要工具。

泛型程序设计的主要思想就是将算法从特定的数据结构中抽象出来，使算法成为通用的、可以作用于各种不同的数据结构。这样就不必为每种容器都编写一套同样的算法，当容器类模板修改、扩充时也不必重写大量算法函数。这种以函数模板形式实现的通用算法与各种通用容器结合，提高了软件的复用性。

**我们可以用概念（concept）来描述泛型程序设计中作为参数的数据类型所具备的功能。这里的“概念”是泛型程序设计的一个术语，它的内涵是这些功能，它的外延是具备这些功能的所有数据类型**。例如，“可以用比较大小、具有公有的复制构造函数并可以用‘=’赋值的所有数据类型”就是一个概念，可以把这个概念记作Sortable。**具备一个概念所需要功能的数据类型称为这一概念的一个模型（model）**。例如，int数据类型就是一个Sortable概念的一个模型。另外，概念之间也有包含和被包含的关系，**对于两个不同概念A和B，如果概念A所需要的所有功能也是概念B所需求的功能（即概念B的模型一定是概念A的模型），那么就说概念B是概念A的子概念**（有些书又把它称为精炼（refinement））。我们可以把“可以比大小的所有数据类型”这一概念记为Comparable，把“具有公有的复制构造函数并可以用‘=’赋值的数据类型”这一概念极为Assignable，那么Sortable即是Comparable的子概念，也是Assignable的子概念。

# 0x02 STL简介 #

标准模板库（Standard Template Library，STL）最初是由HP公司的Alexander Stepanov 和 Meng Lee开发的一个用于支持C++泛型编程的模板库，1994被纳入了C++标准，称为C++标准库的一部分。由于C++标准库有多种不同的实现，因此STL也有不同的版本，但它们为用户提供的接口都遵守共同的标准。

STL提供了一些常用的数据结构和算法。STL更大的意义在于，它定义了一套概念体系，为泛型程序设计提供了逻辑基础。STL中的各个类模板，函数模板的参数都是用这个体系的概念规定的。使用STL的一个模板时所提供的类型参数既可以是C++标准库中已有的类型，也可以是自定义类型–只要这些类型时所要求概念的模型，因此，STL是一个开放的体系。

例：从标准输入中读入几个整数，存入向量容器，用STL输出它们的相反数

#include<iostream>
    #include<vector>
    #include<iterator>
    #include<algorithm>
    #include<functional>
    
    using namespace std;
    
    int main(){ 
        const int N = 5;
        vector<int>s(N);
    
        for(int i = 0;i < N;i++){ 
            cin>>s[i];        
        }
    
        transform(s.begin(), s.end(), ostream_iterator<int>(cout, " "), negate<int>());
        cout<<endl;
    
        return 0;
    }

运行结果：  
输入：

4 -2 1 0 5

输出：

-4 2 -1 0 -5

这个例子涉及STL4中基本组件，下面一一介绍。

## 1 容器（container） ##

容器就是容纳，包含一组元素的对象。容器类库中包括7中基本容器：向量（vector）、双端队列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）。这七种容器可以分为两种基本类型：顺序容器（sequence container）和关联容器（associative container）。顺序容器将一组具有相同类型的元素以严格的线性形式组织起来，向量、双端队列和列表容器就属于这一种。关联容器具有根据一组索引来快速提取元素的能力，集合和映射容器就属于这一种。

使用不同的容器，需要包含不同的头文件。

## 2 迭代器（iterator） ##

迭代器提供了顺序访问容器中的每个元素的方法。对迭代器可以使用“++”运算符来获得指向下一个元素的迭代器，可以使用“\*”运算符访问一个迭代器所指向的元素。如果元素类型是类或结构体，还可以使用“->”运算符方位该元素的一个成员，有些迭代器还支持通过“–”运算符获得指向上一个元素的迭代器。指针也具有同样的特性，因此指针本身就是一种迭代器，迭代器是泛化的指针。

使用独立于STL容器的迭代器，需要包含头文件。

## 3 函数对象（function object） ##

函数对象是一个行为类似函数的对象，对它可以像调用函数一样调用。任何普通的函数和任何重载了“（）”运算符的类的对象都可以作为函数对象使用，函数对象是繁华的函数。  
使用STL的函数对象，需要包含头文件

## 4 算法（argorithm） ##

STL包含70多个算法，这些算法覆盖了相当大的应用领域，其中包括查找算法、排序算法、消除算法、计数算法、比较算法、变换算法、置换算法和容器管理等。这些算法的一个最终哎哟的特定就是它们的统一性，并且可以广泛用于不同的对象和内置的数据类型。

上例中调用transform就是一个算法，为了说明该算法的用途，下面给出该算法的一种实现：

template<calss InputIterator, class OutputIterator, class UnaryFunction>
    OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op){ 
    	for(;first != last; ++first, ++result)
    		*result = op(*first);
    	return resrult;
    }

该算法顺序遍历first和last两个迭代器所指向的元素，将每个元素的值作为函数对象op的参数，将op的返回值通过迭代器result顺序输出。遍历完成后result迭代器指向的是输出的最后一个元素的下一个位置，transform会将该迭代器返回，上例程序忽略了这个返回值。

使用STL的算法，需要包含头文件。

STL4种基本组件它们之间的关系如图所示，STL把迭代器作为算法的参数，通过迭代器来访问容器而不是把容器直接作为算法的参数；STL把函数对象作为算法的参数而不是把函数所执行的运算作为算法的一部分。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdxaW5nY2h1YW45Mg_size_16_color_FFFFFF_t_70_pic_center]

《C++语言程序设计（第4版）》书上所有章节出现的示例源代码随着学习的深入会陆续上传至github，代码为个人手动输入并通过编译，有的示例代码可能没有注释：[https://github.com/fyw4/C-plus-plus-learning-example][https_github.com_fyw4_C-plus-plus-learning-example]  
以上。

参考文档：  
郑莉 董渊 何江舟.《C++语言程序设计（第4版）》\[M\].北京：清华大学出版社。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdxaW5nY2h1YW45Mg_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/2a8cf9adeaa24bd1b4ca7bd43d11d328.png
[https_github.com_fyw4_C-plus-plus-learning-example]: https://github.com/fyw4/C-plus-plus-learning-example