版本比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
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
queue
目录 |
---|