C++标准模板库学习笔记

学习时间：2023年1月9日

参考资料：

C++ primer plus中文第六版第十六章
行码棋的博客
C语言中文网

0 STL简介

0.1 概述

STL，英文全称 standard template library，中文可译为标准模板库或者泛型库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入/输出、数学计算等功能。

STL 最初由惠普实验室开发，于 1998 年被定为国际标准，正式成为 C++ 程序库的重要组成部分。值得一提的是，如今 STL 已完全被内置到支持 C++ 的编译器中，无需额外安装，这可能也是 STL 被广泛使用的原因之一。

Alexander Stepanov（后被誉为 STL 标准模板库之父，后简称 Stepanov），1950 年出生与前苏联的莫斯科，他曾在莫斯科大学研究数学，此后一直致力于计算机语言和泛型库研究。

0.2 STL组成

通常认为，STL 是由容器、算法、迭代器、函数对象、适配器、内存分配器这 6 部分构成，其中后面 4 部分是为前 2 部分服务的。

组成	含义
容器	一些封装数据结构的模板类，例如 vector 向量容器、list 列表容器等。
算法	STL 提供了非常多的数据结构算法，它们都被设计成一个个的模板函数，这些算法在 std 命名空间中定义，其中大部分算法都包含在头文件`<algorithm>`中，少部分位于头文件 `<numeric>` 中。
迭代器	在 STL 中，对容器中数据的读和写，是通过迭代器完成的，扮演着容器和算法之间的胶合剂。
函数对象	如果一个类将 `()`运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象（又称仿函数）。
适配器	可以使一个类的接口（模板的参数）适配成用户指定的形式，从而让原本不能在一起工作的两个类工作在一起。值得一提的是，容器、迭代器和函数都有适配器。
内存分配器	为容器类模板提供自定义的内存申请和释放功能，由于往往只有高级用户才有改变内存分配策略的需求，因此内存分配器对于一般用户来说，并不常用。

STL相关的头文件：

按照 C++ 标准库的规定，所有标准头文件都不再有扩展名。以 <vector> 为例，此为无扩展名的形式，而 <vector.h> 为有扩展名的形式。

1 string类

string类是由头文件string支持的，注意string.h和cstring不支持string类。

1.1 构造字符串

以下是string类的构造函数：

表中size_type是一个依赖于实现的整型。

string类使用string::npos定义为字符串的最大长度，通常为unsigned int的最大值。

程序实例

// str1.cpp -- introducing the string class
#include <iostream>
#include <string>

int main() {
    using namespace std;
    // 将one初始化为C风格字符串
    string one("Lottery Winner!");     // ctor #1
    cout << one << endl;               // overloaded <<
    // 将two初始化为20个$组成的字符串
    string two(20, '$');               // ctor #2
    cout << two << endl;
    // 复制构造
    string three(one);                 // ctor #3
    cout << three << endl;
    // +=重载，连接字符串
    one += " Oops!";                   // overloaded +=
    cout << one << endl;
    // =重载，可以将string对象、C风格字符串或char赋值给string对象
    two = "Sorry! That was ";
    // []重载，用于访问某个位置的字符
    three[0] = 'P';
    // 默认构造
    string four;                       // ctor #4
    // +和=的重载
    four = two + three;                // overloaded +, =
    cout << four << endl;
    char alls[] = "All's well that ends well";
    // 20表示复制alls的前20个字符
    string five(alls, 20);              // ctor #5
    cout << five << "!\n";
    // 模板参数构造
    string six(alls + 6, alls + 10);     // ctor #6
    cout << six  << ", ";
    // 模板参数构造
    string seven(&five[6], &five[10]); // ctor #6 again
    cout << seven << "...\n";
    string eight(four, 7, 16);         // ctor #7
    cout << eight << " in motion!" << endl;
    // std::cin.get();
    return 0; 
}

注意第6个构造函数使用了模板参数：

1 2	template<class Iter> string(Iter begin, Iter end);

通常，begin和end可以是迭代器（STL中的广义化指针）。使用[begin, end)区间的值来构造string对象。

本例中的使用：

1 2	// alls = All's well that ends well string six(alls + 6, alls + 10);

由于数组名相当于指针，所以alls+6和alls+10的类型都是char*，因此使用模板时，将用类型char*替换Iter。第一个参数指向数组 alls中的第一个w，第二个参数指向第一个well后面的空格。因此，six将被初始化为字符串"well"。

现在假设要用这个构造函数将对象初始化为另一个 string 对象（假设为 five）的一部分内容，则下面的语句不管用：

1	string seven(five + 6, five + 10);

原因在于，对象名不是对象的地址。但是five[6]是一个char，&five[6]就是该字符的地址，因此下面可行：

1	string seven(&five[6], &five[10]);

1.2 string类输入

暂略

1.3 使用字符串

1.3.1 比较字符串

string类对关系运算符（<,<=,==,!=,>=,>）进行了重载。对于每个关系运算符，都以三种方式进行重载，以便能够将string对象与另一个string对象，C风格字符串进行比较。

string s1("cobra");
string s2("coral");
char s3[] = "anaconda";
if(s1 < s2) { // operator<(const string &, const string &);
    // ...
}
if(s1 == s3) { // operator==(const string &, const char *);
   // ... 
}
if(s3 != s2) { // operator!=(const char *, const string &);
   // ... 
}

1.3.2 字符串长度

可使用length()或size()方法。前者来自较早版本的string类，后者为兼容STL而添加的。

1
2
3

if(s1.length() == s2.size()) {
    // ...
}

1.3.3 搜索子串和字符

string 类有一些查找子串和字符的成员函数，它们的返回值都是子串或字符在 string 对象字符串中的位置（即下标）。如果查不到，则返回 string::npos。string: :npos 是在 string 类中定义的一个静态常量，为字符串可存储的最大字符数，通常为unsigned int或unsigned long的最大取值。

以find方法为例，string类提供了四个重载函数：

// 从字符串的 pos 位置开始，查找子字符串 str。如果找到，则返回该子符符串首次出现时其首字符的索引；否则，返回string::npos
size_type find(const string &str, size_type pos = 0) const;

size_type find(const char* s, size_type pos = 0) const;

// 从字符串的 pos 位置开始，查找s的前n个字符组成的子字符串。如果找到，则返回该子字符串首次出现时其首字符的索引；
size_type find(const char* s, size_type pos = 0, size_type n) const;

// 从字符串的 pos 位置开始，查找字符ch。如果找到，则返回该字符首次出现的位置；
size_type find(char ch, size_type pos = 0) const;

此外，string类还提供了如下方法，他们的重载函数特征标与find()相同：

rfind：从后往前查找子串或字符出现的位置。
find_first_of：从前往后查找何处出现另一个字符串中包含的字符。
find_last_of：从后往前查找何处出现另一个字符串中包含的字符。
find_first_not_of：从前往后查找何处出现另一个字符串中没有包含的字符。
find_last_not_of：从后往前查找何处出现另一个字符串中没有包含的字符。

1.3.4 求子串

substr 成员函数可以用于求子串，原型如下：

1 2	// 从第n个位置开始，向后获取m个字符 string substr(int n = 0, int m = string::npos) const;

代码示例

string s1 = "this is ok";
string s2 = s1.substr(2, 4);  // s2 = "is i"
// 如果省略 m 或 m 超过了字符串的长度，则求出来的子串就是从下标 n 开始一直到字符串结束的部分
s2 = s1.substr(2);  // s2 = "is is ok"

1.4 字符串种类

string类实际上是基于一个模板类的：

template<class charT, class traits = char _traits<charT>,
	class Allocator = allocator<charT> >
basic_string {
	// ...
};

模板类basic_string有4个具体化：

typedef basic_string<char> string;
typedef basic_string<wchar_t> wstring;
typedef basic_string<char16_t> u16string; // C++11
typedef basic_string<char32_t> u32string; // C++11

2 智能指针模板类

暂略

3 标准模板库

本章只对一些基本概念进行解释和介绍。

3.1 模板类vector

矢量vector对应于数组。

vector模板使用动态分配内存：

#include <vector>
vector<int> ratings(5);
int n;
cin >> n;
vector<double> scores(n);

[]被重载，可以使用通常的数组表示法来访问各个元素：

ratings[0] = 9;
for(int i = 0; i < n; i++) {
    cout << scores[i] <<endl;
}

3.2 可对vector执行的操作

所有的STL容器都提供了一些基本方法：

size()：返回容器中元素的个数
swap()：交换两个容器的内容
begin()：返回一个指向容器中第一个元素的迭代器
end()：返回一个表示超过容器尾的迭代器，类似于字符串的\0

迭代器是一个广义指针。事实上，它可以是指针，也可以是一个可对其执行类似指针的操。通过将指针广义化为迭代器，让STL能够为各种不同的容器类（包括那些简单指针无法处理的类）提供统一的接口。每个容器类都定义了一个合适的迭代器（一个类成员），该迭代器的类型是一个名为iterator的typedef，其作用域为整个类。例如，要为vector的double类型规范声明一个迭代器，可以这样做：

1 2	// 声明一个迭代器 vector<double>::iterator pd;

使用：

1
2
3

pd = scores.begin();
*pd = 22.3; // scores[0] = 22.3;
++pd; // 让迭代器向前移动一个位置

可以看出，迭代器pd的行为类似于指针。

遍历容器：注意end的位置

for(pd = scores.begin(); pd != scores.end(); pd++) {
    cout << *pd << endl;
}
// 或者
for(pd = scores.begin(); pd < scores.end(); pd++) {
    cout << *pd << endl;
}

特有方法

vector容器中有其他容器不具有的特有方法。

push_back()：将元素添加进矢量末尾。它将负责动态内存管理，当矢量内存不够时，将自动扩容

vector<double> scores; // 一个空的vector
double temp;
while(cin >>temp && temp >= 0) {
    scores.push_back(temp);
}

erase()：接收两个迭代器，删除矢量中给定区间的元素，左闭右开

1	scores.erase(scores.begin(), scores.begin() + 2); // 删除begin()~begin()+1的元素

insert()：接收三个迭代器，第一个指定新元素的插入位置，第二三个指定插入区间，左闭右开

vector<int> old_v;
vector<int> new_v;
// ...
old_v.insert(old_v.begin(), new_v.begin() + 1, new_v.end());

上述代码将new_v的除第一个元素外的所有元素插入到old_v的第一个元素的前面。

3.3 其他操作

程序员通常要对数组执行很多操作，如搜索、排序、随机排序等。矢量模板类包含了执行这些常见的操作的方法吗？没有！STL从更广泛的角度定义了非成员（non-member）函数来执行这些操作，即不是为每个容器类定义find成员函数，而是定义了一个适用于所有容器类的非成员函数find。这种设计理念省去了大量重复的工作。

另一方面，即使有执行相同任务的非成员函数，STL有时也会定义一个成员函数。这是因为对有些操作来说，类特定算法的效率比通用算法高，因此，vector的成员函数swap的效率比非成员函数swap高，但非成员函数让您能够交换两个类型不同的容器的内容。

for_each()：接收三个参数，前两个是定义容器中区间的迭代器，最后一个是指向函数的指针（准确来说是函数对象）。它将被指向的函数应用于容器区间中的各个元素，函数不能修改容器元素的值。

// 函数原型
template<typename _InputIterator, typename _Function>
_Function
for_each(_InputIterator __first, _InputIterator __last, _Function __f);

使用：

vector<Review>::iterator pr;
for(pr = books.begin(); pr != books.end(); pr++) {
    ShowReview(*pr);
}
// 可以替换为
for_each(books.begin(), books.end(), ShowReview);

random_shuffle()：接收两个指定容器区间的迭代器，随机排列该区间中的元素。

1	random_shuffle(books.begin(), books.end());

该函数要求容器类允许随机访问。

sort()：要求容器支持随机访问

第一个版本：接受两个定义区间的迭代器参数，并使用为存储在容器中的类型元素定义的<运算符，对区间中的元素进行操作。例如，下面的语句按升序对coolstuff的内容进行排序，排序时使用内置的<运算符对值进行比较：
1
2
3
vector<int> coolstuff;
// ...
sort(coolstuff.begin(), coolstuff.end());

第二个版本：如果容器元素是自定义类型，需要在类中对operator<()函数进行重载

// Review类中：
bool operator<(const Review & r1,const Review & r2) {
    // 先对title比较
    if (r1.title < r2.title)
		return true;
    // title相同则按rating比较
	else if(rl.title == r2.title && r1.rating < r2.rating)
		return true;
    else
		return false;
}

// 使用：
vector<Review> books;
sort(books.begin(), books.end());

第三个版本：接受两个定义区间的迭代器参数，第三个参数是指向要使用的函数的指针（函数对象）

bool WorseThan(const Review & r1, const Review & r2) {
    if(r1.rating < r2.rating) {
        return true;
    } else {
        return false;
    }
}

// 使用
sort(books.begin(), books.end(), WorseThan);

3.4 基于范围的for循环

在Java中为增强for循环。

基于范围的for循环是为用于STL而设计的，但不仅可用于STL：

double prices[5] = {1.1, 1.2, 1.3, 1.4, 1.5};
for(double x : prices) {
    cout << x << endl;
}

对于for_each循环，可以修改为基于范围的for循环：

for_each(books.begin(), books.end(), func);
// 基于范围的for：
for(Review x : books) {
    func(x);
}
// 还可以使用auto关键字自动判别x的类型
for(auto x : books) {
    func(x);
}

基于范围的for循环可以修改容器元素，而for_each不行。

4 泛型编程

STL是一种泛型编程。泛型编程关注的是算法。

4.1 迭代器的必要性

模板使得算法独立于数据类型，迭代器使得算法独立于容器类型（数据结构）。

问题的引出：find函数

在一个double数组中搜索特定值

// n 为数组大小
double * find_ar(double * ar, int n, const double & val) {
    for(int i = 0; i < n; ++i) {
        if(ar[i] == val) {
            return &ar[i];
        }
    }
    return 0; // or return nullptr;
}

可以用模板将这种算法推广到包含==运算符的、任意类型的数组。尽管如此，这种算法仍然与一种特定的数据结构（数组）关联在一起。

在一个链表中搜索特定值

struct Node {
    double item;
    Node * p_next;
};

Node* find_ll(Node* head, const double & val) {
    Node* start;
    for(start = head; start != nullptr; start = start->p_next) {
        if(start->item == val) {
            return start;
        }
    }
    return nullptr;
}

同样，也可以使用模板将这种算法推广到支持==运算符的任何数据类型的链表。然而，这种算法也是与特定的数据结构（链表）关联在一起。

从实现细节上看，这两个find函数的算法是不同的：一个使用数组索引来遍历元素，另一个则将start 重置为 start->p_next。但从广义上说，这两种算法是相同的：将值依次与容器中的每个值进行比较，直到找到匹配的为止。

泛型编程旨在使用同一个find函数来处理数组、链表或任何其他容器类型。即函数不仅独立于容器中存储的数据类型，而且独立于容器本身的数据结构。模板提供了存储在容器中的数据类型的通用表示，因此还需要遍历容器中的值的通用表示，迭代器正是这样的通用表示。

要实现find函数，迭代器应至少具备哪些特征呢？下面是一个简短的列表。

应能够对迭代器执行解除引用的操作，以便能够访问它引用的值。即如果p是一个迭代器，则应对*p进行定义。
应能够将一个迭代器赋给另一个。即如果p和q都是迭代器，则应对表达式 p=q 进行定义。
应能够将一个迭代器与另一个进行比较，看它们是否相等。即如果p和q都是迭代器，则应对p==q和p!=q进行定义。
应能够使用迭代器遍历容器中的所有元素，这可以通过为迭代器p定义++p和p++来实现。

除了上面的功能之外，还可能有其他的功能。实际上，STL按照功能的强弱定义了多种级别的迭代器。

修改后的find函数

常规指针就能满足迭代器的要求，对于find_ar函数可以修改为：

typedef double* iterator;
iterator find_ar(iterator ar, int n, const double & val) {
    for(int i = 0; i < n; i++, ar++)
        if(*ar == val)
            return ar;
    return 0;
}

然后可以修改函数参数，使之接受两个指示区间的指针参数，其中的一个指向数组的起始位置，另一个指向数组的超尾：同时函数可以通过返回尾指针，来指出没有找到要找的值，下面的find_ar版本完成了这些修改：

typedef double* iterator;
iterator find_ar(iterator begin, iterator end, const double & val) {
    iterator ar;
    for(ar = begin; ar != end; ar++)
        if(*ar == val)
            return ar;
    return end; // 没有找到
}

对于find_ll函数，可以定义一个迭代器类iterator，其中重载了*和++

class iterator {
    Node * pt;
public:
    iterator() : pt(0) {}
    iterator(Node * pn) : pt(pn) {}
    doiuble operator*() { return pt->item; }
    iterator& operator++() { // for ++pt;
        pt = pt->p_next;
        return *this;
    }
    iterator& iterator++(int) { // for pt++;
        iterator tmp = *this;
        pt = pt->p_next;
        return tmp;
    }
    // ...
};

于是函数可以修改为：

iterator find_ll(iterator head, const double & val) {
    iterator start;
    for(start = head; start != 0; ++start) {
        if(*start == val)
            return start;
    }
    return 0;
}

这和 find_ar几乎相同，差别在于如何谓词已到达最后一个值。find_ar函数使用超尾迭代器，而find_ll使用存储在最后一个节点中的空值。除了这种差别外，这两个函数完全相同。例如，可以要求链表的最后一个元素后面还有一个额外的元素，即让数组和链表都有超尾元素，并在迭代器到达超尾位置时结束搜索。这样，find_ar和find_ll检测数据尾的方式将相同，从而成为相同的算法。

注意，增加超尾元素后，对迭代器的要求变成了对容器类的要求。

STL对迭代器的实现

STL遵循上面介绍的方法。首先，每个容器类（vector、list、deque等）定义了相应的迭代器类型。

对于其中的某个容器类，迭代器可能是指针；而对于另一个容器类，迭代器则可能是对象。不管实现方式如何，迭代器都将提供所需的操作，如*和++（有些类需要的操作可能比其他类多）。其次，每个容器类都有一个超尾标记，当迭代器递增到超越容器的最后一个值后，这个值将被赋给迭代器。每个容器类都有begin和end方法，它们分别返回一个指向容器的第一个元素和超尾位置的迭代器。每个容器类都使用++操作，让迭代器从指向第一个元素逐步指向超尾位置，从而遍历容器中的每一个元素。

使用容器类时，无需知道其迭代器是如何实现的，也无需知道超尾是如何实现的，而只需知道它有迭代器，其begin返回一个指向第一个元素的迭代器，end返回一个指向超尾位置的迭代器即可。

例如：

vector<double>::iterator pr; // 将pr声明为vector<double>类的迭代器
for(pr = scores.begin(); pr != scores.end(); pr++)
    cout << *pr << endl;

list<double>::iterator pr; // 将pr声明为vector<double>类的迭代器
for(pr = scores.begin(); pr != scores.end(); pr++)
    cout << *pr << endl;

唯一不同的是pr的类型。因此，STL通过为每个容器模板类定义适当的迭代器，并以统一的风格设计类，能够对内部表示绝然不同的容器，编写相同的代码。

使用C++11新增的自动类型推断可进一步简化：对于矢量或列表，都可使用如下代码：

// 省去了vector<double>::iterator pr;声明
// 使用auto自动判定类型
for(auto pr = scores.begin(); pr != scores.end(); pr++)
    cout << *pr << endl;

// 或者：基于范围的for循环
for(auto x : scores) cout << x << endl;

4.2 迭代器类型

不同的算法对迭代器的要求不同，STL定义了5种迭代器。

4.2.1 输入迭代器

略，单向迭代器，只能递增。

4.2.2 输出迭代器

略，单向迭代器，只能递增。

4.2.3 正向迭代器

单向迭代器，只能递增++，可以修改和读取数据：

1 2	int * pirw; // read-write iterator const int * pirw; // read-only iterator

4.2.4 双向迭代器

能够双向遍历容器，即可以进行++和--的操作。

4.2.5 随机访问迭代器

有些算法（如标准排序和二分检索）要求能够直接跳到容器中的任何一个元素，这叫做随机访问，需要随机访问迭代器。

随机访问迭代器具有双向迭代器的所有特性，同时添加了支持随机访问的操作（如指针增加运算）和用于对元素进行排序的关系运算符。下表列出了除双向迭代器的操作外，随机访问迭代器还支持的操作。其中，a和b都是迭代器值，n为整数，r为随机迭代器变量或引用。

4.3 迭代器层次结构

下表中i为迭代器，n为整数：

提供多种迭代器的必要性

目的是为了在编写算法尽可能使用要求最低的迭代器，并让它适用于容器的最大区间。这样，通过使用级别最低的输入迭代器，find函数便可用于任何包含可读取值的容器。而sort函数由于需要随机访问迭代器，所以只能用于支持这种迭代器的容器。

注意，各种迭代器的类型并不是确定的，而只是一种概念性描述。正如前面指出的，每个容器类都定义了一个类级typedef名称——iterator，因此 vector<int> 类的迭代器类型为 vector<int>::interator。然而，该类的文档将指出，矢量迭代器是随机访问迭代器，它允许使用基于任何迭代器类型的算法，因为随机访问迭代器具有所有迭代器的功能。同样，list<int>类的迭代器类型为list<int>::iterator。STL实现了一个双向链表，它使用双向迭代器，因此不能使用基于随机访问迭代器的算法，但可以使用基于要求较低的迭代器的算法。

容器	对应的迭代器类型
`array`	随机访问迭代器
`vector`	随机访问迭代器
`deque`	随机访问迭代器
`list`	双向迭代器
`set / multiset`	双向迭代器
`map / multimap`	双向迭代器
`forward_list`	前向迭代器
`unordered_map / unordered_multimap`	前向迭代器
`unordered_set / unordered_multiset`	前向迭代器
`stack`	不支持迭代器
`queue`	不支持迭代器

4.4 概念、改进和类型

概念是具有名称的通用类别，例如正向迭代器，双向迭代器，序列容器等，它满足一系列的要求。

改进是概念上的继承，例如双向迭代器是对正向迭代器的改进。

类型是概念的具体实现。

例如，指向int的常规指针是一个随机访问迭代器模型，也是一个正向迭代器模型，因为它满足该概念（随机访问和正向）的所有要求。

4.4.1 预定义迭代器类型

迭代器定义方式	具体格式
正向迭代器	`容器类名::iterator 迭代器名;`
常量正向迭代器	`容器类名::const_iterator 迭代器名;`
反向迭代器	`容器类名::reverse_iterator 迭代器名;`
常量反向迭代器	`容器类名::const_reverse_iterator 迭代器名;`

通过定义以上几种迭代器，就可以读取它指向的元素，*迭代器名就表示迭代器指向的元素。其中，常量迭代器和非常量迭代器的分别在于，通过非常量迭代器还能修改其指向的元素。另外，反向迭代器和正向迭代器的区别在于：

对正向迭代器进行 ++ 操作时，迭代器会指向容器中的后一个元素；
而对反向迭代器进行 ++ 操作时，迭代器会指向容器中的前一个元素。

代码示例

#include <iostream>
//需要引入 vector 头文件
#include <vector>
using namespace std;
int main() {
    vector<int> v{1,2,3,4,5,6,7,8,9,10}; //v被初始化成有10个元素
    cout << "第一种遍历方法：" << endl;
    //size返回元素个数
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] <<" "; //像普通数组一样使用vector容器
    //创建一个正向迭代器，当然，vector也支持其他 3 种定义迭代器的方式
    
    cout << endl << "第二种遍历方法：" << endl;
    vector<int>::iterator i;
    //用 != 比较两个迭代器
    for (i = v.begin(); i != v.end(); ++i)
        cout << *i << " ";
    
    cout << endl << "第三种遍历方法：" << endl;
    for (i = v.begin(); i < v.end(); ++i) //用 < 比较两个迭代器
        cout << *i << " ";
   
    cout << endl << "第四种遍历方法：" << endl;
    i = v.begin();
    while (i < v.end()) { //间隔一个输出
        cout << *i << " ";
        i += 2; // 随机访问迭代器支持 "+= 整数"  的操作
    }
}

4.4.2 容器适配器

STL 提供了 3 种容器适配器，分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。

容器适配器	基础容器筛选条件	默认使用的基础容器
stack	满足条件的基础容器有 vector、deque、list。	deque
queue	满足条件的基础容器有 deque、list。	deque
priority_queue	满足条件的基础容器有vector、deque。	vector

详见4.5.2节序列容器

4.5 容器种类

STL具有容器概念和容器类型。概念是具有名称（如容器、序列容器、关联容器等）的通用类别；容器类型是可用于创建具体容器对象的模板，有deque，stack等等。

4.5.1 基本容器

所有的容器都提供某些特征和操作，以下是一些基本的容器特征：

X表示容器类型，如 vector
T表示存储在容器中的对象类型；
a和b表示类型为X的值；
r表示类型为X&的值；
u表示类型为X的标识符（即如果X表示 vector<int>，则u是一个vector<int>对象）。

容器通用操作

4.5.2 序列容器

可以通过添加要求来改进基本的容器概念。序列是一种重要的改进，这种容器的概念称为序列容器。

序列要求：

迭代器至少是正向迭代器（正向、双向或随机的一种）
容器元素按严格的线性顺序排列（有前驱和后继）

模板类deque，list，queue，priority_queue，stack和vector都是序列概念的模型。它们都支持上表中的操作，此外某些容器还有额外的操作可支持：

① vector

该模板类在<vector>头文件中声明。

vector 是数组的一种类表示，它提供了自动内存管理功能，可以动态地改变vector对象的长度，并随着元素的添加和删除而增大和缩小。它提供了对元素的随机访问。在尾部添加和删除元素的时间是固定的，但在头部或中间插入和删除元素的复杂度为线性时间。

除序列外，vector还是可反转容器（reversible container）概念的模型。这增加了两个类方法：rbegin和rend，前者返回一个指向反转序列的第一个元素的迭代器，后者返回反转序列的超尾迭代器。因此，如果dice是一个vector<int>容器，而Show(int)是显示一个整数的函数，则下面的代码将首先正向显示dice的内容，然后反向显示：

1 2	for_each(dice.begin(), dice.end(), Show); // 正向显示 for_each(dice.rbegin(), dice.rend(), Show); // 反向显示

② deque

在<deque>中声明，表示双端队列double-ended queue。

在STL中，其实现类似于vector容器，支持随机访问。主要区别在于，从deque对象的开始位置插入和删除元素的时间是固定（常数时间复杂度）的，而不像 vector 中那样是线性时间的。所以，如果多数操作发生在序列的起始和结尾处，则应考虑使用deque数据结构。

为实现在 deque 两端执行插入和删除操作的时间为固定的这一目的，deque 对象的设计比 vector 对象更为复杂。因此，尽管二者都提供对元素的随机访问和在序列中部执行线性时间的插入和删除操作，但vector容器执行这些操作时速度要快些。

③ list

在<list>中声明，表示双向链表。

除了第一个和最后一个元素外，每个元素都与前后的元素相链接，这意味着可以双向遍历链表。list和 vector 之间关键的区别在于，list 在链表中任一位置进行插入和删除的时间都是固定的（vector 模板提供了除结尾处外的线性时间的插入和删除，在结尾处，它提供了固定时间的插入和删除）。因此，vector强调的是通过随机访问进行快速访问，而 list 强调的是元素的快速插入和删除。

与vector相似，list也是可反转容器。与vector不同的是，list不支持数组表示法和随机访问。

此外，list模板类还提供了专用的成员函数：

程序实例

// list.cpp -- using a list
#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>

void outint(int n) { std::cout << n << " "; }

int main() {
    using namespace std;
    list<int> one(5, 2); // list of 5 2s
    int stuff[5] = {1,2,4,8, 6};
    list<int> two;
    two.insert(two.begin(),stuff, stuff + 5 );
    int more[6] = {6, 4, 2, 4, 6, 5};
    list<int> three(two);
    three.insert(three.end(), more, more + 6);

    cout << "List one: ";
    for_each(one.begin(),one.end(), outint);
    cout << endl << "List two: ";
    for_each(two.begin(), two.end(), outint);
    cout << endl << "List three: ";
    for_each(three.begin(), three.end(), outint);
    three.remove(2);
    cout << endl << "List three minus 2s: ";
    for_each(three.begin(), three.end(), outint);
    three.splice(three.begin(), one);
    cout << endl << "List three after splice: ";
    for_each(three.begin(), three.end(), outint);
    cout << endl << "List one: ";
    for_each(one.begin(), one.end(), outint);
    three.unique();
    cout << endl << "List three after unique: ";
    for_each(three.begin(), three.end(), outint);
    three.sort();
    three.unique();
    cout << endl << "List three after sort & unique: ";
    for_each(three.begin(), three.end(), outint);
    two.sort();
    three.merge(two);
    cout << endl << "Sorted two merged into three: ";
    for_each(three.begin(), three.end(), outint);
    cout << endl;

    return 0; 
}

打印结果：

④ forward_list

表示单向链表。不可反转，提供正向迭代器。

⑤ queue

在<queue>中声明，是一个适配器类，它让底层类（默认为deque）展示典型的队列接口。

queue模板的限制比deque更多。它不仅不允许随机访问队列元素，甚至不允许遍历队列（没有迭代器）。

它把使用限制在定义队列的基本操作上，可以将元素添加到队尾、从队首删除元素、查看队首和队尾的值、检查元素数目和测试队列是否为空。

注意pop函数没有返回值，如果要取得队首元素，需要先使用front来取得队首元素，再用pop删除。

代码示例

创建一个空的 queue 容器适配器，其底层使用的基础容器选择默认的 deque 容器：

1	queue<int> values;

也可以手动指定 queue 容器适配器底层采用的基础容器类型。

1	queue<int, list<int>> values;

可以用基础容器来初始化 queue 容器适配器，只要该容器类型和 queue 底层使用的基础容器类型相同即可。

1 2	deque<int> values{1,2,3}; queue<int> my_queue(values);

使用

#include <iostream>
#include <queue>
#include <deque>
#include <list>
using namespace std;
int main()
{
    //构建 queue 容器适配器
    deque<int> values{ 1,2,3 };
    queue<int> my_queue(values); //{1,2,3}
    //查看 my_queue 存储元素的个数
    cout << "size of my_queue: " << my_queue.size() << endl;
    //访问 my_queue 中的元素
    while (!my_queue.empty())
    {
        cout << my_queue.front() << endl;
        //访问过的元素出队列
        my_queue.pop();
    }
    return 0;
}

执行结果：

size of my_queue: 3
1
2
3

⑥ priority_queue

在<queue>中声明，是一个容器适配器类，默认的底层类为vector。

优先队列是在正常队列的基础上加了优先级，保证每次的队首元素都是优先级最大的。底层是通过堆来实现的。

特性：First in, Largest out

可以修改用于确定哪个元素放到队首的比较方式，方法是提供一个可选的构造函数参数：

1 2	priority_queue<int> pq1; // default version priority_queue<int> pq2(greater<int>); // use greater<int> to order 小根堆

支持的操作：

方法	含义
`q.top()`	访问队首元素
`q.push()`	入队
`q.pop()`	堆顶（队首）元素出队
`q.size()`	队列元素个数
`q.empty()`	是否为空
注意没有`clear()`！	不提供该方法
优先队列只能通过`top()`访问队首元素（优先级最高的元素）

代码示例

#include <iostream>
#include <queue>
#include <array>
#include <functional>
using namespace std;
int main() {
    //创建一个空的priority_queue容器适配器
    std::priority_queue<int> values;
    //使用 push() 成员函数向适配器中添加元素
    values.push(3);
    values.push(1);
    values.push(4);
    values.push(2);
    //遍历整个容器适配器
    while (!values.empty()) {
        //输出第一个元素并移除。
        std::cout << values.top()<<" ";
        values.pop();//移除队头元素的同时，将剩余元素中优先级最大的移至队头
    }
    return 0;
}

打印结果：

4 3 2 1

⑦ stack

在<stack>中声明，是一个容器适配器类，默认底层类为vector。stack的限制和queue相同。

支持的操作如下：

和queue相同，pop没有返回值。

⑧ array

在<array>中声明，C++11标准，并非STL容器。

4.5.3 关联容器

关联容器是对容器概念的另一个改进。关联容器将值与键关联在一起，并使用键来查找值。

关联容器带有模板参数Key和Compare，这两个参数分别表示用来对内容进行排序的键类型和用于对键进行比较的函数对象（被称为比较对象），后者的默认参数为less，即按升序排序。

对于set和multiset容器，存储的键就是存储的值，因此键类型与值类型相同。
对于map和multimap容器，存储的值（模板参数T）与键类型（模板参数Key）相关联，值类型为 pair<const Key, T>。

注意，关联容器中存储的元素，就是一个个的pair类（键值对）的对象。迭代器指向的关联容器元素，就是容器中的pair对象。

关联容器的优点在于，它提供了对元素的快速访问。与序列相似，关联容器也允许插入新元素，但不能指定元素的插入位置。原因是关联容器通常有用于确定数据放置位置的算法，以便能够快速检索信息。

关联容器通常是使用某种树实现的（例如红黑树）。树是一种数据结构，其根节点链接到一个或两个节点，而这些节点又链接到一个或两个节点，从而形成分支结构。像链表一样，节点使得添加或删除数据项比较简单；但相对于链表，树的查找速度更快。

C++ STL 标准库提供了 4 种关联式容器，分别为 map、set、multimap、multiset。

名称	特点
map	定义在 `<map>` 头文件中，使用该容器存储的数据，其各个元素的键必须是唯一的（即不能重复），该容器会根据各元素键的大小，默认进行升序排序（调用 `std::less<T>`）。
set	定义在 `<set>` 头文件中，使用该容器存储的数据，各个元素键和值完全相同，且各个元素的值不能重复（保证了各元素键的唯一性）。该容器会自动根据各个元素的键（其实也就是元素值）的大小进行升序排序（调用 `std::less<T>`）。
multimap	定义在 `<map>` 头文件中，和 map 容器唯一的不同在于，multimap 容器中存储元素的键可以重复。
multiset	定义在 `<set>` 头文件中，和 set 容器唯一的不同在于，multiset 容器中存储元素的值可以重复（一旦值重复，则意味着键也是重复的）。

① pair

上面提到，对于map和multimap，键值对中的值的类型为pair<const Key, T>，即由key的类型和T的类型组成的pair类型。

pair 类模板定义在<utility>头文件中。成员为first和second，可以分别表示键和值。

代码示例

#include <iostream>
#include <utility>      // pair
#include <string>       // string
using namespace std;
int main() {
    // 调用构造函数 1，也就是默认构造函数
    pair <string, double> pair1;
    // 调用第 2 种构造函数
    pair <string, string> pair2("STL教程","http://c.biancheng.net/stl/");  
    // 调用拷贝构造函数
    pair <string, string> pair3(pair2);
    //调用移动构造函数
    pair <string, string> pair4(make_pair("C++教程", "http://c.biancheng.net/cplus/"));
    // 调用第 5 种构造函数
    pair <string, string> pair5(string("Python教程"), string("http://c.biancheng.net/python/"));  
   
    cout << "pair1: " << pair1.first << " " << pair1.second << endl;
    cout << "pair2: "<< pair2.first << " " << pair2.second << endl;
    cout << "pair3: " << pair3.first << " " << pair3.second << endl;
    cout << "pair4: " << pair4.first << " " << pair4.second << endl;
    cout << "pair5: " << pair5.first << " " << pair5.second << endl;
    return 0;
}

执行结果：

pair1:  0
pair2: STL教程 http://c.biancheng.net/stl/
pair3: STL教程 http://c.biancheng.net/stl/
pair4: C++教程 http://c.biancheng.net/cplus/
pair5: Python教程 http://c.biancheng.net/python/

② map

函数方法：

成员方法	功能
`begin()`	返回指向容器中第一个（注意，是已排好序的第一个）键值对的双向迭代器。
`end()`	返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。
`find(key)`	在 map 容器中查找键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。
`lower_bound(key)`	返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。
`upper_bound(key)`	返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。
`operator[key]`	map容器重载了 `[]` 运算符，只要知道 map 容器中某个键值对的键的值，就可以向获取数组中元素那样，通过键直接获取对应的值。例如`m[key]`
`at(key)`	找到 map 容器中 key 键对应的值，如果找不到，该函数会引发 out_of_range 异常。
`insert()`	向 map 容器中插入键值对。需要构造键值对。使用`pair`。
`erase(key	iter)`	删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对。左闭右开。
`emplace()`	在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样，但效率更高。

添加元素

map<int,int> mp;
// 方式1
mp[1] = 1; // 1为key，1为value
// 方式2
mp.insert(pair<int,int>(1, 1));
// 方式3
mp.insert({1, 1});

代码示例

#include <iostream>
#include <map>      // map
#include <string>       // string
using namespace std;
int main() {
    //创建空 map 容器，默认根据个键值对中键的值，对键值对做降序排序
    std::map<std::string, std::string, std::greater<std::string>>myMap;
    //调用 emplace() 方法，直接向 myMap 容器中指定位置构造新键值对
    myMap.emplace("C语言教程","http://c.biancheng.net/c/");
    myMap.emplace("Python教程", "http://c.biancheng.net/python/");
    myMap.emplace("STL教程", "http://c.biancheng.net/stl/");
    //输出当前 myMap 容器存储键值对的个数
    cout << "myMap size==" << myMap.size() << endl;
    //判断当前 myMap 容器是否为空
    if (!myMap.empty()) {
        //借助 myMap 容器迭代器，将该容器的键值对逐个输出
        for (auto i = myMap.begin(); i != myMap.end(); ++i) {
            cout << i->first << " " << i->second << endl;
        }
    }
    return 0;
}

打印结果：

myMap size==3
STL教程 http://c.biancheng.net/stl/
Python教程 http://c.biancheng.net/python/
C语言教程 http://c.biancheng.net/c/

③ set

略

4.5.4 无序关联容器

无序关联容器（或称哈希容器）是对容器概念的另一种改进。

与关联容器一样，无序关联容器也将值与键关联起来，并使用键来查找值。但底层的差别在于，关联容器是基于树结构的，而无序关联容器是基于数据结构哈希表的，这旨在提高添加和删除元素的速度以及提高查找算法的效率。

C++ STL 底层采用哈希表实现无序容器时，会将所有数据存储到一整块连续的内存空间中，并且当数据存储位置发生冲突时，解决方法选用的是“链地址法”（又称“开链法”）。

特点：

无序容器内部存储的键值对是无序的，各键值对的存储位置取决于该键值对中的键，
和关联式容器相比，无序容器擅长通过指定键查找对应的值（平均时间复杂度为 O(1)）；但对于使用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器。

有4种无序关联容器，它们是unordered_set、unordered_multiset、unordered map 和 unordered multimap。

名称	特点
unordered_map	存储键值对 `<key, value>` 类型的元素，其中各个键值对键的值不允许重复，且该容器中存储的键值对是无序的。
unordered_multimap	和 unordered_map 唯一的区别在于，该容器允许存储多个键相同的键值对。
unordered_set	不再以键值对的形式存储数据，而是直接存储数据元素本身（当然也可以理解为，该容器存储的全部都是键 key 和值 value 相等的键值对，正因为它们相等，因此只存储 value 即可）。另外，该容器存储的元素不能重复，且容器内部存储的元素也是无序的。
unordered_multiset	和 unordered_set 唯一的区别在于，该容器允许存储值相同的元素。

① unordered_map

在<unordered_map>中声明。

unordered_map 容器不会像 map 容器那样对存储的数据进行排序。换句话说，unordered_map 容器和 map 容器仅有一点不同，即 map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。

常用方法：同map

代码示例

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
    //创建空 umap 容器
    unordered_map<string, string> umap;
    //向 umap 容器添加新键值对
    umap.emplace("Python教程", "http://c.biancheng.net/python/");
    umap.emplace("Java教程", "http://c.biancheng.net/java/");
    umap.emplace("Linux教程", "http://c.biancheng.net/linux/");
    //输出 umap 存储键值对的数量
    cout << "umap size = " << umap.size() << endl;
    //使用迭代器输出 umap 容器存储的所有键值对
    for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
        cout << iter->first << " " << iter->second << endl;
    }
    return 0;
}

打印结果：

umap size = 3
Python教程 http://c.biancheng.net/python/
Linux教程 http://c.biancheng.net/linux/
Java教程 http://c.biancheng.net/java/

② unordered_set

略

5 函数对象

5.1 简介

很多STL算法都使用函数对象——也叫函数符（functor）、仿函数。

函数符是可以以函数方式与()结合使用的任意对象。这包括函数名、指向函数的指针和重载了()运算符的类对象（即定义了函数operator()）的类），例如，可以像这样定义一个类：

class Linear {
	double slope;
    double y0;
public:
    Linear(double sl_ = 1, double y_ = 0) : slope(sl_), y0(y_) {}
    // 提供对()的重载
    double operator()(double x) { return y0 + slope * x; }
};

对于重载的()运算符，使得能够像函数一样使用Linear的对象：

Linear f1;
Linear f2(2.5, 10.0);
// 此时的f1（重载了括号运算符的类对象）为函数符
double y1 = f1(12.5);
double y2 = f2(0.4);

对于for_each，它将指定的函数应用于区间中的每个成员：

1	for_each(books.begin(), books.end(), ShowReview);

函数将第三个参数（函数）设置为模板参数（因为可能为函数指针或函数符），其函数原型为：

1 2	template<class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f);

ShowReview的原型为：

1	void ShowReview(const Review &);

这样赋给模板参数Function的类型为void(*)(const Review &)。

代码示例

template<typename Function>
void process(vector<int> &num, Function f){
    for(int i = 0; i < num.size(); i ++){
        // 将f作用于num[i]上
        f(num[i]);
    }
}

// 声明一个函数符, 输出数组中的每个元素
class Output{
public:
    // 对()重载，使得对象可以成为函数那样被调用——仿函数
    void operator()(int x){
        cout<<x<<endl;
    }
};
 
int main(){
    int a[5] = {1, 2, 3, 4, 5};
    vector<int> num(&a[0], &a[5]);
    Output out;
    process(num, out);
    return 0;
}

5.2 函数符概念

正如STL定义了容器和迭代器的概念一样，它也定义了函数符概念。

生成器（generator）是不用参数就可以调用的函数符
一元函数（unary function）是用一个参数可以调用的函数符
二元函数（binary function）是用两个参数可以调用的函数符。

例如，提供给 for_each的函数符应当是一元函数，因为它每次用于一个容器元素。

当然，这些概念都有相应的改进版：

返回bool值的一元函数是谓词（predicate）；
返回bool值的二元函数是二元谓词（binary predicate）。

一些STL函数需要谓词参数或二元谓词参数。例如，使用了sort的这样一个版本，即将二元谓词作为其第3个参数：

// 二元谓词
bool WorseThan(const Review &, const Review &);
// ...
sort(books.begin(), books.end(), WorseThan);

5.3 预定义的函数符

引入

例如，考虑函数transform。它有两个版本。

第一个版本将接收四个参数，前两个指定区间的迭代器，第三个是指定将结果复制到哪里的迭代器，最后一个参数是一个函数符，为一元函数。

const int LIM = 5;
double arr1[LIM] = {1, 2, 3, 4, 5};
vector<double> gr8(arr1, arr1 + LIM);
ostream_iterator<double, char> out(cout, " ");
transform(gr8.begin(), gr8.end(), out, sqrt);

上述代码计算每个元素的平方根，并将结果发送到输出流。目标迭代器可以位于原始区间中。例如，将上述示例中的out替换为gr8.begin后，新值将覆盖原来的值。很明显，使用的函数符必须是接受单个参数的函数符。

第二种版本使用一个接受两个参数的函数，并将该函数用于两个区间中元素。它用另一个参数（即第3个）标识第二个区间的起始位置。例如，如果 m8 是另一个vector<double>对象，mean(double, double)返回两个值的平均值，则下面的的代码将输出来自gr8和m8的值的平均值：

1	transform(gr8.begin(), gr8.end(), m8.begin(), out, mean);

现在假设要将两个数组相加。不能将+作为参数，因为对于类型double来说，+是内置的运算符，而不是函数。可以定义一个将两个数相加的函数，然后使用它：

1
2
3

double add(double x, double y) { return x + y; }
// ...
transform(gr8.begin(), gr8.end(), m8.begin(), out, add);

介绍

STL定义了多个基本函数符，它们执行诸如将两个值相加、比较两个值是否相等操作。提供这些函数对象是为了支持将函数作为参数的STL函数。

可以使用plus<>类来完成常规的相加运算。

#include<functional> // 提供plus<>的声明
// ...
plus<double> add; // 声明一个plus<double>的对象
double y = add(2.2, 3.4);
transform(gr8.begin(), gr8.end(), m8.begin(), out, add);
// 或者
transform(gr8.begin(), gr8.end(), m8.begin(), out, plus<double>());
// ()是默认构造，即调用默认构造函数，创建一个匿名对象传入

C++11提供了函数指针和函数符的替代品——lambda表达式。

之前介绍过的map和priority_queue，在构造时，可以指定排序的规则，可以使用预定义的函数符。或者一些排序算法，例如sort也会用到。

以优先队列和map为例：

priority_queue<int> pq; // 默认大根堆, 即每次取出的元素是队列中的最大值
priority_queue<int, greater<int> > q; // 小根堆, 每次取出的元素是队列中的最小值

//创建空 map 容器，默认根据个键值对中键的值，对键值对做降序排序
map<string, string, greater<string> > myMap;

以排序为例：

#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
using namespace std;

int main(void) {
    int arr[5] = {5, 4, 3, 2, 1};
    vector<int> v(arr, arr + 5);
    sort(v.begin(), v.end(), less<int>()); // 升序排列
    vector<int>::iterator iter;
    for(iter = v.begin(); iter != v.end(); iter++) {
        cout << *iter << " ";
    }
    return 0;
}

C++标准模板库学习笔记

C++标准模板库学习笔记

0 STL简介

0.1 概述

0.2 STL组成

1 string类

1.1 构造字符串

1.2 string类输入

1.3 使用字符串

1.3.1 比较字符串

1.3.2 字符串长度

1.3.3 搜索子串和字符

1.3.4 求子串

1.4 字符串种类

2 智能指针模板类

3 标准模板库

3.1 模板类vector

3.2 可对vector执行的操作

3.3 其他操作

3.4 基于范围的for循环

4 泛型编程

4.1 迭代器的必要性

4.2 迭代器类型

4.2.1 输入迭代器

4.2.2 输出迭代器

4.2.3 正向迭代器

4.2.4 双向迭代器

4.2.5 随机访问迭代器

4.3 迭代器层次结构

4.4 概念、改进和类型

4.4.1 预定义迭代器类型

4.4.2 容器适配器

4.5 容器种类

4.5.1 基本容器

4.5.2 序列容器

① vector

② deque

③ list

④ forward_list

⑤ queue

⑥ priority_queue

⑦ stack

⑧ array

4.5.3 关联容器

① pair

② map

③ set

4.5.4 无序关联容器

① unordered_map

② unordered_set

5 函数对象

5.1 简介

5.2 函数符概念

5.3 预定义的函数符

6 算法