本文共 21080 字，大约阅读时间需要 70 分钟。
STL(标准模板库)，是目前C++内置支持的library。它的底层利用了C++类模板和函数模板的机制，由三大部分组成：容器、算法和迭代器。
一、容器是STL中很重要的一种数据结构。常见的容器包括
1.vector容器
vector就是动态数组。在堆中分配内存,元素连续存放,有保留内存,如果减少大小后，内存也不会释放。
如果新值>当前大小时才会再分配内存。
它拥有一段连续的内存空间，并且起始地址不变，因此它能非常好的支持随即存取，即[]操作符，但由于它的内存空间是连续的，所以在中间进行插入和删除会造成内存块的拷贝。
当该数组后的内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。底层数据结构为数组 ，支持快速随机访问。
【vector总结】
需要经常随机访问请用vector
【vector的基本用法】
front()返回头部元素的引用，可以当左值
back()返回尾部元素的引用，可以当左值
push_back()添加元素，只能尾部添加
pop_back()移除元素，只能在尾部移除
int main(int argc, const char * argv[]) { //定义一个vector容器 vector v1; //插入元素(尾部插入) v1.push_back(1); v1.push_back(2); v1.push_back(3); //迭代器遍历打印 for (vector ::iterator it = v1.begin(); it != v1.end(); it++) { cout << *it << " "; } cout << endl; //修改头部元素的值(front()返回是引用，可以当左值) v1.front() = 44; //输出头部元素 cout<< "头部元素:" << v1.front() << endl; //修改尾部的值(back()返回是引用，可以当左值) v1.back() = 99; //输出尾部元素 cout << "尾部元素" << v1.back() < ::iterator it = v1.begin(); it != v1.end(); it++) { cout << *it << " "; } cout << endl; return 0;}复制代码
【vector的初始化】
vector有4种方式初始化，有直接初始化，也有通过拷贝构造函数初始化。
int main(int argc, const char * argv[]) { //直接构造函数初始化 vector v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); //通过拷贝构造函数初始化 vector v2 = v1; //使用部分元素来构造 vector v3(v1.begin(), v1.begin() + 1); vector v4(v1.begin(), v1.end()); //存放三个元素，每个元素都是9 vector v5(3,9); return 0;}复制代码 【vector的遍历】
vector的遍历有多种方式，可以根据[]或者迭代器遍历。
-
[]方式，如果越界或出现其他错误，不会抛出异常，可能会崩溃，可能数据随机出现
-
at方式，如果越界或出现其他错误，会抛出异常，需要捕获异常并处理
-
迭代器提供了逆向遍历，可以通过迭代器来实现逆向遍历，当然上面两种方式也可以
int main(int argc, const char * argv[]) { //创建vector vector v1; //插入元素 for (int i = 0; i < 10; i++) { v1.push_back(i); } //遍历-[]取值 for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } cout << endl; //遍历-at取值 for (int i = 0; i < v1.size(); i++) { cout << v1.at(i) << " "; } cout << endl; //遍历-迭代器遍历 for (vector ::iterator it = v1.begin(); it != v1.end(); it++) { cout << *it << " "; } cout << endl; //遍历-迭代器逆向遍历 for (vector ::reverse_iterator it = v1.rbegin(); it != v1.rend(); it++) { cout << *it << " "; } cout << endl; //测试越界 cout << "[]越界:" << v1[20] << endl; //不会抛出异常，可能会崩溃，可能会乱码 cout << "at越界:" << v1.at(20) << endl; //会抛出异常，需要捕获异常 return 0;}复制代码 【vector的push_back强化】
push_back是在当前vector的内存末尾拷贝元素进入容器。注意这个地方可能产生浅拷贝，所以容器中的对象要支持拷贝操作。另外，如果vector初始化了个数，而不初始化具体的值，push_back也只会在最后面追加。
int main(int argc, const char * argv[]) { //初始化10个元素的容器 vector v(10); //打印容器大小 cout << v.size() << endl; //push_back添加元素 v.push_back(100); //打印容器大小 cout << v.size() << endl; //遍历后的结果是 0 0 0 0 0 0 0 0 0 0 100 for (vector ::iterator it = v.begin(); it != v.end(); it++) { cout << *it << " "; } cout << endl; return 0;}复制代码 【vector的元素删除】
vector的删除，是根据位置进行删除，如果想要删除某个元素，需要找到当前元素的迭代器位置，再进行删除。
erase(iterator)函数，删除后会返回当前迭代器的下一个位置。
int main(int argc, const char * argv[]) { //1 创建容器并初始化 vector v1(10); for (int i = 0; i < v1.size(); i++) { v1[i] = i; } //2 区间删除 //--2.1 删除前3个元素 v1.erase(v1.begin(), v1.begin() + 3); //--2.2 删除指定位置的元素 v1.erase(v1.begin() +3); //3 根据元素的值进行删除,删除值为2的元素 v1.push_back(2); v1.push_back(2); vector ::iterator it = v1.begin(); while (it != v1.end()) { if (*it == 2) { it = v1.erase(it); //删除后，迭代器指针会执行下一个位置并返回。 }else{ it++; } } //4 遍历打印 for (vector ::iterator it = v1.begin(); it != v1.end(); it++) { cout << *it << " "; } cout << endl; return 0;}复制代码 【vector的插入元素】
vector提供了insert函数，结合迭代器位置插入指定的元素。如果迭代器位置越界，会抛出异常。
int main(int argc, const char * argv[]) { //初始化vector对象 vector v1(10); //在指定的位置插入元素10的拷贝 v1.insert(v1.begin() + 3, 10); //在指定的位置插入3个元素11的拷贝 v1.insert(v1.begin(), 3, 11); //遍历 for (vector ::iterator it = v1.begin(); it != v1.end(); it++) { cout << *it << " "; } cout << endl; return 0;}复制代码
2.list链表模型
list就是双向链表,在堆中存放,每个元素都是放在一块内存中,它的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随机存取变的非常没有效率，因此它没有提供[]操作符的重载。
但它可以以很好的效率支持任意地方的删除和插入。
list没有空间预留习惯,所以每分配一个元素都会从内存中分配,每删除一个元素都会释放它占用的内存.底层数据结构为双向链表，支持快速增删
【list总结】
如果你喜欢经常添加删除大对象的话,那么请使用list 要保存的对象不大,构造与析构操作不复杂,那么可以使用vector代替 list<指针>完全是性能最低的做法,这种情况下还是使用vector<指针>好,因为指针没有构造与析构,也不占用很大内存
【list的基本操作】
int main(int argc, const char * argv[]) { //创建list对象 list l; //尾部添加元素 for (int i = 0; i < 10; i++) { l.push_back(i); } //头部添加元素 l.push_front(111); //遍历 for (list ::iterator it = l.begin(); it != l.end(); it++) { cout << *it << " "; } cout << endl; //list不能随机访问 list ::iterator it = l.begin(); it++; it++; cout << *it < 【list的删除】
list提供了两个函数用来删除元素,分别是erase和remove。
erase是通过位置或者区间来删除,主要结合迭代器指针来操作
remove是通过值来删除
int main(int argc, const char * argv[]) { //创建list对象 list l; //添加数据 for (int i = 0; i < 10; i++) { l.push_back(i); } l.push_back(100); l.push_back(100); //删除头部元素 l.erase(l.begin()); //删除某个区间 list ::iterator it = l.begin(); it++; it++; it++; l.erase(l.begin(), it); //移除值为100的所有元素 l.remove(100); //遍历 for (list ::iterator it = l.begin(); it != l.end(); it++) { cout << *it << " "; } cout << endl; return 0;}复制代码
3.deque双端数组
[堆1] --> [堆2] -->[堆3] -->...
每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品.
它支持[]操作符，也就是支持随机存取，可以让你在前面快速地添加删除元素,或是在后面快速地添加删除元素,然后还可以有比较高的随机访问速度,和vector的效率相差无几。
它支持在两端的操作：push_back,push_front,pop_back,pop_front等，并且在两端操作上与list的效率也差不多。
在标准库中vector和deque提供几乎相同的接口,在结构上它们的区别主要在于这两种容器在组织内存上不一样,deque是按页或块来分配存储器的,每页包含固定数目的元素.相反vector分配一段连续的内存,vector只是在序列的尾段插入元素时才有效率,而deque的分页组织方式即使在容器的前端也可以提供常数时间的insert和erase操作,而且在体积增长方面也比vector更具有效率
【deque操作】
- push_back 从尾部插入元素
- push_front 从头部插入元素
- pop_back 从尾部删除元素
- pop_front 从头部删除元素
- distance函数可以求出当前的迭代器指针it距离头部的位置，也就是容器的指针，用法: distance(v1.begin(), it)
int main(int argc, const char * argv[]) { //定义deque对象 deque d1; //尾部插入元素 d1.push_back(10); d1.push_back(20); d1.push_back(30); //头部插入元素 d1.push_front(1); d1.push_front(2); d1.push_front(3); //尾部删除元素 d1.pop_back(); //头部删除元素 d1.pop_front(); //修改头部和尾部的值 d1.front() = 111; d1.back() = 222; //查找元素为1的下标 //通过distance求取下标 deque ::iterator it = d1.begin(); while (it != d1.end()) { if (*it == 1) { cout << "下标：" << distance(d1.begin(), it) << endl; } it++; } //遍历 for (deque ::iterator it = d1.begin(); it != d1.end(); it++) { cout << *it << " "; } cout << endl; return 0;}复制代码 【vector、list、deque总结】
vector是可以快速地在最后添加删除元素,并可以快速地访问任意元素
list是可以快速地在所有地方添加删除元素,但是只能快速地访问最开始与最后的元素
deque在开始和最后添加元素都一样快,并提供了随机访问方法,像vector一样使用[]访问任意元素,但是随机访问速度比不上vector快,因为它要内部处理堆跳转 deque也有保留空间.另外,由于deque不要求连续空间,所以可以保存的元素比vector更大,这点也要注意一下.还有就是在前面和后面添加元素时都不需要移动其它块的元素,所以性能也很高。
因此在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：
1、如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2、如果你需要大量的插入和删除，而不关心随即存取，则应使用list
3、如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。
4.stack栈模型
底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
▽ 基础数据类型的stack
int main(int argc, const char * argv[]) { //定义stack对象 stack s1; //入栈 s1.push(1); s1.push(2); s1.push(3); s1.push(4); //打印栈顶元素，并出栈 while (!s1.empty()) { //取出栈顶元素 cout << "当前栈顶元素" << s1.top() << endl; //获取栈的大小 cout << "当前栈的大小" << s1.size() << endl; //出栈 s1.pop(); } return 0;}复制代码 ▽ 复杂数据类型的stack
//定义类class Teacher { public: char name[32]; int age; void printT() { cout << "age = " << age << endl; } };int main(int argc, const char * argv[]) { Teacher t1, t2, t3; t1.age = 22; t2.age = 33; t3.age = 44; //定义栈容器 stack s1; //入栈 s1.push(t1); s1.push(t2); s1.push(t3); //出栈并打印 while (!s1.empty()) { //打印栈顶元素 Teacher tmp = s1.top(); tmp.printT(); //出栈 s1.pop(); } return 0;}复制代码
5.queue队列模型
底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时 （stack和queue其实是适配器,而不叫容器，因为是对容器的再封装）
#include void main(){ queue q; q.push(1); q.push(2); q.push(3); cout << "对头元素" << q.front() < q; q.push(t1); q.push(t2); q.push(t3); while (!q.empty()) { Teacher tmp = q.front(); tmp.printT(); q.pop(); }}复制代码
6.priotriy_queue优先级队列容器
底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现
优先级队列分为：最小值优先队列和最大值优先队列。
此处的最大值、最小值是指队头的元素（增序、降序）。默认，是创建最大值优先级队列。 定义优先级的方法：
priority_queue默认定义int类型的最大值队列
priority_queue<int, vector, less>定义int型的最大值优先队列
priority_queue<int, vector, greater>定义int型的最小值队列
上面的定义中，less和greater相当于谓词，是预定义好的排序函数，称之为“仿函数”。
void main(){ //定义优先级队列(默认是最大值优先级队列) priority_queue p1; //定义一个最大优先级队列 //less是提前定义好的预定义函数 相当于谓词 priority_queue