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

学习时间：2023年1月9日

参考资料：

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相关的头文件：

image-20230109124542162

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

1 string类

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

1.1 构造字符串

以下是string类的构造函数：

image-20230109130723806

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

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

程序实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 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"。

image-20230114112338238

现在假设要用这个构造函数将对象初始化为另一个 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风格字符串进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
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类提供了四个重载函数：

1
2
3
4
5
6
7
8
9
10
// 从字符串的 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;

代码示例

1
2
3
4
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类实际上是基于一个模板类的：

1
2
3
4
5
template<class charT, class traits = char _traits<charT>,
	class Allocator = allocator<charT> >
basic_string {
	// ...
};
1
2
3
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

1.5 相关方法

① 长度
代码 含义
s.size()和s.length() 返回string对象的字符个数，他们执行效果相同。
② 插入
代码 含义
s.push_back() 在末尾插入
例：s.push_back('a') 末尾插入一个字符a
s.insert(pos,element) 在pos位置插入element
例：s.insert(s.begin(),'1') 在第一个位置插入1字符
s.append(str) 在s字符串结尾添加str字符串
例：s.append("abc") 在s字符串末尾添加字符串“abc”
③ 删除
代码 含义
erase(iterator p) 删除字符串中p所指的字符
erase(iterator first, iterator last) 删除字符串中迭代器区间[first,last)上所有字符
erase(pos, len) 删除字符串中从索引位置pos开始的len个字符
clear() 删除字符串中所有字符
④ 字符替换
代码 含义
s.replace(pos,n,str) 把当前字符串从索引pos开始的n个字符替换为str
s.replace(pos,n,n1,c) 把当前字符串从索引pos开始的n个字符替换为n1个字符c
s.replace(it1,it2,str) 把当前字符串[it1,it2)区间替换为str
⑤ 大小写转换
代码 含义
tolower(s[i]) 转换为小写
toupper(s[i]) 转换为大写
⑥ 分割
代码 含义
s.substr(pos,n) 截取从pos索引开始的n个字符
⑦ 查找

略

2 智能指针模板类

暂略

3 标准模板库

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

3.1 模板类vector

矢量vector对应于数组。

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

1
2
3
4
5
#include <vector>
vector<int> ratings(5);
int n;
cin >> n;
vector<double> scores(n);

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

1
2
3
4
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的位置

1
2
3
4
5
6
7
for(pd = scores.begin(); pd != scores.end(); pd++) {
    cout << *pd << endl;
}
// 或者
for(pd = scores.begin(); pd < scores.end(); pd++) {
    cout << *pd << endl;
}

image-20230114125902278

特有方法

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

  • push_back()：将元素添加进矢量末尾。它将负责动态内存管理，当矢量内存不够时，将自动扩容
1
2
3
4
5
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()：接收三个迭代器，第一个指定新元素的插入位置，第二三个指定插入区间，左闭右开
1
2
3
4
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()：接收三个参数，前两个是定义容器中区间的迭代器，最后一个是指向函数的指针（准确来说是函数对象）。它将被指向的函数应用于容器区间中的各个元素，函数不能修改容器元素的值。
1
2
3
4
// 函数原型
template<typename _InputIterator, typename _Function>
_Function
for_each(_InputIterator __first, _InputIterator __last, _Function __f);

使用：

1
2
3
4
5
6
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<()函数进行重载

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      // 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());

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

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      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：

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

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

1
2
3
4
5
6
7
8
9
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数组中搜索特定值
1
2
3
4
5
6
7
8
9
// 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;
}

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

  • 在一个链表中搜索特定值
1
2
3
4
struct Node {
    double item;
    Node * p_next;
};
1
2
3
4
5
6
7
8
9
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函数可以修改为：
1
2
3
4
5
6
7
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版本完成了这些修改：

1
2
3
4
5
6
7
8
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，其中重载了*和++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
    }
    // ...
};

于是函数可以修改为：

1
2
3
4
5
6
7
8
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返回一个指向超尾位置的迭代器即可。

例如：

1
2
3
4
5
6
7
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新增的自动类型推断可进一步简化：对于矢量或列表，都可使用如下代码：

1
2
3
4
5
6
7
// 省去了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为随机迭代器变量或引用。

image-20230114151713252

4.3 迭代器层次结构

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

image-20230114151901626

提供多种迭代器的必要性

目的是为了在编写算法尽可能使用要求最低的迭代器，并让它适用于容器的最大区间。这样，通过使用级别最低的输入迭代器，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 迭代器名;

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

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

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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 基本的容器特征

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

  • X表示容器类型，如 vector；
  • T表示存储在容器中的对象类型，例如基本数据类型，结构体，自定义类等等；
  • a和b表示类型为X的值；
  • r表示类型为X&的值；
  • u表示类型为X的标识符（即如果X表示 vector<int>，则u是一个vector<int>对象）。

image-20230114153204223

4.5.1 获取迭代器

代码 含义
X::iterator 迭代器

4.5.2 创建和初始化

代码 含义
X u; 创建一个名为u的空容器
X (); 创建一个匿名的空容器
X u(a); 调用复制构造函数后u == a
a.begin() 返回指向第一个元素的迭代器
a.end() 返回超尾迭代器
a.size() 返回元素个数，等于a.end()-a.begin()
a.swap(b) 交换a和b的内容

4.6 序列容器

4.6.1 通用操作

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

序列要求：

  • 迭代器至少是正向迭代器（正向、双向或随机的一种）
  • 容器元素按严格的线性顺序排列（有前驱和后继）
① 创建和初始化
代码 含义
X a(n, t); 声明一个名为a的由n个t值组成的序列
X (n, t) 匿名序列
X a(iter1, iter2) 声明一个名为a的序列，并初始化区间[iter1, iter2)的内容
② 插入
代码 含义
a.insert(iter, t) 将t插入到iter前面，并返回表示新插入元素位置的迭代器。
a.insert(iter, n ,t) 将n个t插入到iter前面，并返回表示第一个新插入元素位置的迭代器。
a.insert(iter, iter1, iter2) 将区间[iter1, iter2)插入到iter前面，并返回表示第一个新插入元素位置的迭代器。
③ 删除
代码 含义
a.erase(iter) 删除iter指向的元素
a.erase(iter1, iter2) 删除区间[iter1, iter2)的元素
a.clear() 等价于a.erase(a.begin(), a.end())
④ 判空
代码 含义
a.empty() 判断是否为空，空则返回真

4.6.2 特殊操作

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

① 首尾元素
代码 返回类型 含义 支持容器
a.front() T& 返回头元素 vector，list，deque
a.back() T& 返回尾元素 vector，list，deque
② 首尾增加和删除
代码 返回类型 支持容器
a.push_front() void list，deque
a.push_back() void vector，list，deque
a.pop_front() void list，deque
a.pop_back() void vector，list，deque
③ 随机访问
代码 返回类型 支持容器
a[n] T& vector，deque
a.at[n] T& vector，deque

总结：

image-20230114154120007

4.6.3 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); // 反向显示

创建和初始化

  • 一维初始化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> a; //定义了一个名为a的一维数组,数组存储int类型数据
vector<double> b;//定义了一个名为b的一维数组，数组存储double类型数据
vector<node> c;//定义了一个名为c的一维数组，数组存储结构体类型数据，node是结构体类型

vector<int> v(n);//定义一个长度为n的数组，初始值默认为0，下标范围[0, n - 1]
vector<int> v(n, 1);//v[0]到v[n-1]所有的元素初始值均为1
//注意：指定数组长度之后（指定长度后的数组就相当于正常的数组了）

vector<int> a(n + 1, 0);
vector<int> b(a);//两个数组中的类型必须相同,a和b都是长度为n+1，初始值都为0的数组

//-------以上均为通用操作

vector<int> a{1, 2, 3, 4, 5}; // 列表初始化
  • 二维初始化
1
2
3
4
5
6
7
8
9
10
11
//初始化二维均可变长数组
vector<vector<int>> v;//定义一个行和列均可变的二维数组

vector<int> t1{1, 2, 3, 4};
vector<int> t2{2, 3, 4, 5};
v.push_back(t1);
v.push_back(t2);
v.push_back({3, 4, 5, 6}); // {3, 4, 5, 6}可以作为vector的初始化,相当于一个无名vector

// n行m列
vector<vector<int> > a(n, vector<int>(m, 0));

4.6.4 deque

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

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

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

4.6.5 list

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

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

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

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

image-20230114155700147

4.6.6 forward_list

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

4.6.7 queue

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

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

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

image-20230114160513159

代码 含义
q.front() 返回队首元素 O(1)
q.back() 返回队尾元素 O(1)
q.push(element) 尾部添加一个元素element 进队O(1)
q.pop() 删除第一个元素 出队 O(1)
q.size() 返回队列中元素个数，返回值类型unsigned int O(1)
q.empty() 判断是否为空，队列为空，返回true O(1)

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

代码示例

  • 创建一个空的 queue 容器适配器，其底层使用的基础容器选择默认的 deque 容器：
1
2
3
queue<int> values;
// 相当于调用默认构造器
queue<int> values = queue<int>();
  • 也可以手动指定 queue 容器适配器底层采用的基础容器类型。
1
queue<int, list<int>> values;
  • 可以用基础容器来初始化 queue 容器适配器，只要该容器类型和 queue 底层使用的基础容器类型相同即可。
1
2
deque<int> values{1,2,3};
queue<int> my_queue(values);
  • 使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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;
}

执行结果：

1
2
3
4
size of my_queue: 3
1
2
3

4.6.8 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()访问队首元素（优先级最高的元素）

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
}

打印结果：

1
4 3 2 1

设置优先级

  • 基本数据类型优先级
1
2
priority_queue<int> pq; // 默认大根堆, 即每次取出的元素是队列中的最大值
priority_queue<int, vector<int>, greater<int> > q; // 小根堆, 每次取出的元素是队列中的最小值
  • 结构体优先级
1
2
3
4
//要排序的结构体（存储在优先队列里面的）
struct Point {
    int x,y;
};
1
2
3
4
5
6
7
8
9
10
11
//定义的比较结构体
//注意：cmp是个结构体 
struct cmp { //自定义堆的排序规则 
    // 重载()运算符
    bool operator()(const Point& a,const Point& b) {
        return a.x < b.x;
    }
};

//初始化定义
priority_queue<Point, vector<Point>, cmp> q; // x大的在堆顶
  • pair类型优先级

默认排序规则：默认先对pair的first进行降序排序，然后再对second降序排序；对first先排序，大的排在前面，如果first元素相同，再对second元素排序，保持大的在前面。

4.6.9 stack

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

支持的操作如下：

image-20230115111322921

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

初始化

1
2
3
4
5
6
7
//头文件需要添加
#include<stack>

//声明
stack<int> s;
stack<string> s;
stack<node> s;//node是结构体类型

方法

代码 含义
s.push(ele) 元素ele入栈，增加元素 O(1)
s.pop() 移除栈顶元素 O(1)
s.top() 取得栈顶元素（但不删除）O(1)
s.empty() 检测栈内是否为空，空为真 O(1)
s.size() 返回栈内元素的个数 O(1)

访问

遍历只能一个个退栈。

4.6.10 array

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

4.7 关联容器

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

关联容器带有模板参数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 容器中存储元素的值可以重复（一旦值重复，则意味着键也是重复的）。

4.7.1 pair

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

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

1
2
p.first;
p.second;

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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;
}

执行结果：

1
2
3
4
5
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/

4.7.2 map

map会按照键的顺序从小到大自动排序，键的类型必须可以比较大小。

函数方法：

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

查找元素是否存在时，可以使用①mp.find() ② mp.count() ③ mp[key]

但是第三种情况，如果不存在对应的key时，会自动创建一个键值对（产生一个额外的键值对空间）
所以为了不增加额外的空间负担，最好使用前两种方法。

添加元素

1
2
3
4
5
6
7
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});

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
map<int,int> mp;
mp[1] = 2;
mp[2] = 3;
mp[3] = 4;
auto it = mp.begin();
while(it != mp.end()) {
    cout << it->first << " " << it->second << "\n";
    it ++;
}

for(auto i : mp)
cout << i.first << " " << i.second << endl;//键，值

map<string,string>::iterator it;
for(it = mp.begin(); it != mp.end(); it++) {
    //      键                 值 
    // it是结构体指针访问所以要用 -> 访问
    cout << it->first << " " << it->second << "\n";
    //*it是结构体变量 访问要用 . 访问
    //cout<<(*it).first<<" "<<(*it).second;
}

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <map>      // map
#include <string>       // string
using namespace std;
int main() {
    //创建空 map 容器，默认根据个键值对中键的值，对键值对做降序排序
    map<string, string, greater<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;
}

打印结果：

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

4.7.3 set

set容器中的元素不会重复，当插入集合中已有的元素时，并不会插入进去，而且set容器里的元素自动从小到大排序。

函数方法：和map一样。

4.8 无序关联容器

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

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

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 唯一的区别在于，该容器允许存储值相同的元素。

4.8.1 unordered_map

在<unordered_map>中声明。正向迭代器。

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

常用方法：同map

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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;
}

打印结果：

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

4.8.2 unordered_set

略

5 函数对象

5.1 简介

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

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

1
2
3
4
5
6
7
8
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的对象（用函数的方式使用对象）：

1
2
3
4
5
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 &)。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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个参数：

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

5.3 预定义的函数符

引入

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

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

1
2
3
4
5
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函数。

image-20230115144724308

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

1
2
3
4
5
6
7
8
#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为例：

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

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

以排序为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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;
}

5.4 Lambda表达式

5.4.1 定义

① 例子
1
2
3
4
5
6
7
8
9
10
11
#include <algorithm>
#include <cmath>

void abssort(float* x, unsigned n) {
    std::sort(x, x + n,
        // Lambda expression begins
        [](float a, float b) {
            return (std::abs(a) < std::abs(b));
        } // end of lambda expression
    );
}

在上面的实例中std::sort函数第三个参数应该是传递一个排序规则的函数，但是这个实例中直接将排序函数的实现写在应该传递函数的位置，省去了定义排序函数的过程，对于这种不需要复用，且短小的函数，直接传递函数体可以增加代码的可读性。

② 语法

img

  1. 捕获列表。在C++规范中也称为Lambda导入器， 捕获列表总是出现在Lambda函数的开始处。实际上，[]是Lambda引出符。编译器根据该引出符判断接下来的代码是否是Lambda函数，捕获列表能够捕捉上下文中的变量以供Lambda函数使用。
  2. 参数列表。与普通函数的参数列表一致。如果不需要参数传递，则可以连同括号()一起省略。
  3. 可变规格。mutable修饰符， 默认情况下Lambda函数总是一个const函数，mutable可以取消其常量性。在使用该修饰符时，参数列表不可省略（即使参数为空）。
  4. 异常说明。用于Lamdba表达式内部函数抛出异常。
  5. 返回类型。 追踪返回类型形式声明函数的返回类型。我们可以在不需要返回值的时候也可以连同符号->一起省略。此外，在返回类型明确的情况下，也可以省略该部分，让编译器对返回类型进行推导。
  6. lambda函数体。内容与普通函数一样，不过除了可以使用参数之外，还可以使用所有捕获的变量。
③ 参数详解

捕获列表

Lambda表达式与普通函数最大的区别是，除了可以使用参数以外，Lambda函数还可以通过捕获列表访问一些上下文中的数据。具体地，捕捉列表描述了上下文中哪些数据可以被Lambda使用，以及使用方式（以值传递的方式或引用传递的方式）。语法上，在“[]”包括起来的是捕获列表，捕获列表由多个捕获项组成，并以逗号分隔。捕获列表有以下几种形式：

  • []表示不捕获任何变量
1
2
3
4
5
6
auto function = ([]{
		std::cout << "Hello World!" << std::endl;
	}
);

function();
  • [var]表示值传递方式捕获变量var
1
2
3
4
5
6
7
int num = 100;
auto function = ([num]{
		std::cout << num << std::endl;
	}
);

function();
  • [=]表示值传递方式捕获所有父作用域的变量（包括this）
1
2
3
4
5
6
7
8
9
int index = 1;
int num = 100;
auto function = ([=]{
			std::cout << "index: "<< index << ", " 
                << "num: "<< num << std::endl;
	}
);

function();
  • [&var]表示引用传递捕捉变量var
1
2
3
4
5
6
7
int num = 100;
auto function = ([&num]{
		num = 1000;
		std::cout << "num: " << num << std::endl;
	}
);
function();
  • [&]表示引用传递方式捕捉所有父作用域的变量（包括this）
1
2
3
4
5
6
7
8
9
10
11
int index = 1;
int num = 100;
auto function = ([&]{
		num = 1000;
		index = 2;
		std::cout << "index: "<< index << ", " 
            << "num: "<< num << std::endl;
	}
);

function();
  • [this]表示值传递方式捕捉当前的this指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
 
class Lambda
{
public:
    void sayHello() {
        std::cout << "Hello" << std::endl;
    };

    void lambda() {
        auto function = [this]{ 
            this->sayHello(); 
        };

        function();
    }
};
 
int main()
{
    Lambda demo;
    demo.lambda();
}
  • [=, &]拷贝与引用混合
    • [=, &a, &b]表示以引用传递的方式捕捉变量a和b，以值传递方式捕捉其它所有变量。
1
2
3
4
5
6
7
8
9
10
11
int index = 1;
int num = 100;
auto function = ([=, &index, &num]{
		num = 1000;
		index = 2;
		std::cout << "index: "<< index << ", " 
            << "num: "<< num << std::endl;
	}
);

function();
  • [&, a, this]表示以值传递的方式捕捉变量a和this，引用传递方式捕捉其它所有变量。

不过值得注意的是，捕捉列表不允许变量重复传递。下面一些例子就是典型的重复，会导致编译时期的错误。例如：

  • [=,a]这里已经以值传递方式捕捉了所有变量，但是重复捕捉a了，会报错的；
  • [&,&this]这里&已经以引用传递方式捕捉了所有变量，再捕捉this也是一种重复。

如果Lambda主体total通过引用访问外部变量，并factor通过值访问外部变量，则以下捕获子句是等效的：

1
2
3
4
5
6
[&total, factor]
[factor, &total]
[&, factor]
[factor, &]
[=, &total]
[&total, =]

参数列表

除了捕获列表之外，Lambda还可以接受输入参数。参数列表是可选的，并且在大多数方面类似于函数的参数列表。

1
2
3
4
5
auto function = [](int first, int second)->{
    return first + second;
};

function(100, 200);

可变规格mutable

mutable修饰符， 默认情况下Lambda函数总是一个const函数，mutable可以取消其常量性。在使用该修饰符时，参数列表不可省略（即使参数为空）。

1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;

int main() {
   int m = 0;
   int n = 0;
   [&, n] (int a) mutable { m = ++n + a; }(4);
   cout << m << endl << n << endl;
}

返回类型

Lambda表达式的返回类型会自动推导。除非你指定了返回类型，否则不必使用关键字。返回型类似于通常的方法或函数的返回型部分。但是，返回类型必须在参数列表之后，并且必须在返回类型->之前包含类型关键字。如果Lambda主体仅包含一个return语句或该表达式未返回值，则可以省略Lambda表达式的return-type部分。如果Lambda主体包含一个return语句，则编译器将从return表达式的类型中推断出return类型。否则，编译器将返回类型推导为void。

1
auto x1 = [](int i){ return i; };

函数体

Lambda表达式的Lambda主体（标准语法中的复合语句）可以包含普通方法或函数的主体可以包含的任何内容。普通函数和Lambda表达式的主体都可以访问以下类型的变量：

  • 捕获变量
  • 形参变量
  • 局部声明的变量
  • 类数据成员，当在类内声明this并被捕获时
  • 具有静态存储持续时间的任何变量，例如全局变量
1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;

int main() {
   int m = 0;
   int n = 0;
   [&, n] (int a) mutable { m = ++n + a; }(4);
   cout << m << endl << n << endl;
}

5.4.2 工作原理

编译器会把一个Lambda表达式生成一个匿名类的匿名对象，并在类中重载函数调用运算符，实现了一个operator()方法。

1
auto print = []{cout << "Hello World!" << endl; };

编译器会把上面这一句翻译为下面的代码：

1
2
3
4
5
6
7
8
9
class print_class {
public:
    // 重载()运算符
	void operator()(void) const {
		cout << "Hello World!" << endl;
	}
};
// 用构造的类创建对象，print此时就是一个函数对象
auto print = print_class();

5.4.3 使用场景

for_each应用实例

1
2
int a[4] = {11, 2, 33, 4};
for_each(a, a+4, [=](int x) { cout << x << " ";} );

sort函数

1
2
3
4
5
6
7
8
9
10
11
12
int main(void) {
    int data[6] = { 3, 4, 12, 2, 1, 6 };
    vector<int> testdata;
    testdata.insert(testdata.begin(), data, data + 6);

    // 对于比较大小的逻辑，使用lamdba不需要在重新定义一个函数
    sort(testdata.begin(), testdata.end(), [](int a, int b){ 
        return a > b; 
    });

    return 0;
}

6 算法

STL 包含很多处理容器的非成员函数，前面已经介绍过其中的一些：sort、copy、find、random_shuffle、set_union、set_intersection、set_difference和transform。可能已经注意到，它们的总体设计是相同的，都使用迭代器来标识要处理的数据区间和结果的放置位置。有些函数还接受一个函数对象参数，并使用它来处理数据。

6.1 算法组

STL将算法库分成4组：

  • 非修改式序列操作；
  • 修改式序列操作；
  • 排序和相关操作；
  • 通用数字运算。

前三组在头文件<algorithm>，第四组在头文件<numeric>中。

6.2 排序

STL排序函数如下表：

函数名 用法
sort (first, last) 对容器或普通数组中 [first, last) 范围内的元素进行排序，默认进行升序排序。
stable_sort (first, last) 和 sort() 函数功能相似，不同之处在于，对于 [first, last) 范围内值相同的元素，该函数不会改变它们的相对位置。
partial_sort (first, middle, last) 从 [first,last) 范围内，筛选出 muddle-first 个最小的元素并排序存放在 [first，middle) 区间中。
partial_sort_copy (first, last, result_first, result_last) 从 [first, last) 范围内筛选出 result_last-result_first 个元素排序并存储到 [result_first, result_last) 指定的范围中。
is_sorted (first, last) 检测 [first, last) 范围内是否已经排好序，默认检测是否按升序排序。
is_sorted_until (first, last) 和 is_sorted() 函数功能类似，唯一的区别在于，如果 [first, last) 范围的元素没有排好序，则该函数会返回一个指向首个不遵循排序规则的元素的迭代器。
void nth_element (first, nth, last) 找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

6.2.1 sort

sort函数是基于快速排序实现的。默认按照升序排序（std::less<T>），且可能会改变相同元素的位置。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream> 
#include <algorithm>
#include <vector>
using namespace std;
// 以普通函数的方式实现自定义排序规则
bool mycomp(int i, int j) {
    return (i < j);
}

// 以函数对象的方式实现自定义排序规则
class mycomp2 {
public:
    // 提供对()的重载
    bool operator() (int i, int j) {
        return (i < j);
    }
};

int main() {
    vector<int> myvector{ 32, 71, 12, 45, 26, 80, 53, 33 };
    //调用第一种语法格式，对 32、71、12、45 进行排序
    sort(myvector.begin(), myvector.begin() + 4);
    
    //调用第二种语法格式，利用STL标准库提供的其它比较规则（比如 greater<T>）进行排序，降序
    sort(myvector.begin(), myvector.begin() + 4, greater<int>()); 
   
    //调用第二种语法格式，通过自定义比较规则（函数对象）进行排序
    sort(myvector.begin(), myvector.end(), mycomp2());
    
    //调用第二种语法格式，通过自定义比较规则（函数指针）进行排序
    sort(myvector.begin(), myvector.end(), mycomp);
    
    //输出 myvector 容器中的元素
    for (vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) {
        cout << *it << ' ';
    }
    return 0;
}

6.2.2 stable_sort

stable_sort函数基于归并排序实现，不会改变相同元素的相对位置。

使用和sort相同。

6.2.3 is_sorted

此函数专门用于判断某个序列是否为有序序列。默认判断升序，返回布尔值。

使用和sort相同。

6.2.4 merge

merge函数用于将 2 个有序序列合并为 1 个有序序列，前提是这 2 个有序序列的排序规则相同（要么都是升序，要么都是降序）。并且最终借助该函数获得的新有序序列，其排序规则也和这 2 个有序序列相同。

语法格式

1
2
3
4
5
6
7
8
//以默认的升序排序作为排序规则
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result);
//以自定义的 comp 规则作为排序规则
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      OutputIterator result, Compare comp);

result 为输出迭代器，用于为最终生成的新有序序列指定存储位置；

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>  
#include <vector> 
using namespace std;
int main() {
    //first 和 second 数组中各存有 1 个有序序列
    int first[] = { 5,10,15,20,25 };
    int second[] = { 7,17,27,37,47,57 };
    //用于存储新的有序序列
    vector<int> myvector(11);
    //将 [first,first+5) 和 [second,second+6) 合并为 1 个有序序列，并存储到 myvector 容器中。
    merge(first, first + 5, second, second + 6, myvector.begin());
    //输出 myvector 容器中存储的元素
    for (vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) {
        cout << *it << ' ';
    }   
    return 0;
}

输出结果：

1
5 7 10 15 17 20 25 27 37 47 57

6.3 查找

6.3.1 find

find用于在指定范围内查找和目标元素值相等的第一个元素。底层采用顺序查找的方式。

函数原型：

1
InputIterator find (InputIterator first, InputIterator last, const T& val);

该函数会返回一个输入迭代器，当 find() 函数查找成功时，其指向的是在 [first, last) 区域内查找到的第一个目标元素；如果查找失败，则该迭代器的指向和 last 相同。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    //find() 函数作用于普通数组
    char stl[] ="http://c.biancheng.net/stl/";
    //调用 find() 查找第一个字符 'c'
        char * p = find(stl, stl + strlen(stl), 'c');
    //判断是否查找成功
    if (p != stl + strlen(stl)) {
        cout << p << endl;
    }
    //find() 函数作用于容器
    vector<int> myvector{ 10,20,30,40,50 };
    vector<int>::iterator it;
    it = find(myvector.begin(), myvector.end(), 30);
    if (it != myvector.end())
        cout << "查找成功：" << *it;
    else
        cout << "查找失败";
    return 0;
}

6.3.2 lower_bound

底层采用二分查找。只能用于有序序列。复杂度：

lower_bound 函数用于在指定区域内查找不小于目标值的第一个元素。

1
2
3
4
//在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

6.3.3 upper_bound

upper_bound 函数用于在指定范围内查找大于目标值的第一个元素。