STL简述

一、标准容器

容器是标准模板库（STL，standard template library）中的一个核心概念，它指的是那些能够存储和管理数据集合的类。容器的主要目的是提供一种机制，使得程序员可以存储一个元素集合，并以一种统一和高效的方式来处理这些元素，而不需要关心底层数据的具体存储细节。

1. 顺序容器

vector

1. 向量容器。

2. 底层数据结构：动态开辟的数组，每次以原来空间大小的2倍进行扩容

3. ​vector<int> vec;​

4. 常用方法

   1. 增加：

      方法	解释
      vec.push_back(20)	末尾添加元素，时间复杂度O(1)，可以导致容器扩容
      vec.insert(it, 20)	向迭代器位置插入元素，时间复杂度O(n)

   2. 删除：

      方法	解释
      vec.pop_back()	删除末尾元素 O(1)
      vec.erase(it)	删除it迭代器指向的元素 O(n)

   3. 查询：

      方法	解释
      operator[]	通过下标随机访问 O(1)
      iterator	迭代器访问
      find(vec.begin(), vec.end(), 3);	不是成员方法，是泛型算法函数
      for_each(vec.begin(), vec.end(), [] (auto it)->void {cout<<*it;});	不是成员方法，是泛型算法函数

   4. 其他：

      方法	方法
      vec.size()	查看容器有效元素数量
      vec.empty()：	判空
      vec.reserve(20)	给vector预留空间，只给容器底层开辟指定大小的内存空间，并不会添加新的元素
      vec.resize(20)	容器扩容，不仅开辟内存空间，还会添加新元素，默认添加的是0
      swap(vec[1], vec[3])	交换容器元素

5. 迭代器失效问题：对容器进行连续插入或者删除操作（insert/erase)，一定要更新迭代器，否则第一次insert或者erase完成，迭代器就失效了，详见下面的实例

6. 实例：

   	// 删除偶数
   	auto it2 = vec.begin();
   	while(it2!=vec.end())
   	{
   	if(*it2%2 == 0 )
   	{
   	it2 = vec.erase(it2); //更新迭代器。 erase删除迭代器指向的元素后，返回新的指向原来位置的迭代器。解释：迭代器指向12345中的4，删除了4后5前移到4的位置，返回的迭代器指向5
   	}else
   	{
   	it2++;
   	}
   	}

   	// 在奇数前添加小1的偶数
   	auto it3 = vec.begin();
   	for(;it3!=vec.end();++it3)
   	{
   	if(*it3%2!=0)
   	{
   	it3 = vec.insert(it3, *it3-1); // insert，向迭代器前插入元素，且返回的迭代器指向插入的那个元素
   	++it3;
   	}
   	}

deque

1. 双端队列容器
2. 底层数据结构：动态开辟的二维数组，以2倍的方式进行扩容，每次扩容后，原来第二维的数组的指针，从新的第一维数组的下标oldsize/2开始存放，上下都预留相同的空行，方便支持deque的首尾元素添加。
3. std:deque的实现较为复杂，但通常是由一个存放固定长度数组的指针的数组作为第一维的数组，第二维的数组则是动态开辟的固定长度数组。

​deque底层数据结构示意图（假想）

1. deque<int> deq;
2. 常用方法

   1. 增加：

      • deq.push_back(20); 从末尾添加元素 O(1)
      • deq.push_front(20); 从首部添加元素 O(1)
      • deq.insert(it, 20); 在指定位置添加元素 O(n)

   2. 删除：

      • deq.pop_back(); O(1)
      • deq.pop_front(); O(1)
      • deq.erase(it) O(n)

   3. 查询：

      和vector相同，支持随机访问和迭代器访问，以及find函数和for_each函数

list

1. 链表容器
2. 底层数据结构：双向循环链表
3. list<int> mylist
4. 常用方法

   1. 增加：

      • mylist.push_back(20); 从末尾添加元素 O(1)
      • mylist.push_front(20); 从首部添加元素 O(1)
      • mylist.insert(it, 20); 在指定位置添加元素 O(1)，但是在链表中插入前一般都要先进行查询操作，链表的查询操作效率比较低，时间复杂度一般为O(n)

   2. 删除：

      • mylist.pop_back(); O(1)
      • mylist.pop_front(); O(1)
      • mylist.erase(it); O(1)

   3. 查询

      迭代器，find和for_each

三者对比

1. vector特点：动态数组，内存是连续的，2倍的方式进行扩容，vec<int> vec；0-1-2-4-8-... 默认创建的vector不分配内存空间，可以使用vec.reserve(20)开辟内存空间。
2. deque特点：动态开辟的二维数组空间，第二维是固定长度的数组，内存是分块连续的，扩容的时候（第一维的数组进行2倍扩容），第二维的数组从新的第一维数组的下标为oldsize/2的位置开始放置。oldsize指旧的第一维数组长度。默认分配的最小内存比vector更大。
3. 面经问题：deque底层内存是否是连续的？不连续，每一个第二维数组是本身连续的，但是多个第二维数组之间是不连续的。即分块连续。
4. vector和deque之间的区别？
   1. 底层数据结构不同：一维数组和二维数组
   2. 在前中后插入删除元素的时间复杂度：中间和末尾相同，前deque O(1), vector O(n)
   3. 内存的使用效率：vector低，因为vector随着扩容需要更大的连续的内存空间；deque高，deque第二维的各个数组之间不需要连续的内存块
   4. 在中间进行inert和erase，vector和deque它们的效率谁能好一点？vector，vector的内存是完全连续的，更好移动一点。而deque因为多个二维数组在内存中并不连续，因此移动更麻烦一点。
5. vector和list之间的区别？（也就是问数组和链表的区别）
   1. 底层数据结构不同：数组和双向循环链表
   2. 数组：增删查O(n)，随机访问O(1)
   3. 链表：增加删除插入O(1)，查找O(n)，不支持随机访问

2. 容器适配器

如何理解容器适配器（特点）：

1. 容器适配器没有自己的数据结构，它是另外一个容器的封装，它的方法全部由底层依赖的容器进行实现
2. 没有实现自己的迭代器

stack

1. 栈，特点：后进先出，入栈和出栈都在栈顶
2. 依赖deque
3. stack<int> st
4. 常用方法
   • st.push(e) 入栈
   • st.pop() 出栈
   • st.top() 查看栈顶元素
   • st.empty() 判断栈空
   • st.size() 返回元素个数

queue

1. 队列，特点：先进先出，尾部入队，首部出队
2. 依赖deque
3. queue<int> que
4. 常用方法
   • que.push(ele) 入队
   • que.pop() 出队
   • que.front() 查看队头元素
   • que.back() 查看队尾元素
   • que.empty() 判空
   • que.size() 返回元素个数

priority_queue

1. 优先级队列，队列中的元素根据优先级排序，默认是大根堆。入队时进行排序，出队时排出优先级最高的元素，并对剩下的元素重新排序
2. 依赖vector，底层数据结构默认是大根堆
3. 头文件
4. priority_queue<int> pque
5. 常用方法
   • pque.push(ele) 入队
   • pque.pop() 出优先级最高的元素
   • pque.top() 查看优先级最高的元素
   • pque.empty() 判空
   • pque.size() 返回元素数量

为什么stack和queue的底层依赖deque而不是vector?

1. vector的初始内存使用效率太低，没有deque好 vector 0-1-2-4-8-… deque 在某些资料中指出当插入第一个元素时会分配至少8倍该元素大小的内存，在64位系统上是16倍，或者4096字节，以较大者为准
2. 对于queue来说，需要支持尾部插入，头部删除，deque在该方面的是O(1)的时间复杂度，比vector好
3. vector需要大片的连续内存，而deque只需要分段连续的内存，当存储大量数据时，显然deque对于内存的利用率更好一点

为什么priority_queue的底层依赖vector

因为priority_queue的底层数据结构是大根堆，而大根堆的左右子节点是通过下标来计算出来的，所以在一个内存连续的数组上构建大根堆或是小根堆。vector的底层是连续的内存。

3. 关联容器

关联容器的主要特点是它们可以自动对元素进行排序，并且提供了快速的查找、插入和删除操作。

无序关联容器

1. 底层数据结构：链式哈希表
2. 增删查时间复杂度O(1)
3. 数据是无序的
4. unordered_set, unordered_multiset, unordered_map, unordered_multimap

有序关联容器

1. 底层数据结构：红黑树
2. 增删查时间复杂度O(logn)
3. 数据是有序的
4. set, multiset, map, multimap
5. 有序关联容器的方法与无序关联容器的方法名相同

集合(set)

1. unordered_set

   不存储重复的元素，插入重复元素自动去重

2. unordered_multset

   允许元素重复

3. 常用方法

   • set.size()：返回集合中的元素数量。
   • set.empty()：检查集合是否为空。
   • set.insert(value)：插入一个新元素。
   • set.erase(value)：删除一个元素。
   • set.find(value)：查找一个元素，如果找到则返回指向该元素的迭代器，否则返回 end()。
   • set.clear()：清空集合中的所有元素。
   • set.begin() 和 set.end()：返回指向集合开始和结束的迭代器。

映射(map)

1. unordered_map

   不允许key重复，插入重复的key自动忽略，也就是说插入多个相同key的键值对，只会存储第一个

   	// 插入方式
   	unordered_map<int, string> map1;
   	map1.insert(make_pair(1, "aaa"));
   	map1.insert({2, "bbb"});
   	map1[3] = "ccc";
   	// map1 = {
   	{1, "aaa"},
   	{2, "bbb"},
   	}

2. unordered_multimap

   允许key重复

3. 存储的数据为键值对[key,value]，实际是一个pair对象

   	template<class A, class B>
   	struct pair
   	{
   	A first; // KEY
   	B second; // VALUE
   	{

4. map的operator[]

   1. 查询，如果key存在，map[key]返回value
   2. 如果key不存在，map[key]插入一对数据[key, value]，value为空，map[key]=val则会插入一对[key, val]的键值对

5. 除了插入以外，其余的方法与set的成员方法相同

哈希表使用场景：海量数据查重

例如：查询十万个随机数字中，有哪些数字重复了，并且统计数字重复的次数，使用map

如果要对这些数据去重，则使用set

二、近容器

近容器不是一个标准术语，在这里我对他的定义是：可以看成是容器，但不完全符合标准容器的所有要求和特性。

数组(array)

1. std::array 是C++11中引入的一个容器，它是一个固定大小的数组，其大小在编译时确定。它提供了一个容器接口，使得数组可以像其他STL容器一样使用。

2. std::array 的优点是性能好，因为它不涉及动态内存分配，并且可以利用固定大小的优势进行优化。

3. 使用示例：

   	#include <array>
   	std::array<int, 5> myArray = {1, 2, 3, 4, 5};

字符串(string)

1. std::string 是一个可变长度的字符串容器，它封装了C风格的字符数组，并提供了丰富的字符串操作功能。

2. std::string 的优点是使用方便，功能强大，支持字符串的动态扩展，并且提供了大量的成员函数来处理字符串。

3. 使用示例：

   	#include <string>
   	// 使用常量字符串构造
   	std::string str1 = "Hello, World!";
   	// 使用字符数组和长度构造
   	char data[] = {'H', 'e', 'l', 'l', 'o'};
   	std::string str2(data, 5);
   	// 使用单个字符和数量构造
   	std::string str('a', 5); // "aaaaa"

4. 常用方法

   1. 访问：

      • str[0]，通过下标随机访问
      • str.at(0)，通过at函数和下标随机访问

   2. 插入：

      • str.push_back(”a”); 在末尾添加一个字符
      • str.append(”world”); 在末尾添加一个字符串
      • str.insert(5, “world”); 在下标5的位置插入字符串，原来的位于下标5位置的字符后移

   3. 删除:

      • str.erase(5); 删除下标5的元素

   4. 查找：

      • str.find("World"); 从前往后查找子字符串或字符在字符串中的位置
      • str.rfind("l"); 从后往前查找子字符串或字符
      • str.substr(0, 3); 获取从下标0开始，长度3的字符串

   5. 字符处理

      • tolower(ch)：将一个字母字符转换为小写
      • toupper(ch)：将一个字母字符转换成大小
      • isalpha(ch)：判断字符是否是字母
      • isalnum(ch)：判断字符是否是字母或数字

   6. 其他：

      • str.size(); 获取字符串中字符数量
      • str.length(); 同str.size()
      • str.empty(); 判空
      • str.clear(); 清空字符串
      • str.substr(index, length)：获取str中从index位置开始length长度的字串，如果没有length，就获取从index到结尾的字串

   7. 字符串和整数相互转换的方法

   8. 整数到字符串

      • C++11引入的to_string函数，可以将整数（包括 char、int、long、long long 等）转换为 std::string。

        	int num = 123;
        	std::string str = std::to_string(num);

      • 使用字符串流**std::stringstream**

        	int num = 123;
        	std::stringstream ss;
        	ss << num;
        	std::string str = ss.str();

   9. 从字符串到整数

      • ​std::stoi​​ ** 函数：string→int**

        	std::string str = "123";
        	int num = std::stoi(str);

      • ​std::stol​​ ** 函数：string→long**

      • ​std::stoll​​ ** 函数：string→long long**

      • ​std::stoul​​ ** 函数：string→unsigned long**

      • ​std::stoull​​ ** 函数：string→unsigned long long**

      • 使用字符串流（​​std::stringstream​​ ）

        	std::string str = "123";
        	std::stringstream ss(str);
        	int num;
        	ss >> num;

位集(bitset)

1. std::bitset 是一个固定大小的位容器，可以存储固定数量的布尔值。它是C++标准库中的一个类模板，用于高效地存储和操作位。

2. std::bitset 的优点是访问速度快，因为它直接操作位，并且提供了方便的接口来设置、清除和翻转位。

3. 使用示例：

   	#include <bitset>
   	std::bitset<8> myBitset("10101010"); // 字符串初始化
   	std::bitset<8> myBitset(170); // 十进制整数初始化
   	// 按位设置bitset的值
   	myBitset.set(7, 1); // 设置第7位为1
   	myBitset.set(6, 0); // 设置第6位为0
   	// 下标访问
   	myBitset[5] = 1;

三、迭代器

迭代器（Iterator）是一种抽象概念，用于遍历容器（如数组、链表、树等）中的元素。迭代器提供了一种统一的方法来访问容器中的元素，而不需要暴露容器的内部结构。迭代器可以被看作是一种泛化的指针，指向容器中的一个元素，并提供了一系列操作来移动到下一个元素或访问当前元素。

1. iterator和const_iterator

   容器的begin()和end()方法返回正向迭代器，iterator可以对容器的元素读写，const_iterator只能读不能写

2. reverse_iterator和const_reverse_iterator

   容器的rbegin和rend方法返回的是反向迭代器，可以从末尾向首部迭代

3. 迭代器通常支持以下操作：

   • 解引用（Dereference） ：*iter，访问迭代器指向的元素。
   • 成员访问（Member Access） ：iter->mem，访问迭代器指向的元素的成员。
   • 递增（Increment） ：++iter 或 iter++，移动到下一个元素。
   • 递减（Decrement） ：--iter 或 iter--（仅双向和随机访问迭代器支持），移动到前一个元素。
   • 相等和不等比较：iter1 == iter2 和 iter1 != iter2，比较两个迭代器是否相等或不等。
   • 距离计算：iter2 - iter1（仅随机访问迭代器支持），计算两个迭代器之间的距离。

四、函数对象

1. 函数对象是对象，但是能像调用函数一样使用该对象。

   	class greator
   	{
   	public:
   	bool operator()(const int a, const int b)const
   	{
   	return a>b;
   	}
   	}; // 二元函数对象的类
   	int mmain(){
   	greator gre;
   	bool b = gre(1, 2); // 像调用函数一样使用函数对象
   	return 0;
   	return 0;
   	}

2. 如果一个类中重写了operator()运算符重载函数，那使用该类创建的对象称作函数对象，或者仿函数。这类对象可以调用函数的方式使用，而这样使用时实质是调用对象中的operator()运算符重载函数。

3. 主要的作用的是替代C语言中的函数指针，函数对象（也称为functor）和函数指针都是回调机制的实现方式

4. 好处

   1. 通过函数对象调用operator()，可以省略函数的调用开销，比通过函数指针调用（不能够inline内联调用）函数效率高。
   2. 因为函数对象是用类生成的，所以可以添加相关的成员变量，用来记录函数对象使用时的信息

5. 实例

   	class greator
   	{
   	public:
   	bool operator()(const int a, const int b)const
   	{
   	return a>b;
   	}
   	}; // 函数对象的类
   	int main() {
   	using namespace std;
   	priority_queue<int> pque1; // 默认的优先级队列
   	priority_queue<int, vector<int>, greator> pque2; // 通过模版中使用函数对象类改变优先级队列
   	for(int i=0; i&lt;20; i++)
   	{
   	pque1.push(rand()%100+1);
   	pque2.push(rand()%100+1);
   	}
   	auto length = pque1.size();
   	for(int i=0; i&lt;length; ++i)
   	{
   	cout&lt;&lt;pque1.top()&lt;&lt;' ';
   	pque1.pop();
   	}
   	cout&lt;&lt;endl;
   	for(int i=0; i&lt;length; ++i)
   	{
   	cout&lt;&lt;pque2.top()&lt;&lt;' ';
   	pque2.pop();
   	}
   	cout&lt;&lt;endl;
   	return 0;
   	}
   	for(int i=0; i&lt;20; i++)
   	{
   	pque1.push(rand()%100+1);
   	pque2.push(rand()%100+1);
   	}
   	auto length = pque1.size();
   	for(int i=0; i&lt;length; ++i)
   	{
   	cout&lt;&lt;pque1.top()&lt;&lt;' ';
   	pque1.pop();
   	}
   	cout&lt;&lt;endl;
   	for(int i=0; i&lt;length; ++i)
   	{
   	cout&lt;&lt;pque2.top()&lt;&lt;' ';
   	pque2.pop();
   	}
   	cout&lt;&lt;endl;
   	return 0;

   	96 93 92 82 79 72 70 70 68 63 62 48 42 36 35 28 22 19 6 3
   	1 5 13 17 25 27 28 37 39 43 46 54 59 65 68 83 92 95 96 100

五、泛型算法

C++的泛型算法是C++标准模板库（STL）中的一部分，它们是一组独立于任何特定容器的函数模板，可以在任何类型的容器上操作。泛型算法的核心思想是算法与数据容器分离，算法不依赖于容器的具体实现，而容器也不依赖于特定的算法。

1. 泛型算法的主要特点
   1. 模板化：泛型算法通过模板参数接受任何类型的迭代器，使其能够适用于各种容器。
   2. 迭代器依赖：算法的操作仅依赖于迭代器，不依赖于容器的具体类型。
   3. 类型无关性：算法不关心容器中元素的具体类型，只关心元素可以被迭代器访问和操作。
2. 头文件：#include<algorithm>
3. 泛型算法的接收的参数是迭代器和函数对象
4. 常见的泛型算法：
   • sort：对迭代器范围内的元素进行排序。
   • swap：交换两个元素位置
   • find：查找迭代器范围内第一个符合特定条件的元素。
   • find_if：查找迭代器范围内满足if条件的元素
   • copy：复制迭代器范围内元素到另一个容器。
   • shuffle：打乱迭代器范围内元素顺序
   • binary_search：在迭代器范围内二分查找一个元素
   • reverse：反转迭代器范围内元素
   • min：返回迭代器范围内最小值
   • max：返回迭代器范围内最大值
   • for_each：遍历迭代器范围内元素，并可以传入一个函数对象处理这个元素
5. 补充：
   1. 非修改算法：
      • std::find：查找第一个符合特定条件的元素。
      • std::count：计算某个值在范围内出现的次数。
      • std::search：搜索子序列。
   2. 修改算法：
      • std::copy：复制元素到另一个容器。
      • std::fill：将某个值赋给一定范围内的所有元素。
      • std::replace：替换范围内所有符合特定条件的元素。
   3. 排序和相关算法：
      • std::sort：对范围内的元素进行排序。
      • std::partial_sort：部分排序，确保范围的前N个元素是整个范围中最小的N个元素。
      • std::nth_element：确保第N个位置的元素放置在排序后它应该在的位置。
   4. 集合算法：
      • std::set_union：计算两个集合的并集。
      • std::set_intersection：计算两个集合的交集。
      • std::set_difference：计算两个集合的差集。
   5. 配对算法：
      • std::mismatch：查找两个序列中第一个不匹配的元素。
      • std::equal：检查两个序列是否相等。
   6. 算术和数学算法：
      • std::accumulate：计算范围内所有元素的总和。
      • std::inner_product：计算两个序列元素的内积。
      • std::transform：对范围内的每个元素应用给定的函数。
   7. 容器修改算法：
      • std::erase：从容器中删除元素。
      • std::remove：从序列中移除符合特定条件的元素。
      • std::unique：移除序列中连续重复的元素。
   8. 查找和搜索算法：

      • std::binary_search：在已排序的范围内进行二分查找。

      • std::lower_bound：有序的情况下，找到大于等于给定值的第一个元素。使用二分查找

      • std::upper_bound：有序的情况下，找到大于给定值的第一个元素。使用二分查找

      • std::lower_bound和std::upper_bound的区别：

        	vector<int> nums = {1,2,2,2,3};
        	int index1 = lower_bound(nums.begin(), nums.end(), 2);
        	int index2 = upper_bound(nums.begin(), nums.end(), 2);

        index1的值为1，即nums中第一个2的下标；index2的值为4，nums中3的下标，也是第一个大于2的元素的下标。