C/C++中的STL

容器

vector

首先,vector是一个变长数组,元素属于顺序存储.
数组扩容,默认以倍增的思想进行扩容.在算法中,开辟动态内存的次数会极大影响算法的运算时间,这个时间主要是os为程序申请内存时的的内核态和用户态的堆栈切换导致的.所以能一次性分配完就不要频繁分配内存.
一般有两种扩容方法:

1. 定长扩容:每次扩容固定长度,如每次扩容 10 个元素空间。这种方式扩容后空间可能存在一定浪费,但扩容操作的时间复杂度固定(用于数据拷贝),为 O(n).扩容次数为O(n),总的时间复杂度为O(n^2)
2. 翻倍扩容:每次扩容将向量容量翻倍。这种方式空间利用率高,扩容操作时间复杂度为 O(n),扩容次数为O(logn),总的时间复杂度为O(nlogn).
   具体实现时,一般采用翻倍扩容方式:

void vector::expand() {
    // 记录原数组指针、容量和大小
    int* oldArr = arr;
    int oldCap = cap;
    int oldSize = size;
    
    // 新容量为原来的 2 倍
    int newCap = oldCap * 2;
    
    // 申请新内存
    arr = new int[newCap];
    
    // 拷贝原数据到新内存
    for (int i = 0; i < oldSize; i++) {
        arr[i] = oldArr[i]; 
    }
    
    // 释放原内存
    delete[] oldArr;
    
    // 更新容量
    cap = newCap;
    
    // 打印状态
    printf("expand: cap=%d, size=%d\n", cap, size);
} 
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

当向向量添加元素时,如果发现 size == cap(容量已满),就调用 expand() 方法进行扩容,然后再添加元素.
这个扩容方法(数组元素拷贝)的时间复杂度为 O(n),但由于采用翻倍扩容,所以总的扩容次数为 O(logn).总的时间复杂度为O(nlogn).而定长扩容的总的时间复杂度为O(n^2)

常用方法

size(); // 返回元素个数
empty(); //判断空
clear();//清空vector中的所有元素
push_back(); //向后增加
pop_back(); // 删除末尾
front()/back() //获得第一个和最后一个
Capacity() //表示vector容器预留的n个元素的空间.
[] //顺序索引,最为常用
begin()/end() //begin() 指向第0个元素的前一个元素,end()指向最后一个的下一个

1
2
3
4
5
6
7
8
9
10

reserve()

用于向该容器预留一定数量的内存空间。具体来说，它会调整容器的capacity大小，使得至少可以容纳指定数量的元素，但不会改变容器中实际元素的数量。这样做可以避免在后续插入元素时反复分配内存空间，提高程序效率。最常见的使用方法是在循环中使用，例如：

vector<int> vec;
vec.reserve(1000);
for (int i = 0; i < 1000; ++i) {
    vec.push_back(i); //插入元素，不会触发内存重新分配
}
1
2
3
4
5

reserve() 预先分配空间,优化开辟内存的时间.

vector的空间收缩

在vector执行push_back多次后,vector的容量capacity会越来越大.vector在内存的分配是连续的,若vector中只存在少量元素,则使得空间使用效率降低.
这时候就需要收缩内存空间:
清空 vector 容器，并释放它占用的内存空间，以便重新使用。一般情况下，当我们需要清空一个 vector 中的元素时，可以使用 v.clear() 函数来实现。但是，如果 vector 的容量很大，而其中的元素数量比较少，v.clear() 只会清空元素，但是并不会释放内存空间，因此可能会浪费一定的内存。

为了彻底释放 vector 占用的内存空间，可以使用如下代码：

vector<int>(v).swap(v);
1

这行代码的作用是创建一个临时的 vector 对象（拷贝了原始 vector 对象的所有元素），然后将这个临时对象与原始 vector 对象交换内存空间，最后临时对象被销毁，同时也将原始 vector 对象的内存空间释放掉了。由于交换后的 vector 容量大小不变，所以可以避免频繁地进行内存分配和释放，提高代码性能。

vector支持比较运算,按字典序

pair<类型,类型>

first,返回第一个元素
second,返回第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
pair相当于提供一个一个2个自定义类型的结构体,由此可以相互嵌套为多个对象的结构体.比如
pair > >

#include 

int main() {

    // 声明一个 pair,第一个元素是 string,第二个元素是 int
    pair<string, int> p("Hello", 10);

    // 访问 first 和 second
    cout << p.first << " " << p.second << endl;

    // 使用 make_pair() 函数构造 pair
    pair<int, double> p2 = make_pair(1, 2.5);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

string

size()/length()  返回字符串长度
empty()
clear()
substr(起始下标，(子串长度))  返回子串 
// substr 这一点和python,Java中不一样,第二个值指的是子串长度而不是截至位置(不包括)
c_str()  返回字符串所在字符数组的起始地址
[] 可通过序列去修改字符串中的单个字符 
支持+操作,拼接字符串或字符
//可当栈使用
pop_back()
push_back()
back() //相当于stack中的top操作


1
2
3
4
5
6
7
8
9
10
11
12
13
14

用例

	string a = "abcdef";
	a[0] = 'e';//索引赋值
	cout << a << endl;
	a += "abcd"; //拼接字符串
	a += 'a'; //拼接字符
	cout << a << endl;
	
	a.pop_back(); //弹栈
	cout << a << endl;
	a.push_back('p'); // 入栈 末尾添加
	cout << a.empty() << endl; //判空
	cout << a.back() << endl; //获取末尾
	cout << a.c_str() << endl;
1
2
3
4
5
6
7
8
9
10
11
12
13

stack

比较简单

size()
empty()
push()  向栈顶插入一个元素
top()  返回栈顶元素
pop()  弹出栈顶元素
1
2
3
4
5

queue/priority_queue

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列

size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)

set/multiset
insert()  插入一个数
find()  查找一个数
count()  返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x   O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x)  返回大于等于x的最小的数的迭代器
upper_bound(x)  返回大于x的最小的数的迭代器
map/multimap
insert()  插入的数是一个pair
erase()  输入的参数是pair或者迭代器
find()
[]  注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

unordered_map/unordered_set/unordered_multiset/unordered_multimap

基于哈希表实现
增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，–
lower_bound() 返回大于等于给定值的元素
upper_bound() 返回大于给定值的元素
在C++中，unordered_map是一个哈希表实现的关联容器，用于存储键值对，并支持快速插入、删除和查找操作。因为元素是键值对的形式,所以每一个插入的对象可以看作是pair类型.
以下是unordered_map常用的方法：

insert()：向unordered_map中插入一个键值对或一组键值对。
erase()：从unordered_map中删除指定键的元素。
clear()：清空unordered_map中的所有元素。
find()：查找给定键是否存在于unordered_map中，并返回指向该键的迭代器。
count()：统计给定键在unordered_map中出现的次数。
empty()：测试unordered_map是否为空。
size()：返回unordered_map中元素的数量。
at()：返回给定键所对应的值，如果键不存在，则抛出异常。
[]：通过给定键访问元素的值，如果键不存在，则自动插入一个新元素.(最为常用的操作)
另外，unordered_map还支持遍历操作，可以使用迭代器或者范围循环遍历元素。
1
2
3
4
5
6
7
8
9
10

例如，下面是一个使用unordered_map的示例程序，演示了一些常用的方法：

#include 
#include 

using namespace std;

int main() {
    // 创建一个 unordered_map 对象
    unordered_map<int, int> map1;

    // 向 unordered_map 中插入元素
    map1.insert({1, 10});
    map1.insert({2, 20});
    map1[3] = 30;

    // 遍历 unordered_map
    for (auto& kv : map1) {
        cout << "key=" << kv.first << ", value=" << kv.second << endl;
    }

    // 查找和访问 unordered_map 中的元素
    auto it = map1.find(2);
    if (it != map1.end()) {
        cout << "map1[2]=" << it->second << endl;
    }

    // 删除 unordered_map 中的元素
    int n = map1.erase(3);
    cout << "删除元素个数：" << n << endl;

    // 判断 unordered_map 是否为空
    if (map1.empty()) {
        cout << "unordered_map is empty." << endl;
    } else {
        cout << "unordered_map size: " << map1.size() << endl;
    }

    return 0;
}
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
STL提供了大量的算法模板,这些算法模板可以和lambda表达式充当回调函数发挥很大的作用.

1. 非变容算法:对序列不做更改,主要用于查找、计数和遍历操作。常用的有:
- find():查找元素
- count():计数
- for_each():遍历
1. 变容算法:会更改序列内容。常用的有:
- copy():复制
- remove():移除
- replace():替换
- reverse():反转
- sort():排序
1. 二分查找算法:用于在有序序列中快速查找元素。常用的有:
- binary_search():二分查找
- lower_bound():第一个不小于的元素
- upper_bound():第一个大于的元素
1. 数值算法:用于对数值类型数据执行一些基本运算。常用的有:
- accumulate():累加
- max():最大值
- min():最小值
1. 堆算法:用于创建堆和堆操作。常用的有:
- make_heap():创建堆
- push_heap():添加元素
- pop_heap():移除元素
1. 其他常用算法:
- swap():交换两个元素
- next_permutation():计算下一个排列
- prev_permutation():计算上一个排列
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

列举下常用的

sort排序

sort(v.beign(),v.end(),lambda表达式/模板参数/函数指针).

#include 
int main() {



	vector<pair<int, int>> a = { {1181,2},{3,92},{21,0},{43,222},{43,212},{3,22} };

	sort(a.begin(), a.end(), [](pair<int, int> a, pair<int, int>b) {

		if (a.first < b.first) return true;   //按pair的第一个元素从小倒大进行排序
		else if (a.first == b.first) return a.second < b.second; // 第一个元素相同则按第二个元素从小到大排序
		else
			return false;
		       
		});
	print(a);


    //或者一下写法
    //vector中比较默认就是按字典序从小到大排序,若第一个元素相同,则按第二个元素的字典序排列.


    
	vector<pair<int, int>> a = { {1181,2},{3,92},{21,0},{43,222},{43,212},{3,22},{1181,0} };

	sort(a.begin(), a.end());
	print(a);
 
 

    


};
 

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

sort应用 指定某个元素放到最后,其余元素从小到大排序

	std::vector<int> v = { 1,2,13,2 };

	//std::sort(v.begin(), v.end(),std::greater()); //从大到小排序
	 //13放到最后,其余元素从小到大排序
	std::sort(v.begin(), v.end(), [](int a, int b) {

		if (a == 13)return false;  
		if (b == 13) return  true; 
		return a < b;//从小到大进行排序

		/*   -如果a == 13, 返回false, 意思是a不会被视为"更小"的那个元素。
			 - 如果b == 13, 返回true, 意思是b会被视为"更小"的那个元素。
			 - 否则, 执行正常的从小到大比较, a < b。*/

		});
	for (int i = 0; i < v.size(); i++) {
		std::cout << v[i] << "\n";
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

reserve 逆序

reserve(v.begin(), v.end());

erase删除

迭代器

一般的迭代器遍历情况

vector<int>a(5, 12);

 
	for (vector<int> ::iterator it = a.begin(); it != a.end();it++) {
		cout << *it << endl;
	}
  //或者
  	for (auto it : a) {
		cout << it << endl;
	}

 
1
2
3
4
5
6
7
8
9
10
11
12

迭代器失效情况

• 对于序列式容器(如vector,deque)，序列式容器就是数组式容器，删除当前的iterator或者插入某个iterator会使后面所有元素的iterator都失效。这是因为vetor,deque使用了连续分配的内存，删除或插入一个元素导致后面所有的元素会向前或向后移动一个位置。所以不能使用erase(iter++)的方式，还好erase，insert方法可以返回下一个有效的iterator。

解决方法：
（1）通过erase方法的返回值来获取下一个有效的迭代器，如下例。
（2）在调用erase之前，先使用‘++’来获取下一个有效的迭代器
1
2
3

• 链表型数据结构（list）
  使用了不连续分配的内存，删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器。还好erase，insert方法可以返回下一个有效的iterator。
  解决方法：
  通过erase方法的返回值来获取下一个有效的迭代器.

• 树形数据结构（map、set、multimap,multiset）
  删除当前的iterator，仅仅会使当前的iterator失效，只要在erase时，递增当前iterator即可。这是因为map之类的容器，使用了红黑树来实现，插入、删除一个结点不会对其他结点造成影响。erase迭代器只是被删元素的迭代器失效，但是返回值为void，所以要采用erase(iter++)的方式删除迭代器。

解决方法：
（1）采用erase(iter++)的方式删除迭代器。如下第一个例子：
（2）在调用erase之前，先使用‘++’来获取下一个有效的迭代器

参考
https://www.acwing.com/blog/content/404/