- 由 zhongluqiang创建, 最后修改于3月 24, 2022
STL基本概念
- 容器:用于存放数据的类模板,比如vector, list, stack, queue等。
- 迭代器:用于存取容器中存放的元素,可以理解成指针,用于遍历和操作容器。使用迭代器可以实现以相同的风格访问和操作大部分的容器。
- 算法:用来操作容器中元素的函数模板,比如sort, unique等。
容器
用于存放元素,实例化时指定元素类型。如果存储的是一个对象,那么最好重载==
和<
运算,因为大部分算法都会用这两个运算符来进行相等判断和排序。
容器分为两大类:
顺序容器:可变长动态数组vector、双端队列deque、双向链表list。顺序容器的元素具有前后关系,可指定位置插入和删除。
关联容器:set、multiset、map、multimap。关联容器的元素是排序过的,不能指向插入位置。插入的元素会自动排序。默认情况下,关联容器中的元素按从小到大排序,使用运算符"<"进行比较。关联容器在查找时有很好的性能。
容器适配器:栈stack、队列queue、优先队列priority_queue。在上两类容器的基础上屏蔽一部分功能,突出或增加另一部分功能。
任何两个容器对象,只要类型相同,就可以用<、<=、>、>=、==、!=进行字典式的比较,它们的运行规则如下:
a == b: a和b中的元素个数相同,且对应元素相等,使用==运算符。
a < b: 类似于单词的字典序比较,使用<运算符。
a != b: 等价于!(a == b)。
a > b: 等价于 b < a。
a <= b:等价于 !(b < a)。
a >= b: 等价于!(a < b)。
所有的容器都有以下两个成员函数:
int size():返回容器对象中元素的个数。
bool empty():判断容器对象是否为空。
顺序容器和关联容器还有以下成员函数:
begin(): 返回指向容器第一个元素的迭代器。
end(): 返回指向容器最后一个元素后面的位置的迭代器。
rbegin(): 返回指向容器最后一个元素的反向迭代器。
rend(): 返回指向容器第一个元素前面的位置的迭代器。
erase(): 删除一个或几个元素。
clear(): 删除所有元素。
顺序容器还有以下常用成员函数:
front(): 返回容器中第一个元素的引用。
back(): 返回容器中最后一个元素的引用。
push_back(): 在容器末尾增加新的元素。
pop_back(): 删除容器末尾的元素。
insert(): 插入一个或多个元素。
迭代器
用于访问容器中的元素,有以下四种:
1. 正向迭代器,定义方法如下:
容器类名::iterator 迭代器名;
2. 常量正向迭代器,定义方法如下:
容器类名::const_iterator 迭代器名;
3. 反向迭代器,定义方法如下:
容器类名::reverse_iterator 迭代器名;
4. 常量反向迭代器,定义方法如下:
容器类名::const_reverse_iterator 迭代器名;
注意,容器适配器stack、queue和priority_queue没有迭代器,它们有自己的方法用于访问元素。
不同的容器的迭代器功能有强弱之分,这决定了容器是否支持某种STL算法,比如,排序算法sort需要通过迭代器支持随机访问功能,如果某种容器不支持随机访问,如list,那就不支持使用sort进行排序。
常用的迭代器按功能强弱分为输入、输出、正向、双向、随机访问5种:
正向迭代器:支持++p和p++、*p,两个迭代器可以赋值,可以用==和!=比较;
双向迭代器:支持正向迭代器的全部功能,还支持--p和p--;
随机访问迭代器:在双向迭代器的基础上,支持 p+i、p-i、p+=i、p-=i、p[i],还支持 <、>、<=、>=比较。
不同容器的迭代器功能:
容器 | 迭代器功能 |
---|---|
vector | 随机访问 |
deque | 随机访问 |
list | 双向 |
set/multiset | 双向 |
map/multimap | 双向 |
stack | 不支持 |
queue | 不支持 |
priority_queue | 不支持 |
迭代器的辅助函数:
advance(p, n): 使迭代器向前或向后移动n个元素。
distance(p, q): 计算两个迭代器之间的距离,即p经过多少次++后和q相等,如果p本身就在q后面,则这个函数会陷入死循环。
iter_swap(p, q): 用于交换两个迭代器q、q指向的值,相当于通过指针交换元素内容。
算法
能在各种容器上通用的函数模板,通过迭代器来操作元素。
大部分算法需要通过迭代器提供一个操作区间,比如begin()~end()。
有的算法返回一个迭代器,比如find算法。
排序、查找等算法需要对元素进行比较,比较判断大小及是否相等。在STL中,比较大小通过"<"运算符来实现,和">"无关。而比较相等时,并不一定是使用"=="运行符,而是要根据情况来确定。如果是在未排序的区间上应用find进行查找,那么使用"=="运算符来判断相等。如果是在已经排序好的区间上进行查找、合并等操作(比如折半查找算法binary_search,关联容器自身的find成员函数),那么判断x=y的条件是x<y和y<x同时为假。如果一个类将"<"运算符重载为永远返回false,那么对于STL算法来说,这个类的所有对象都是相等的。
vector
可变长数组,支持以下迭代器:
- begin()/end()
- rbegin()/rend()
- cbegin()/cend()
- crbegin()/crend()
支持以下容量相关的操作:
- size()
- empty()
- resize()
- reserve()
- capacity()
注意:size()和resize()是配套的,用于调整数组的实际大小,调小时截断,调大时补零。reserve()和capacity()是配套的,用于调整数组的预分配空间大小,这个大小不影响数组的内容和size()的返回值。如果对性能要求不高,那么完全不需要调用reserve()来预分配空间,而是只使用vector默认的增长策略。
支持以下元素访问操作:
- 下标操作符[]
- front()
- back()
注意front()和back()都是返回引用,也就是可以直接通过这两个函数的返回值来修改元素。
支持以下修改操作:
- push_back()
- pop_back()
- insert()
- erase()
- clear()
以下是vector的一些示例操作:
#include <iostream> #include <vector> using namespace std; int main() { vector<int> v1{1, 2, 3, 4, 5}; cout << "size:" << v1.size() << endl; // 5 cout << "capacity:" << v1.capacity() << endl; // 5 v1.reserve(15); cout << "size:" << v1.size() << endl; // 5 cout << "capacity:" << v1.capacity() << endl; // 15 v1.resize(10); cout << "size:" << v1.size() << endl; // 10, 后面的5个元素值为全零 cout << "capacity:" << v1.capacity() << endl; // 15 v1.resize(5); // 截断后面5个元素 // 正向遍历 for(auto it = v1.begin(); it != v1.end(); it++) { cout << *it << endl; } cout << endl; // 反向遍历,注意it仍为++ for(auto it = v1.rbegin(); it != v1.rend(); it++) { cout << *it << endl; } cout << endl; // 访问元素 v1.front(); v1.front() = 0; v1.back(); v1.back() = 6; // 修改元素 v1.push_back(6); v1.pop_back(); for(auto it = v1.begin(); it != v1.end(); it++) { cout << *it << endl; } cout << endl; // insert v1.insert(v1.begin(), -1); // 在指定位置之前插入 v1.insert(v1.end(), 7); v1.insert(v1.begin(), 5, -2); // 批量插入 { vector<int> tmp{8, 9, 10}; v1.insert(v1.end(), tmp.begin(), tmp.end()); // 在指定位置插入一个区间的值 } for(auto it = v1.begin(); it != v1.end(); it++) { cout << *it << endl; } cout << endl; // erase v1.erase(v1.begin()); // 删除当前位置的元素 v1.erase(v1.begin(), v1.begin() + 4); // 删除一个区间的元素 for(auto it = v1.begin(); it != v1.end(); it++) { cout << *it << endl; } cout << endl; return 0; }
list
与vector同为顺序容器,但是不支持随机访问,其访问过程只能是从前往后遍历或是从后往前遍历。
支持的迭代器如下:
- begin()/end()
- rbegin()/rend()
- cbegin()/cend()
- crbegin()/crend()
以上迭代器只支持双向操作,也就是it++
和it--
,不支持随机访问,比如it+n
。
容量相关的操作如下:
- size()
- empty()
元素访问:
- front()
- back()
修改元素:
- push_front()
- pop_front()
- push_back()
- pop_back()
- insert()
- resize()
上面的resize()和vector的resize()类似,用于重新分配大小,不够补上空的元素,多了截断多余的元素。
示例代码:
#include <iostream> #include <list> using namespace std; int main() { list<int> a{1, 2, 3, 4, 5}; for(auto it = a.begin(); it != a.end(); it++) { cout << *it << endl; } cout << endl; // 前后插入/删除元素 a.pop_front(); a.pop_back(); a.push_front(0); a.push_back(6); for(auto it = a.begin(); it != a.end(); it++) { cout << *it << endl; } cout << endl; // 删除单个元素 for(auto it = a.begin(); it != a.end(); it++) { if(*it == 3) { a.erase(it); break; // 这里必须break,因为it被删除后已经被回收了,不再指向下一个元素 } } // 循环体中删除元素 auto it = a.begin(); while(it != a.end()) { if(*it == 2) { it = a.erase(it); // 返回删除元素的下一个元素 } else { it++; } } for(auto it = a.begin(); it != a.end(); it++) { cout << *it << endl; } cout << endl; return 0; }
queue/deque
queue和deque都是队列,用于先进先出操作,不同的是queue只能在一头插入,在另一头弹出,而deque两头都可以插入和弹出,通过比较它们支持的方法即可分辨出区别:
queue支持的方法:
push(); pop(); front(); back(); size(); empty(); clear();
deque支持的方法:
push_front(); push_back(); pop_front(); pop_back(); front(); back(); size(); empty(); clear();
stack
先进后出,支持以下方法:
push(); pop(); top(); size(); emtpy();
注意stack不支持清空操作!!!如果要清空一个队列,可以将其与一个空的队列进行swap。
- 无标签