C++ STL详解（1）

深藏阁楼爱情的钟 2022-10-30 12:24 133阅读 0赞

**上一篇博客：[哈希表][Link 1]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  概述
 *  刷题时常用的STL
 *   *  vector
     *   *  初始化
         *  size()
         *  empty()
         *  push\_back()
         *  pop\_back()
         *  clear()
         *  front()、back()
         *  begin()、end()
         *  operator\[\]
         *  vector的三种遍历方式
         *  支持比较运算
     *  pair
     *   *  定义方式
         *  初始化
         *  构造pair
         *  访问
         *  支持比较运算
         *  嵌套pair
     *  stack
     *   *  使用数组模拟栈
     *  queue
     *   *  使用数组模拟队列

# 概述 #

>  STL 是“Standard Template Library”的缩写，中文译为“标准模板库”。STL 是 C++ 标准库的一部分，不用单独安装。  
>  C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。例如，vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环队列，set 的底层为红黑树，hash\_set 的底层为哈希表。  
>  STL 从根本上讲是“容器”的集合，也是组件的集合。容器包括 list、vector、set、map 等；组件包括迭代器等。STL 的目的是标准化组件。  
>  STL 是 C++ 的一部分，不用额外安装，被内建在支持 C++ 的编译器中。  
> STL 的算法是标准算法，其实现了将已经定义好的算法应用在容器的对象上。

更多STL介绍请看 [STL是什么][STL]

# 刷题时常用的STL #

通过概述可以了解到STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。所以在刷题时配合使用 **STL** 可以极大的提高做题的速度。可以根据情况来选择使用 **STL** 来做题目，如果题目对时间要求比较高的话可以不使用 **STL**，比如栈和队列可以使用数组来进行模拟等等。一般情况下可以直接选择使用STL来做题目。

## vector ##

之前写过一篇介绍 `vector` 的博客： [C++STL之vector详解][C_STL_vector] 这里再补充说明一下。

### 初始化 ###

*  定义一个vector  
     一般情况下直接定义一个默认初始长度的 vector 即可。当插入的长度超过这个默认长度时vector会自动扩容。

vector<int> v;

*  在定义时初始化vector的长度  
     vector 可以一开始不定义大小，之后用 resize 方法分配大小，也可以一开始就定义大小，之后还可以对它插入删除动态改变它的大小。不管在 main 函数里还是在全局中定义，它都能够直接将所有的值初始化为0 (不用显式地写出来，默认就是所有的元素为0)

**注意：** 系统为某一程序分配空间时所需的时间与空间大小无关，而与分配的次数有关。所以尽量减少申请空间的次数，也有利于提高程序的效率。

在vector的扩展大小中有一个 **倍增思想**：假如vector的实际长度为 n ，m为vector当前的最大长度，那么在加入一个元素的时候，先看一下，假如当前的 n = m，则再动态申请一个 2m 大小的内存。反之，在删除的时候，如果 n ≤  m ÷ 2 m\\div2 m÷2，则再释放一半的内存。基于该思想，如果长度为 **n** 的vector数组，假设一开始只申请了一个空间，那么最后其申请的次数是  l o g ( n ) log(n) log(n) 的，所以vector是一种效率比较高的数组。

#include<iostream>
    #include<vector>
    using namespace std;
    
    int main() { 
    	vector<int> v(10); // 定义一个长度为 10 的 vector 
    	for (int i = 0; i < 10; i++) cout << v[i] << ' ';
    	// 输出结果: 0 0 0 0 0 0 0 0 0 0 
    	return 0;
    }

*  在定义时对vector的内容进行初始化  
     vector不仅可以支持在定义初始化长度，也支持初始化内容

#include<iostream>
    #include<vector>
    using namespace std;
    
    int main() { 
    	vector<int> v(10, 9); 
    	// 定义一个长度为 10 的 vector,并且将所有的内容都初始化为 9 
    	for (int i = 0; i < 10; i++) cout << v[i] << ' ';
    	// 输出结果: 9 9 9 9 9 9 9 9 9 9 
    	return 0;
    }

*  定义一个vector数组  
     可以通过定义vector数组的方式一次定义多个vector。相当于定义了一个行数确定，列数不确定的二维数组。

#include<iostream>
    #include<vector>
    using namespace std;
    
    int main() { 
    	vector<int> v[10]; 
    	int cnt = 1;
    	for (int i = 0; i < 5; i++) { 
    		for (int j = 0; j < 5; j++) { 
    			v[i].push_back(cnt++);
    		}
    	}
    	
    	for (int i = 0; i < 5; i++) { 
    		for (int j = 0; j < 5; j++) { 
    			cout << v[i][j] << ' ';
    		}
    		cout << endl;
    	}
    
    	return 0;
    }

*  定义一个不定长的二维数组  
     还可以使用 `vector<<vector<int> >` 的方式定义一个行和列都不定长的二维数组。注意最后两个 `>` 不要写在一块，否则可能会被一些编译器认为是 `>>` 运算符。

#include<iostream>
    #include<vector>
    using namespace std;
    
    int main() { 
    	vector<vector<int> > v; 
    	int cnt = 1;
    	// 输入 5 行正数，每行数字以 -1 结束输入 
    	for (int i = 0; i < 5; i++) { 
    		vector<int> q;
    		int x;
    		cin >> x;
    		while (x != -1) { 
    			q.push_back(x);
    			cin >> x;
    		}
    		v.push_back(q);
    	}
    	
    	cout << "输出的结果为:" << endl;	
    	for (int i = 0; i < v.size(); i++) { 
    		for (int j = 0; j < v[i].size(); j++) { 
    			cout << v[i][j] << ' ';
    		}
    		cout << endl;
    	}
    
    	return 0;
    }

### size() ###

size() ：返回vector中元素的个数，时间复杂度 `O(1)`。

**注意：** 对于顺序容器size() 的时间复杂度为 O(1)，对于list之类的节点容器，可能是线性时间即 O(n)。所以在 for 循环中需要求长度时最好把 size() 放到循环之外求，这样可以在一些情况下将算法的时间复杂度由 O( n 2 n^2 n2) 降到 O(n)。

#include<iostream>
    #include<vector>
    using namespace std;
    
    int main() { 
    	vector<int> v(10, 9); 
    	// 定义一个长度为 10 的 vector,并且将所有的内容都初始化为 9 
    	cout << "数组中元素的个数为：" << v.size() << endl;
    	int len = v.size();
    	for (int i = 0; i < len; i++) cout << v[i] << ' ';
    	// 输出结果: 9 9 9 9 9 9 9 9 9 9 
    	return 0;
    }

### empty() ###

empty() ：**v.empty()** 检查数组 **v** 是否为空。若容器为空则返回 `true` ，否则返回 `false`

### push\_back() ###

向vector的最后插入一个元素

### pop\_back() ###

删除vector的最后一个元素

#include<iostream>
    #include<vector>
    using namespace std;
    
    int main() { 
    	vector<int> v; 
    	v.push_back(1);
    	v.push_back(2);
    	v.push_back(3);
    	for (int i = 0; i < 3; i++) cout << v[i] << ' ';
    	// 输出 1 2 3 
    	cout << endl;
    	v.pop_back();
    	for (int i = 0; i < 3; i++) cout << v[i] << ' ';
    	// 输出 1 2 3
    	cout << endl;
    	for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
    	// 输出 1 2
    	return 0;
    }

通过以上实验可知，使用 **pop\_back()** 并不是真正的将最后一个元素删除了，只是修改了vector的末尾指针。

### clear() ###

清空数组中的所有元素

#include<iostream>
    #include<vector>
    using namespace std;
    
    int main() { 
    	vector<int> v; 
    	v.push_back(1);
    	v.push_back(2);
    	v.push_back(3);
    	cout << "数组的元素个数为:" << v.size() << endl; 
    	for (int i = 0; i < v.size(); i++) cout << v[i] << ' '; 
    	cout << endl;
    	v.clear();
    	cout << "数组的元素个数为:" << v.size();
    	return 0;
    }

### front()、back() ###

front()访问vector的第一个元素，back() 返回最后一个元素。

#include<iostream>
    #include<vector>
    using namespace std;
    
    int main() { 
    	vector<int> v; 
    	v.push_back(1);
    	v.push_back(2);
    	v.push_back(3);
    	cout << "数组的第一个元素为:" << v.front() << endl; 
    	cout << "数组的最后一个元素为:" << v.back() << endl;
    	return 0;
    }

### begin()、end() ###

begin() 返回指向容器首元素的迭代器。若容器为空，则返回的迭代器将等于 end() 。end() 返回指向容器末元素后一元素的迭代器，即指向vector中最后一个元素之后的一个元素。`此元素表现为占位符；试图访问它导致未定义行为。`  
![示意图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_000000_t_70]

### operator\[\] ###

vector支持随机寻址，像数组一样。operator\[pos\]返回位于指定位置 pos 的元素的引用。不进行边界检查。在上面的例子中已经用到很多次了，比如： `v[i]` 表示访问vector中下标为 **i** 的元素。这里就不再演示了。

### vector的三种遍历方式 ###

1.  使用随机寻址的方式遍历
2.  范围遍历
3.  迭代器方式遍历

#include<iostream>
    #include<vector>
    using namespace std;
    
    int main() { 
    	vector<int> v; 
    	for (int i = 0; i < 10; i++) v.push_back(i);
    	// 使用随机寻址的方式遍历 
    	for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
    	cout << endl;
    	
    	// 使用范围遍历 
    	for (int i : v) cout << i << ' ';
    	cout << endl;
    	
    	// 使用迭代器遍历 
    	for (vector<int>::iterator i = v.begin(); i != v.end(); i++) cout << *i << ' ';
    	// 输出 1 2
    	return 0;
    }

### 支持比较运算 ###

vector可以支持比较运算，可以直接比较两个vector的大小。vector支持 `==, !=, <, <=, >, >=` 运算符。

1.  检查两个vector的内容是否相等，即它们是否拥有相同数量的元素且 **vector1** 中每个元素与 **vector2** 的同位置元素比较相等。
2.  按 `字典序` 比较 **vector1** 与 **vector2** 的内容。

#include<iostream>
    #include<vector>
    using namespace std;
    
    int main() { 
    	vector<int> a(6, 5), b(5, 6); 
    	if (a > b) cout << "a > b";
    	else cout << "b > a";
    	// 输出结果： b > a
    	return 0;
    }

## pair ##

**pair** 是一个结构体模板，其可于一个单元存储两个相异对象。

### 定义方式 ###

pair 的定义方式为：`pair<int, int>`，其中的两个参数可以是任意的，比如 **int、string、double、float** 等等。

### 初始化 ###

可以在定义**pair**的时候直接初始化**pair**。

#include<iostream>
    using namespace std;
    
    int main() { 
    	pair<int, string> p(1, "AC-fun");
    	cout << p.first << ":" << p.second;
    	return 0;
    }

### 构造pair ###

pair 有两种构造方式：

1.  使用 **make\_pair()** 创建一个 pair 对象，其类型根据各实参类型定义。

#include<iostream>
    using namespace std;
    
    int main() { 
    	pair<int, string> p;
    	p = make_pair(1, "AC-fun");
    	cout << p.first << ":" << p.second;
    	return 0;
    }

1.  在 C++ 11 中还可以直接构造。

#include<iostream>
    using namespace std;
    
    int main() { 
    	pair<int, string> p;
    	p = { 1, "AC-fun"};
    	cout << p.first << ":" << p.second;
    	return 0;
    }

### 访问 ###

pair 以 **first** 为第一个关键字，以 **second** 为第二个关键字。例如现在已经构造好了一个 `pair<int, string> p(1, "AC-fun");` 可以使用 **p.first** 访问第一个关键字，使用 **p.second** 访问第二个关键字。

#include<iostream>
    using namespace std;
    
    int main() { 
    	pair<int, string> p(1, "AC-fun");
    	cout << p.first << ":" << p.second;
    	return 0;
    }

### 支持比较运算 ###

pair 与 vector 一样，也是可以支持比较运算的。pair支持 `==, !=, <, <=, >, >=` 运算符。按照 `字典序` 进行排序。

### 嵌套pair ###

如果有一种东西有三种属性，可以使用嵌套的pair来存储。比如：

pair<int, pair<int, string> >

## stack ##

关于 **栈** 在之前的博客： [数据结构——栈的详解][Link 2] 已经详细介绍过了，这里就不再赘述了。在开头提到了可以使用数组模拟栈，这里就只贴一下代码。思路与 [数据结构——栈的详解][Link 2] 文章中一样。

### 使用数组模拟栈 ###

#include<iostream>
    #include<string>
    using namespace std;
    
    const int N = 100010;
    int stk[N], tt; // tt为栈顶指针 
    
    // 在栈顶添加一个元素 
    void add(int x) { 
        stk[tt++] = x;
    }
    
    // 弹出栈顶元素 
    void remove() { 
        tt--;
    }
    
    // 取栈顶元素 
    int top() { 
        return stk[tt - 1];
    }
    
    // 判断栈是否为空 
    bool ept() { 
        if (tt) return false;
        else return true;
    }
    
    int main() { 
        int n;
        cin >> n;
        while (n--) { 
            string op;
            int x;
            cin >> op;
            if (op == "push") { 
                cin >> x;
                add(x);
            } else if (op == "pop") { 
                remove();
            } else if (op == "empty") { 
                if (ept()) { 
                    cout << "YES" << endl;
                } else { 
                    cout << "NO" << endl;
                }
            } else { 
                cout << top() << endl;
            }
        }
    
        return 0;
    }

## queue ##

关于 **队列** 在之前的博客： [数据结构——队列的详解][Link 3] 也已经详细介绍过了。这里贴一下数组模拟队列的代码。

### 使用数组模拟队列 ###

#include<iostream>
    #include<string>
    using namespace std;
    
    const int N = 100010;
    int q[N], front, tail; // front为队头指针，tail为队尾指针 
    
    // 在队尾添加一个元素 
    void add(int x) { 
        q[tail++] = x;
    }
    
    // 移除队头元素 
    void remove() { 
        front++;
    }
    
    // 判空
    bool ept() { 
        if (front == tail) return true;
        return false;
    }
    
    // 返回队头元素
    int qey() { 
       return q[front]; 
    }
    
    int main() { 
        int n;
        cin >> n;
        while (n--) { 
            string op;
            int x;
            cin >> op;
            if (op == "push") { 
                cin >> x;
                add(x);
            } else if (op == "pop") { 
                remove();
            } else if (op == "empty") { 
                if (ept()) cout << "YES" << endl;
                else cout << "NO" << endl;
            } else { 
                cout << qey() << endl;
            }
        }
        return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![20210219220302498.png][]

[Link 1]: https://ac-fun.blog.csdn.net/article/details/113844432
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[STL]: http://c.biancheng.net/view/1436.html
[C_STL_vector]: https://ac-fun.blog.csdn.net/article/details/105507724
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_000000_t_70]: /images/20221024/f3f8510983284876824365c76b7c2d0a.png
[Link 2]: https://ac-fun.blog.csdn.net/article/details/105619109
[Link 3]: https://ac-fun.blog.csdn.net/article/details/105650259
[20210219220302498.png]: /images/20221024/650e7b7dc83145d4a6bb16e037ca6620.png