STL
基本概念
- STL（Standard Template Library，标准模板库）是惠普实验室开发的一系列软件的统称。
- STL 从广义上讲分为三类：algorithm（算法）、container（容器）和 iterator（迭代器），容器和算法通过迭代器可以进行无缝连接。几乎所有的代码都采用了模板类和模板函数的方式，这相比传统的函数和类组成的库来说提供了更好的代码重用机会。
- 在C++标准中，STL被组织为下面13个头文件：<algorithm>、<deque>、<functional>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<statck>和<utility>。
- 优点：
- STL是C++的一部分，不用额外安装什么，被内建在编译器之内
- STL的一个重要特点是数据结构和算法分离。
- 无需思考STL的具体实现过程，只要能够熟练使用STL就OK
- STL具有高可重用性，高性能，高移植性，跨平台的优点。
- 高可重用性：STL中几乎所有的代码都采用了模板和模板函数的方式实现
- 高性能：如map可以高效地从十万条记录里面查找出指定的记录，因为map是采用红黑树的变体实现的。
- 高移植性：在项目A上用STL编写的模块，可以移植到项目B上
- 跨平台：如用windows的Visual Studio编写的代码可以在Mac OS的XCode上直接编译
容器
容器的分类
- 序列式容器（Sequence containers）
- 每个元素都有固定位置 —— 取决于插入时机和地点，和元素值无关
- vector、deque、list、queue
- 关联式容器（Associated containers）
- 元素位置取决于特定的排序准则，和插入顺序无关
- set、multiset、map、multimap
| 数据结构 | 描述 | 实现头文件 |
| 向量（vector） | 连续存储的元素 | <vector> |
| 列表（list） | 由节点组成的双向链表，每个节点包含一个元素 | <list> |
| 双队列（deque） | 连续存储的指向不同元素的指针所组成的数组 | <deque> |
| 集合（set） | 由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用与元素对的谓词排列，不会出现两个相同的元素 | <set> |
| 多重集合（multiset） | 允许存在两个相同的元素的集合 | <set> |
| 栈（statck） | 先进后出的值的排列 | <statck> |
| 对列（queue） | 先进先出的值的排列 | <queue> |
| 优先队列（priority_queue） | 元素的次序是由作用与所存储的值 对上的某种谓词决定的一种队列 | <queue> |
| 映射（map） | 由键值对组成的集合，以某种作用于键 对上的谓词排列，不允许存在重复的键 | <map> |
| 多重映射（multimap） | 允许存在重复的键 | <map> |
vector容器
- 简介：
- vector是将元素置于一个动态数组中加以管理的容器
- vector可以随机存取元素（支持索引值直接存取，用[ ]操作符或at()方法）
- vector尾部添加或移除元素非常快速，但是在中部或头部插入元素或移除元素比较费劲
- vector对象的默认构造
- vector采用模板类实现，vector对象的默认构造形式：
- vector对象的带参数构造
- vector(beg,end); // 构造函数将数组 [beg, end)区间（实际是对应地址区间）中的元素赋值给本身。注意该区间是左闭右开的区间。
- vector(n, elem); // 构造函数将 n 个elem赋值给本身。
- vector(const vector &vec); // 拷贝构造函数
- vector的赋值
- vector.assign(beg, end); // 将数组 [beg, end)区间（实际是对应地址区间）中的元素赋值给本身，注意该区间是左闭右开的
- vector.assign(n, elem); // 构造函数将 n 个elem赋值给本身。
- vector & operator = (const vector &vec); // 重载等号操作符 （即调用等号）
- vector.swap(vec); // 两个vector的元素互换
- vector的大小
- vector.size(); // 返回容器中的元素个数
- vector.empty(); // 判断容器是否为空
- vector.resize(num); // 重新指定容器的长度为num，若容器边长，则以默认值填充新位置，若容器变短，则删除超出末尾的元素。
- vector.resize(num, elem); // 设置默认值为elem
- vector的访问
- vector支持 [ ] 直接访问，但是当[ ]内的下标越界时，程序有可能异常终止，且系统不会报任何错误信息，导致问题排查变得困难。 使用vector时，不推荐使用 [ ] 访问，而是期内置的函数at(idx)
- vec.at(idx); // 返回索引idx所指的数据，如果idx越界，抛出out_of_range异常
- vector的插入
- vector末尾的添加移除操作
- vec.push_back(elem); // 在vector末尾添加元素 elem
- vec.pop_back(); // 移除vector末尾的元素
- 在某位置插入
- vec.insert(pos, elem); // 在pos位置插入elem元素的拷贝，返回新数据的位置
- vec.insert(pos, n, elem); // 在pos位置插入n 个elem数据，无返回值
- vec.insert(pos, beg, end); // 在pos位置插入[ beg, end )区间的数据，无返回值
- vector末尾的添加移除操作
#include "iostream"
#include "vector"
using namespace std;void printVector(vector<int> vec);int main() {int arr1[] = {1, 2, 3, 4, 5};vector<int> v1(arr1,arr1 + 5); // 存储数组中的1到5cout << "v1:";printVector(v1);vector<int> v2(6,10); // 存储三个10cout << "v2:";printVector(v2);vector<int> v3(v1); // 拷贝cout << "v3:";printVector(v3);return 0;
}void printVector(vector<int> vec) {int length = vec.size();for (int i = 0; i < length; ++i) {if(i == 0) {cout << "[" << vec[i] << ",";}else if (i == length -1) {cout << vec[i] << "]" << endl;}else {cout << vec[i] << ",";}}
}
