STL Tutorial Note

CJC From NJU wrote a C++ STL Tutorial. This is a perfect learning material for STL beginners to get familiar with C++ STL. Hope this note can help you learn the material!

概述

STL包含什么？

STL是一个基于模版实现的标准模板库，包含容器类模版、算法模版和迭代器模版。

其中迭代器是指向容器的元素，是容器和算法之间的桥梁。

容器(Container)

vector<元素类型>

快速访问任意位置的元素，主要在元素序列的尾部增加/删除元素

用动态数组实现

list<元素类型>

在元素序列中任意位置上插入/删除元素

用双向链表实现

C++11中增加了forward_list容器，本质上是一个单向链表，定义在头文件forward_list中。

deque<元素类型>

在元素序列的两端增加/删除元素，快速访问任意位置的元素

用分段的连续空间结构实现

stack<元素类型>

仅在元素序列的尾部增加/删除元素

可基于deque、list或vector来实现

queue<元素类型>

仅在元素序列的尾部增加、头部删除元素

可基于deque和list来实现。

priority_queue<元素类型>

每次增加/删除元素之后，对元素位置进行调整，使得头部元素总是最大的。也就是说，每次删除操作总是从头部把最大（优先级最高）的元素去掉。

可基于deque和vector来实现

map<key，value> 和 multimap<key，value>

根据key来访问元素，容器中每个元素是一个pair<key, value>结构

对于map，不同元素的关键字不能相同；对于multimap，不同元素的关键字可以相同。

常用某种二叉树来实现

有时候我们不需要排序，所以C++11中新增加了unordered_map

和unordered_multimap容器。

set<元素类型> 和 multiset<元素类型>

它们分别是map和multimap的特例，每个元素只有key而没有value

C++11中增加了unordered_set和unordered_multiset容器。

basic_string<字符类型>

与vector类似，不同之处在于其元素为字符类型

string和wstring分别是它的两个实例：

basic_string<char>
basic_string<wchar_t>

迭代器(Iterator)

迭代器的分类（五种基本迭代器）

根据访问修改权限分类：

输出迭代器（output iterator，记为：OutIt）：修改它所指向的容器元素
输入迭代器（input iterator，记为：InIt）：读取它所指向的容器元素

根据迭代方式分类：

前向迭代器（forward iterator，记为：FwdIt）
双向迭代器（bidirectional iterator，记为：BidIt）
随机访问迭代器（random-access iterator，记为：RanIt）

对于vector、deque以及basic_string容器类，与它们关联的迭代器类型为随机访问迭代器（RanIt）

对于list、map/multimap以及set/multiset容器类，与它们关联的迭代器类型为双向迭代器（BidIt）

queue、stack和priority_queue容器类，不支持迭代器！

在需要箭头左边迭代器的地方可以用箭头右边的迭代器去替代。

反向迭代器（reverse iterator）

用于对容器元素从尾到头进行反向遍历，可以通过容器类的成员函数rbegin和rend可以获得容器的尾和首元素的反向迭代器。

插入迭代器（insert iterator）

back_insert_iterator（用于在尾部插入元素）
front_insert_iterator（用于在首部插入元素）
insert_iterator（用于在任意指定位置插入元素）

可以分别通过函数back_inserter、front_inserter和inserter来获得，函数的参数为容器。

// 准备用于演示的容器
std::vector<int> vec;              // 用于back_inserter
std::list<int> lst;                // 用于front_inserter
std::vector<int> middle_vec{10, 20, 30, 40, 50};  // 用于inserter

// 1. back_insert_iterator示例
// 将source中的元素复制到vec的末尾
std::copy(source.begin(), source.end(), std::back_inserter(vec));

// 2. front_insert_iterator示例
// 将source中的元素复制到lst的开头
// 注意：front_inserter只能用于支持push_front的容器（如list）
std::copy(source.begin(), source.end(), std::front_inserter(lst));

// 3. insert_iterator示例
// 将source中的元素插入到middle_vec的中间位置
auto insert_pos = middle_vec.begin() + 2;  // 在30前面插入
std::copy(source.begin(), source.end(), std::inserter(middle_vec, insert_pos));

使用迭代器求解约瑟夫问题

N 个人围成一圈，从第 1 个人开始报数，每报到第 M 个人就让他出列并从下一个人重新开始报数，直到所有人都出列为止。问最后一个出列的人是原来的第几号。

int m,n; // m用于存储要报的数，n用于存储小孩个数
cout << "请输入小孩的个数和要报的数：";
cin >> n >> m;
// 构建圈子
list<int> children; // children是用于存储小孩编号的容器
for (int i=0; i<n; i++) // 循环创建容器元素
    children.push_back(i); // 把i（小孩的编号）从容器尾部放入容器
// 开始报数
list<int>::iterator current; // current为指向容器元素的迭代器
current = children.begin(); // current初始化成指向容器的第一个元素
while (children.size() > 1) // 只要容器元素个数大于1，就执行循环
{
    for (int count = 1; count < m; count++)  //报数，循环m-1次
    {
        current++; //current指向下一个元素
        // 如果current指向的是容器末尾，current指向第一个元素
        if (current == children.end()) current = children.begin();
    }
    // 循环结束时，current指向将要离开圈子的小孩
    current = children.erase(current);  // 小孩离开圈子，current指向下一个元素
    // 如果current指向的是容器末尾，current指向第一个元素
    if (current == children.end()) current = children.begin();
} // 循环结束时，current指向容器中剩下的唯一的一个元素，即胜利者
// 输出胜利者的编号
cout << "The winner is No." << *current << "\n";

算法(Algorithm)

在STL中，我们把某些迭代器传递给算法，算法通过迭代器来访问和遍历相应容器中的元素。

用算法对容器中的元素进行操作时，大都需要用两个迭代器来指出要操作的元素的范围。

例如：

1	`void sort(RanIt first, RanIt last);`

有些算法可以有多个操作范围，这时，除第一个范围外，其它范围可以不指定最后一个元素位置，它由第一个范围中元素的个数决定。例如：

1	`OutIt copy(InIt src_first, InIt src_last, OutIt dst_first);`

算法的自定义操作

自定义操作可分为：

Op或Fun：一元操作，需要一个参数

例如：

Fun for_each(InIt first, InIt last, Fun f);

void f(int x) { cout << ' ' << x; }

vector<int> v;
...... // 往容器中放了元素
for_each(v.begin(), v.end(), f); // 对v中的每个元素去调用函数f进行操作

BinOp或BinFun：二元操作，需要两个参数

例如，对于下面的元素“变换/映射”算法:

OutIt transform(InIt src_first, InIt src_last, OutIt dst_first, Op f);
OutIt transform(InIt1 src_first1, InIt1 src_last1, InIt2 src_first2, OutIt dst_first, BinOp f);

int f1(int x) { return x * x; }
int f2(int x1, int x2) { return x1 + x2; }

vector<int> v1,v2,v3,v4;
...... // 往v1和v2容器中放了元素

transform(v1.begin(),v1.end(),v3.begin(),f1); 
// v3中的元素是v1相应元素的平方

transform(v1.begin(),v1.end(),v2.begin(),v4.begin(),f2); 
// v4中的元素是v1和v2相应元素的和

仿函数(Functor)

这里稍微拓展一下**仿函数(Functor)**的使用，在后续会有详细的介绍。

仿函数，也可以叫作函数对象

利用仿函数实现算法的自定义操作：

定义函数对象类如下：

class MatchMajor
{
    Major major;
public:
    MatchMajor (Major m) { major = m; }
    bool operator ()(Student& st) { return st.get_major() == major; }
};

统计某某专业的人数：

count_if(students.begin(), students.end(), MatchMajor(COMPUTER))；
count_if(students.begin(), students.end(), MatchMajor(PHYSICS))；

// 统计XXX专业的人数
count_if(students.begin(), students.end(), MatchMajor(XXX))；

匿名函数(lambda表达式)

https://www.runoob.com/cplusplus/cpp-functions.html

Lambda表达式可以看作一个函数对象

Lambda 表达式具体形式如下:

1	`[capture](parameters)->return-type{body}`

例如：

1	`[](int x, int y){ return x < y ; }`

如果没有返回值可以表示为：

1	`[capture](parameters){body}`

例如：

1	`[]{ ++global_x; }`

在一个更为复杂的例子中，返回类型可以被明确的指定如下：

1	`[](int x, int y) -> int { int z = x + y; return z + x; }`

在Lambda表达式内可以访问当前作用域的变量，这是Lambda表达式的闭包（Closure）行为。与JavaScript闭包不同，C++变量传递有传值和传引用的区别。可以通过前面的[]来指定：

[]      // 沒有定义任何变量。使用未定义变量会引发错误。
[x, &y] // x以传值方式传入（默认），y以引用方式传入。
[&]     // 任何被使用到的外部变量都隐式地以引用方式加以引用。
[=]     // 任何被使用到的外部变量都隐式地以传值方式加以引用。
[&, x]  // x显式地以传值方式加以引用。其余变量以引用方式加以引用。
[=, &z] // z显式地以引用方式加以引用。其余变量以传值方式加以引用。

需要注意的是，[]是空捕获列表的lambda表达式是不能访问外部非静态的局部变量的，但是可以访问全局变量和静态的局部变量，因为他们的生命周期覆盖整个程序运行期间

利用lambda表达式实现算法的自定义操作：

//统计“计算机专业女生”的人数	
cout << "计算机专业女生的人数是：" 
      << count_if(students.begin(),students.end(),
        [](Student &st) { return (st.get_major() == COMPUTER)
			     && (st.get_sex() == FEMALE); });

//按“学号由小到大”对students的元素进行排序
sort(students.begin(),students.end(),
		[](Student &st1,Student &st2) {  
                                 return  st1.get_no()<st2.get_no();});

最后

这里附上微软的C++文档pdf链接：

https://box.nju.edu.cn/f/c19cd234d4a94fd2b458/

后续将会介绍各种常用STL的用法。熟悉这些常见的STL用法+查文档是C++开发的基本要求。

容器(Container)

选择容器

容器分为序列容器和容器适配器。

选择序列容器：

选择容器适配器：

字符串(string)

string本质上是一个动态char数组

常用API

string构造函数

string();
// 默认构造函数，创建一个空的字符串
string(const string& str);
// 拷贝构造函数，使用一个string对象初始化另一个string对象
string(const char* s);
// 含参构造函数，使用C风格字符串初始化
string(int n, char c);
// p含参构造函数，使用n个字符c初始化

赋值操作

=赋值操作符:

string& operator=(const char* s);
// C风格字符串赋值给当前的字符串
string& operator=(const string& s);
// 把字符串s赋给当前的字符串
string& operator=(const char c);
//字符赋值给当前的字符串

assign成员函数:

string& assign(const char* s); 
// C风格字符串赋值给当前的字符串
string& assign(const char* s, int n); 
// 把C风格字符串s的前n个字符赋给当前的字符串
string& assign(const string& s); 
// 把字符串s赋给当前字符串
string& assign(int n, char c); 
// 把n个字符c赋给当前的字符串
string& assign(const string& s, int start, int n); 
// 将字符串s中从start开始的n个字符赋值给当前字符串

string存取字符操作

下标获取操作符：

1 2	`char& operator[](int n); // 通过[]下标方式获取字符`

使用下标操作符获取字符时，如果下标越界，程序将会强制终止。

at成员函数：

1 2	`char& at(int n); // 通过at方法获取字符`

使用at方法获取字符时，如果下标越界，at方法内部会抛出异常（exception），可以使用try-catch捕获并处理该异常。示例如下：

string s = "hello world";
try
{
//s[100]不会抛出异常，程序会直接挂掉
s.at(100);
}
catch (out_of_range& e) 
//如果不熟悉异常类型，可以使用多态特性， catch(exception& e)。
{
cout << e.what() << endl; 
//打印异常信息
}

string拼接操作

+=复合操作符号：

string& operator+=(const string& str); 
// 将字符串str追加到当前字符串末尾
string& operator+=(const char* str); 
// 将C风格字符数组追加到当前字符串末尾
string& operator+=(const char c); 
// 将字符c追加到当前字符串末尾
/* 上述操作重载了复合操作符+= */

append成员函数：

string& append(const char* s); 
// 把C风格字符数组s连接到当前字符串结尾
string& append(const char* s, int n); 
// 把C风格字符数组s的前n个字符连接到当前字符串结尾
string& append(const string &s); 
// 将字符串s追加到当前字符串末尾
string& append(const string&s, int pos, int n); 
// 把字符串s中从pos开始的n个字符连接到当前字符串结尾
string& append(int n, char c); 
// 在当前字符串结尾添加n个字符c

string 查找和替换

find成员函数：

int find(const string& str, int pos = 0) const; 
// 查找str在当前字符串中第一次出现的位置，从pos开始查找，pos默认为0
int find(const char* s, int n = 0) const; 
// 查找C风格字符串s在当前字符串中第一次出现的位置，从pos开始查找，pos默认为0
int find(const char* s, int pos, int n) const; 
// 从pos位置查找s的前n个字符在当前字符串中第一次出现的位置
int find(const char c, int pos = 0) const; 
// 查找字符c第一次出现的位置，从pos开始查找，pos默认为0

当查找失败时，find方法会返回-1，-1已经被封装为string的静态成员常量string::npos
1
static const size_t nops = -1;

rfind成员函数：

int rfind(const string& str, int pos = npos) const; 
// 从pos开始向左查找最后一次出现的位置，pos默认为npos
int rfind(const char* s, int pos = npos) const; 
// 查找s最后一次出现的位置，从pos开始向左查找，pos默认为npos
int rfind(const char* s, int pos, int n) const; 
// 从pos开始向左查找s的前n个字符最后一次出现的位置
int rfind(const char c, int pos = npos) const; 
// 查找字符c最后一次出现的位置

find方法通常查找字串第一次出现的位置，而rfind方法通常查找字串最后一次出现的位置。

rfind(str, pos)的实际的开始位置是pos + str.size()，即从该位置开始（不包括该位置字符）向前寻找匹配项，如果有则返回字符串位置，如果没有返回string::npos。

-1其实是size_t类的最大值，所以string::npos还可以表示“直到字符串结束”，rfind中pos的默认参数是字符串最后一个字符的后面一个位置。

replace成员函数：

string& replace(int pos, int n, const string& str); 
// 替换从pos开始n个字符为字符串s
string& replace(int pos, int n, const char* s);
// 替换从pos开始的n个字符为字符串s

string比较操作

compare成员函数：

1 2	`int compare(const string& s) const; // 与字符串s比较 int compare(const char* s) const; // 与C风格字符数组比较`

compare函数依据字典序比较，在当前字符串比给定字符串小时返回-1，在当前字符串比给定字符串大时返回1，相等时返回0。

比较操作符：

bool operator<(const string& str) const;
bool operator<(const char* str) const;
bool operator<=(const string& str) const;
bool operator<=(const char* str) const;
bool operator==(const string& str) const;
bool operator==(const char* str) const;
bool operator>(const string& str) const;
bool operator>(const char* str) const;
bool operator>=(const string& str) const;
bool operator>=(const char* str) const;
bool operator!=(const string& str) const;
bool operator!=(const char* str) const;

string类重载了所有的比较操作符，其含义与比较操作符本身的含义相同。

string子串

substr成员函数：

1 2	`string substr(int pos = 0, int n = npos) const; // 返回由pos开始的n个字符组成的字符串`

string 插入和删除操作

insert成员函数：

1
2
3

string& insert(int pos, const char* s); // 在pos位置插入C风格字符数组
string& insert(int pos, const string& str); // 在pos位置插入字符串str
string& insert(int pos, int n, char c); // 在pos位置插入n个字符c

返回值是插入后的字符串结果，erase同理。其实就是指向自身的一个引用。

erase成员：

1	`string& erase(int pos, int n = npos); // 删除从pos位置开始的n个字符`

默认一直删除到末尾。

string 和 C-Style 字符串的转换

string转const char：

1 2	`string str = "demo"; const char* cstr = str.c_str();`

const char转string：

1 2	`const char* cstr = "demo"; string str(cstr); // 本质上其实是一个有参构造`

C++可以隐式地将const char *转换为string，但反过来不行。

string相关的全局函数

大小写转换

int tolower(int c); // 如果字符c是大写字母，则返回其小写形式，否则返回本身
int toupper(int c); // 如果字符c是小写字母，则返回其大写形式，否则返回本身

/**
  * C语言中字符就是整数，这两个函数是从C库沿袭过来的，保留了C的风格
*/

string str = "Hello, World!";
transform(str.begin(), str.end(), str.begin(), toupper); //字符串转大写
transform(str.begin(), str.end(), str.begin(), tolower); //字符串转小写

字符串和数字的转换

int/double转string

c++11标准新增了全局函数std::to_string，十分强大，可以将很多类型变成string类型。

/** 带符号整数转换成字符串 */
string to_string(int val);
string to_string(long val);
string to_string(long long val);

/** 无符号整数转换成字符串 */
string to_string(unsigned val);
string to_string(unsigned long val);
string to_string(unsigned long long val);

/** 实数转换成字符串 */
string to_string(float val);
string to_string(double val);
string to_string(long double val);

string转int/double

/** 字符串转带符号整数 */
int stoi(const string& str, size_t* idx = 0, int base = 10);
long stol(const string& str, size_t* idx = 0, int base = 10);
long long stoll(const string& str, size_t* idx = 0, int base = 10);

/**
  * 1. idx返回字符串中第一个非数字的位置，即数值部分的结束位置
  * 2. base为进制
  * 3. 该组函数会自动保留负号和自动去掉前导0
 */

/** 字符串转无符号整数 */
unsigned long stoul(const string& str, size_t* idx = 0, int base = 10);
unsigned long long stoull(const string& str, size_t* idx = 0, int base = 10);

/** 字符串转实数 */
float stof(const string& str, size_t* idx = 0);
double stod(const string& str, size_t* idx = 0);
long double stold(const string& str, size_t* idx = 0);

与之类似的在同一个库里的还有一组基于字符数组（C风格字符串）的函数如下。

// 'a' means array, since it is array-based. 

int atoi(const char* str); // 'i' means  int
long atol(const char* str); // 'l' means long
long long atoll(const char* str); // 'll' means long long

double atof(const char* str); // 'f' means double

向量(vector)

array是静态空间，而vector是动态空间

vector提供的是随机访问迭代器（Random Access Iterator），其内部用普通指针实现。

vector数据结构

就是简单的线性连续空间，两个迭代器_Myfirst和_Mylast分别指向配置得来的连续空间中已被使用的范围，迭代器Myend指向整块连续内存空间的尾端

常用API

构造函数

vector<T> v; // 采用模版类实现，默认构造函数
vector<T> v(T* v1.begin(), T* v1.end()); // 将v1[begin(), end())区间中的元素拷贝给本身
vector<T> v(int n, T elem); // 将n个elem拷贝给本身
vector<T> v(const vector<T> v1); // 拷贝构造函数

赋值操作

1
2
3

assign(beg, end); // 将[beg, end)区间中的数据拷贝复制给本身
assign(n, elem); // 将n个elem拷贝给本身
vector& operator=(const vector& vec); // 重载赋值操作符

互换操作：

1	`swap(vec); //将vec与本身的元素互换`

大小操作

int size(); // 返回容器中的元素个数
bool empty(); // 判断容器是否为空

void resize(int num); 
// 重新指定容器的长度为num，若容器变长，则以默认值填充新位置。
// 若容器变短，则末尾超出容器长度的元素被删除
void resize(int num, T elem); 
// 重新指定容器的长度为num，若容器变长，则以elem填充新位置。
// 若容器变短，则末尾超出容器长度的元素被删除

int capacity(); // 返回容器的容量
void reserve(int len); 
// 容器预留len个元素长度，预留位置不初始化，元素不可访问

数据存取

T& at(int idx); // 返回索引idx所指的数据，如果idx越界，抛出out_of_range异常
T& operator[](int idx); // 返回索引idx所指的数据，如果idx越界，运行直接报错

T& front(); // 返回首元素的引用
T& back(); // 返回尾元素的引用

插入和删除

vector是单向开口的，只有在尾部插入和删除元素效率较高，向其它位置插入和删除元素需要大量移位操作，效率很低。

insert(const_iterator pos, T elem); // 在pos位置处插入元素elem
insert(const_iterator pos, int n, T elem); // 在pos位置插入n个元素elem
insert(pos, beg, end); // 将[beg, end)区间内的元素插到位置pos
push_back(T elem); // 尾部插入元素elem
pop_back(); // 删除最后一个元素

erase(const_iterator start, const_iterator end); // 删除区间[start, end)内的元素
erase(const_iterator pos); // 删除位置pos的元素

clear(); // 删除容器中的所有元素

双向队列(deque)

vector是单向开口的连续内存空间，而deque是双向开口的连续线性空间：

deque在头部尾部插入删除元素都都是使用常数项时间
deque是动态的分段连续空间组合而成，随时可以增加新空间链接起来

deque虽然也支持随机访问，但实现较复杂，需要随机访问最好用vector。

常用API

构造函数

deque<T> deqT; // 默认构造函数
deque(beg, end); // 构造函数将[beg, end)区间中的元素拷贝给本身
deque(int n, T elem); // 构造函数将n个elem拷贝给本身
deque(const deque& deq); // 拷贝构造函数

赋值操作

assign(beg, end); // 将[beg, end)区间中的元素拷贝赋值给本身
assign(int n, T elem); // 将n个元素elem拷贝赋值给本身

deque& operator=(const deque& deq); // 重载赋值操作符

swap(deq); // 将deq与本身的元素互换

大小操作

int size(); // 返回容器中元素的个数
bool empty(); // 判断容器是否为空

void resize(int num); 
// 重新指定容器的长度为num，若容器变长，则以默认值填充新位置，
// 如果容器变短，则末尾超出容器长度的元素被删除
void resize(int num, T elem);
// 重新指定容器的长度为num，若容器变长，则以elem填充新位置，
// 如果容器变短，则末尾超出容器长度的元素被删除

双端插入和删除

push_back(T elem); // 在容器尾部添加一个元素
push_front(T elem); // 在容器头部插入一个元素

pop_back(); // 删除容器最后一个数据
pop_front(); // 删除容器第一个数据

数据存取

T& at(int idx); // 返回索引idx所指的数据，如果idx越界，抛出out_of_range异常
T& operator[](int idx); // 返回索引idx所指的数据，如果idx越界，运行直接报错

T& front(); // 返回首元素的引用
T& back(); // 返回尾元素的引用

插入操作

const_iterator insert(const_iterator pos, T elem); 
// 在pos位置处插入元素elem的拷贝，返回新数据的位置
void insert(const_iterator pos, int n, T elem); 
// 在pos位置插入n个元素elem，无返回值
void insert(pos, beg, end);
// 将[beg, end)区间内的元素插到位置pos，无返回值

删除操作

clear(); // 移除容器的所有数据
iterator erase(iterator beg, iterator end);
// 删除区间[beg, end)的数据，返回下一个数据的位置
iterator erase(iterator pos)；
// 删除pos位置的数据，返回下一个数据的位置

栈(stack)

不允许遍历行为，不提供迭代器！

常用API

构造函数

1 2	`stack<T> stkT; // 默认构造函数，stack采用模版类实现 stack(const stack& stk); // 拷贝构造函数`

赋值操作

1	`stack& operator=(const stack& stk); // 重载赋值操作符`

数据存取操作

1
2
3

void push(T elem); // 向栈顶添加元素
void pop(); // 从栈顶移除第一个元素
T& top(); // 返回栈顶元素

大小操作

1 2	`bool empty(); // 判断堆栈是否为空 int size(); // 返回栈的大小`

队列(queue)

先进先出，从队头pop，从队尾push

外界只会访问queue的顶端元素，queue不提供遍历功能，因此没有迭代器

queue中的元素在内存中不一定连续

常用API

queue 构造函数

1 2	`queue<T> queT; // queue对象的默认构造函数形式，采用模版类实现 queue(const queue& que); // 拷贝构造函数`

queue 存取、插入和删除操作

void push(T elem); // 往队尾添加元素
void pop(); // 从队头移除第一个元素
T& back(); // 返回最后一个元素
T& front(); // 返回第一个元素

queue 赋值操作

1	`queue& operator=(const queue& que); // 重载赋值操作符`

queue 大小操作

1 2	`bool empty(); // 判断队列是否为空 int size(); // 返回队列的大小`

链表(list)

list容器是一个循环的双向链表。

链表对于任意位置插入或删除都是常数项时间。

常用API

构造函数

list<T> lstT; // 默认构造形式，list采用模版类实现
list(beg, end); // 构造函数将[beg, end)区间内的元素拷贝给本身
list(int n, T elem); // 构造函数将n个elem拷贝给本身
list(const list& lst); // 拷贝构造函数

数据元素插入和删除操作

void push_back(T elem); // 在容器尾部加入一个元素
void pop_back(); // 删除容器中最后一个元素

void push_front(T elem); // 在容器开头插入一个元素
void pop_front(); // 从容器开头移除第一个元素

insert(iterator pos, elem); // 在pos位置插入elem元素的拷贝，返回新数据的位置
insert(iterator pos, n, elem); // 在pos位置插入n个elem元素的拷贝，无返回值
insert(iterator pos, beg, end); // 在pos位置插入[beg, end)区间内的数据，无返回值

void clear(); // 移除容器的所有数据

erase(beg, end); // 删除[beg, end)区间内的所有数据，返回下一个数据的位置
erase(pos); // 删除pos位置的数据，返回下一个数据的位置

remove(elem); // 删除容器中所有与elem匹配的元素

大小操作

int size(); // 返回容器中元素的个数
bool empty(); // 判断容器是否为空

void resize(int num);
// 重新制定容器的长度为num，若容器变长，则以默认值填充新位置；
// 若容器变短，则末尾超出容器长度的元素被删除
void resize(int num, T elem);
// 重新制定容器的长度为num，若容器变长，则以elem填充新位置；
// 若容器变短，则末尾超出容器长度的元素被删除

赋值操作

assign(beg, end); // 将[beg, end)区间中的数据拷贝赋值给本身
assign(n, elem); // 将n个elem拷贝赋值给本身

list& operator=(const list& lst); // 重载等号操作符

swap(lst); // 将lst与本身的元素互换

数据的存取

1 2	`T& front(); // 返回第一个元素 T& back(); // 返回最后一个元素`

反转排序

void reverse(); // 反转链表

void sort(); // 默认list排序，规则为从小到大
void sort(bool (*cmp)(T item1, T item2)); // 指定排序规则的list排序

// 不能用sort(lst.begin(), lst.end())
// 因为所有系统提供的某些算法（比如排序），其迭代器必须支持随机访问
// 不支持随机访问的迭代器的容器，容器本身会对应提供相应的算法的接口

集合(set/multiset)

set和multiset的底层实现是红黑树

不可以通过set的迭代器改变set元素的值，因为其元素值就是key值，随意改变会破坏set组织，因此set的iterator是const_iterator。

常用API

构造函数

1
2
3

set<T> st; // set 默认构造函数
multiset<T> mst; // multiset 默认构造函数
set(const set& st); // 拷贝构造函数

赋值操作

1
2
3

set& operator=(const set& st); // 重载等号操作符

swap(st); // 交换两个集合容器

大小操作

1 2	`int size(); // 返回容器中元素的数目 bool empty(); // 判断容器是否为空`

插入和删除操作

pair<iterator, bool> insert(T elem); 
// 在容器中插入元素，返回插入位置的迭代器（不成功则返回end()）和是否插入成功
// 如果是multiset，则返回值只有iterator
clear(); // 清除所有元素
iterator erase(pos); // 删除pos迭代器所指的元素，返回下一个元素的迭代器
iterator erase(beg, end); // 删除区间[beg, end)内的所有元素，返回下一个元素的迭代器
erase(T elem); // 删除容器中值为elem的元素

插入之前可以指定排序规则：

//利用仿函数 指定set容器的排序规则
class MyCompare
{
public:
    bool operator()(int v1, int v2)
    {
        return v1 > v2;
    }
};

set<int, MyCompare> s;

//模版类也是可以有默认值的，第二个模版参数的默认值为less

自定义的数据类型需要指出排序规则。

当然，也可以通过重载小于操作符的方式指出。

查找操作

iterator find(T key); 
// 查找键key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回set.end();
int count(T key);
// 查找键key的元素个数
iterator lower_bound(T keyElem);
// 返回第一个key>=keyElem元素的迭代器
iterator upper_bound(T keyElem);
// 返回第一个key>keyElem元素的迭代器
pair<iterator, iterator> equal_range(T keyElem);
// 返回容器中key与keyElem上相等的两个上下限迭代器

上述几个方法若不存在，返回值都是尾迭代器。

对组的构造和使用：

//构造
pair<T1, T2> p(k, v);
//另一种构造方式
pair<T1, T2> p = make_pair(k, v);
//使用
cout << p.first << p.second << endl;

映射(map/multimap)

map和multimap的底层实现是红黑树

常用API

map 构造函数

1 2	`map<T1, T2> mapTT; // map默认构造函数 map(const map& mp); // 拷贝构造函数`

map 赋值操作

1 2	`map& operator=(const map& mp); // 重载等号操作符 swap(mp); // 交换两个集合容器`

map 大小操作

1 2	`int size(); // 返回容器中元素的数目 bool empty(); // 判断容器是否为空`

map 插入元素操作

pair<iterator, bool> insert(pair<T1, T2> p); // 通过pair的方式插入对象
/*
1. 参数部分可以用pair的构造函数创建匿名对象
2. 也可以使用make_pair创建pair对象
3. 还可以用map<T1, T2>::value_type(key, value)来实现
*/

T2& operator[](T1 key); // 通过下标的方式插入值
// 如果通过下标访问新的键却没有赋值，会自动用默认值填充

map<string, int> myMap;
// 直接使用pair构造函数
myMap.insert(pair<string, int>("apple", 5));
// 使用make_pair函数
myMap.insert(make_pair("banana", 3));
// 使用value_type
myMap.insert(map<string, int>::value_type("orange", 4));

map指定排序规则的方式和set类似，都是利用functor在模版类型表的最后一个参数处指定。

map 删除操作

void clear(); // 删除所有元素
iterator erase(iterator pos); // 删除pos迭代器所指的元素，返回下一个元素的迭代器
iterator erase(beg, end); // 删除区间[beg, end)内的所有元素，返回下一个元素的迭代器
erase(keyElem); // 删除容器中key为keyElem的对组

map 查找操作

iterator find(T1 key); 
// 查找键key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回map.end()
int count(T1 keyElem);
// 返回容器中key为keyElem的对组个数，对map来说只可能是0或1，对于multimap可能大于1

iterator lower_bound(T keyElem);
// 返回第一个key>=keyElem元素的迭代器
iterator upper_bound(T keyElem);
// 返回第一个key>keyElem元素的迭代器
pair<iterator, iterator> equal_range(T keyElem);
// 返回容器中key与keyElem上相等的两个上下限迭代器

优先级队列(priority_queue)

优先级队列的底层实现是最小/最大二叉堆

常用API

// C++中的优先队列
#include <queue>

// 创建最大堆(默认)
priority_queue<int> maxHeap;
// 创建最小堆
priority_queue<int, vector<int>, greater<int>> minHeap;
// greater表示大的元素会放在小的元素下方，堆顶是最小的元素

// 主要操作
void push(const value_type& val);  // 插入元素
void pop();                         // 删除堆顶元素
value_type top() const;             // 访问堆顶元素
bool empty() const;                 // 检查队列是否为空
size_type size() const;             // 返回队列中的元素数量

自定义优先级

自定义比较函数对象（仿函数）

// 自定义比较类
struct CustomCompare {
    bool operator()(const int& a, const int& b) {
        // 自定义比较逻辑
        return a % 10 > b % 10;  // 按个位数字从小到大排序
    }
};

// 使用自定义比较器
priority_queue<int, vector<int>, CustomCompare> customPQ;

对于自定义类型，重载比较运算符

注意构建最大堆需要重载的是小于运算符，较小的放较大的下面，堆顶是最大的元素

struct Task {
    int id;
    int priority;
    
    // 重载小于运算符（用于最大堆）
    bool operator<(const Task& other) const {
        return priority < other.priority;  // 优先级高的先出队
    }
};

// 默认是最大堆，会使用operator
priority_queue<Task> taskQueue;

// 如果要创建最小堆，需要反转比较逻辑
struct ReverseCompare {
    bool operator()(const Task& a, const Task& b) {
        return a.priority > b.priority;
    }
};
priority_queue<Task, vector<Task>, ReverseCompare> minTaskQueue;

无序容器(`unordered_*`)

无序容器包括：unordered_map、unordered_multimap、unordered_set、unordered_multiset

无序容器 vs 有序容器

无序容器的底层实现是哈希表，有序容器的实现是红黑树
哈希表的插入/查找/删除的平均时间复杂度都是O(1)，但最坏时间复杂度是O(n)（哈希冲突严重时）

红黑树插入/查找/删除的平均和最坏时间复杂度都是O(log n)
无序容器通常消耗更多的内存，但在平均情况下查找/插入/删除更快速

有序容器用在需要对元素排序时，能保证稳定的最坏情况性能，相对节省内存空间

函数对象/仿函数(Functor)

适配器

函数对象适配器

class myPrint: public binary_function<int, int, void> 
// 2.做继承 参数1类型 + 参数2类型 + 返回值类型 binary_function
{
public:
    void operator()(int val, int base) const // 3. 加const, 和父类保持一致
    {
        cout << val + base << endl;
    }
}

int main()
{
    vector<int> v;
    for (int i = 0; i < 10; i++) v.push_back(i);
    int n;
    cin >> n;
    for_each(v.begin(), v.end(), bind2nd(myPrint(), n)); 
    // 1. 将参数进行绑定 bind2nd
    // bind1st 功能类似，不过n会被绑定到第一个参数中
    return 0;
};

取反适配器

class GreaterThanFive: public unary_function<int, bool> 
// 2. 做继承 参数类型 + 返回值类型 unary_function
{
public:
    bool operator()(int val) const // 3.加 const
    {
        return val > 5;
    }
}

int main()
{
    vector<int> v;
    for (int i = 0; i < 10; i++) v.push_back(i);
    
    vector<int>::iterator pos = find_if(v.begin(), v.end(), not1(GreaterThanFive()));  //1. 一元取反 not1
    
    if (pos != v.end()) cout << *pos << endl;
    return 0;
}

或者用更简便的方法：

1	`vector<int>::iterator pos = find_if(v.begin(), v.end(), not1(bind2nd(greater<int>(), 5)));`

函数指针适配器

1 2	`for_each(v.begin(), v.end(), bind2nd(ptr_fun(myPrint), n)); // 函数指针适配器 ptr_fun 将函数指针适配成仿函数`

成员函数适配器

1
2
3

for_each(v.begin(), v.end(), mem_fun_ref(&Dog::bark));
// 成员函数适配器 mem_fun_ref
// 如果容器中存放的不是对象实体，而是对象指针时，则需使用 ptr_fun

偏函数

对于一个多参数的函数，在某些应用场景下，它的一些参数往往取固定值，可以针对这样的函数，生成一个新函数，该新函数不包含原函数中已指定固定值的参数。

例如，对于下面的print函数：

1	`void print(int n, int base); // 按base进制来输出n`

由于它常常用来按十进制输出，因此，可以基于print生成一个新函数print10，只接受一个参数n，base固定为10：

#include <functional>
using namespace std;
using namespace std::placeholders;

function<void(int)> print10 = bind(print, _1, 10);
print10(23); //相当于 print(23, 10)

算法(Algorithm)

自定义的类如果想直接使用算法库，则需补全默认构造函数、拷贝构造函数、析构函数、赋值操作符、小于操作符、等于操作符。

遍历算法

`for_each`

/**
  * 遍历算法 遍历容器元素
  * @param beg 开始迭代器
  * @param end 结束迭代器
  * @param _callback 函数回调或者函数对象
  * @return 函数对象
*/
for_each(iterator beg, iterator end, _callback);

`transform`

/**
  * transform算法 将指定容器内的元素搬运到另一个容器中
  * 注意：transform不会给目标容器分配内存，所以需要我们提前分配好内存
  * @param beg1 源容器开始迭代器
  * @param end1 源容器结束迭代器
  * @param beg2 目标容器开始迭代器
  * @param _callback 回调函数或者函数对象
  * @return 返回目标容器迭代器
*/
iterator transform(iterator beg1, iterator end1, iterator beg2, _callback);

查找算法

`find`

/**
  * find 算法 查找元素
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
  * @param value 查找的元素
  * @return 返回查找元素的位置
*/
iterator find(iterator beg, iterator end, value);

`find_if`

/**
  * find_if 算法 条件查找
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
  * @param _callback 回调函数或者谓词(返回 bool 类型的函数对象)
  * @return 返回查找元素的位置
*/
iterator find_if(iterator beg, iterator end, _callback);

利用find_if实现自定义类的find操作的时候，之前的函数适配器可能会派上用场。

`adjacent_find`

/**
  * adjacent_find 算法 查找相邻重复元素
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
  * @param _callback 回调函数或者谓词(返回 bool 类型的函数对象)
  * @return 返回相邻元素的第一个位置的迭代器
*/
iterator adjacent_find(iterator beg, iterator end, _callback);

`binary_search`

/**
  * binary_search 算法 二分法查找
  * 注意：在无序序列中不可用
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
  * @param value 查找的元素
  * @return bool 查找返回true，否则false
*/
bool binary_search(iterator beg, iterator end, value);

`count`

/**
  * count 算法 统计元素出现次数
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
  * @param value 待计数的元素
  * @return int 返回元素个数
*/
int count(iterator beg, iterator end, value);

`count_if`

/**
  * count_if 算法 统计元素出现次数
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
  * @param _callback 回调函数或者谓词
  * @return int 返回元素个数
*/
int count_if(iterator beg, iterator end, _callback);

排序算法

`merge`

/**
  * merge 算法 容器元素合并，并储存到另一个容器中
  * 注意：两个容器必须是有序的
  * @param beg1 容器1开始迭代器
  * @param end1 容器1结束迭代器
  * @param beg2 容器2开始迭代器
  * @param end2 容器2结束迭代器
  * @param dest 目标容器开始迭代器
*/
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

`sort`

/**
  * sort 算法 容器元素排序
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
  * @param _callback 回调函数或者谓词
*/
sort(iterator beg, iterator end, _callback);

`random_shuffle`

/**
  * random_shuffle 算法 对指定范围内的元素随机调整次序
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
*/
random_shuffle(iterator beg, iterator end);

如果想要每次打乱不同，需要自己设置随机数种子：

#include <ctime>
using namespace std;

int main()
{
    srand((unsigned int)time(NULL));
    ......//random_shuffle
}

`reverse`

/**
  * reverse 算法 反转指定范围的元素
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
*/
reverse(iterator beg, iterator end);

拷贝和替换算法

`copy`

/**
  * copy算法 将容器内指定范围的元素拷贝到另一容器当中
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
  * @param dest 目标容器开始迭代器
*/
copy(iterator beg, iterator end, iterator dest);

使用copy算法快速打印容器：

vector<int> v = {1, 2, 3, 4, 5};
for_each(v.begin(), v.end(), [](int val){cout << val << " ";});
// 等价于
copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
// 需要#include <iterator>

`replace`

/**
  * replace算法 将容器内指定范围的旧元素修改为新元素
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
  * @param oldvalue 旧元素
  * @param newvalue 新元素
*/
replace(inerator beg, iterator end, oldvalue, newvalue);

`replace_if`

/**
  * replace_if 算法 将容器内指定范围满足条件的元素替换为新元素
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
  * @param _callback 回调函数或者谓词（返回bool类型的函数对象）
  * @param newvalue 新元素
*/
replace_if(inerator beg, inerator end, _callback, newvalue);

`swap`

/**
  * swap 算法 互换两个容器元素
  * @param c1 容器1
  * @param c2 容器2
*/
swap(container c1, container c2);

算数生成算法

`accumulate`

#include <numeric> // 注意头文件不是algorithm了
/**
  * accumulate 算法 计算容器元素累计总和
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
  * @param value 起始累加值
*/
accumulate(iterator beg, iterator end, value);

`fill`

/**
  * fill 算法
  * @param beg 容器开始迭代器
  * @param end 容器结束迭代器
  * @param value 填充元素
*/
fill(iterator beg, iterator end, value);

集合算法

`set_intersection`

/**
  * set_intersection 算法 求两个set集合的交集
  * 注意：两个集合必须是有序序列
  * @param beg1 容器1开始迭代器
  * @param end1 容器1结束迭代器
  * @param beg2 容器2开始迭代器
  * @param end2 容器2结束迭代器
  * @param dest 目标容器开始迭代器
  * @return 目标容器最后一个元素的迭代器地址
*/
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

`set_union`

/**
  * set_union 算法 求两个set集合的并集
  * 注意：两个集合必须是有序序列
  * @param beg1 容器1开始迭代器
  * @param end1 容器1结束迭代器
  * @param beg2 容器2开始迭代器
  * @param end2 容器2结束迭代器
  * @param dest 目标容器开始迭代器
  * @return 目标容器最后一个元素的迭代器地址
*/
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

`set_difference`

/**
  * set_difference 算法 求两个set集合的差集
  * 注意：两个集合必须是有序序列
  * @param beg1 容器1开始迭代器
  * @param end1 容器1结束迭代器
  * @param beg2 容器2开始迭代器
  * @param end2 容器2结束迭代器
  * @param dest 目标容器开始迭代器
  * @return 目标容器最后一个元素的迭代器地址
*/
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

C++

#C++ #STL

STL Tutorial Note

http://oooscar8.github.io/2025/02/21/STL/

作者

Alex Sun

发布于

2025年2月21日

许可协议

Simulator Lab 上一篇

将Typora警告框转化成fluid便签下一篇

STL Tutorial Note

概述

容器(Container)

vector<元素类型>

list<元素类型>

deque<元素类型>

stack<元素类型>

queue<元素类型>

priority_queue<元素类型>

map<key，value> 和 multimap<key，value>

set<元素类型> 和 multiset<元素类型>

basic_string<字符类型>

迭代器(Iterator)

迭代器的分类（五种基本迭代器）

反向迭代器（reverse iterator）

插入迭代器（insert iterator）

使用迭代器求解约瑟夫问题

算法(Algorithm)

算法的自定义操作

仿函数(Functor)

匿名函数(lambda表达式)

最后

容器(Container)

选择容器

字符串(string)

常用API

string相关的全局函数

向量(vector)

vector数据结构

常用API

双向队列(deque)

常用API

栈(stack)

常用API

队列(queue)

常用API

链表(list)

常用API

集合(set/multiset)

常用API

映射(map/multimap)

常用API

优先级队列(priority_queue)

常用API

自定义优先级

无序容器(unordered_*)

无序容器 vs 有序容器

函数对象/仿函数(Functor)

适配器

函数对象适配器

取反适配器

函数指针适配器

成员函数适配器

偏函数

算法(Algorithm)

遍历算法

for_each

transform

查找算法

find

find_if

adjacent_find

binary_search

count

count_if

排序算法

merge

sort

random_shuffle

reverse

拷贝和替换算法

copy

replace

replace_if

swap

算数生成算法

accumulate

fill

集合算法

set_intersection

无序容器(`unordered_*`)

`for_each`

`transform`

`find`

`find_if`

`adjacent_find`

`binary_search`

`count`

`count_if`

`merge`

`sort`

`random_shuffle`

`reverse`

`copy`

`replace`

`replace_if`

`swap`

`accumulate`

`fill`

`set_intersection`

`set_union`

`set_difference`