c++的STL学习笔记
在实际的开发过程中,合理组织数据的存取与选择处理数据的算法同等重要,存取数据的方式往往会直接影响到对它们进行增删改查操作的复杂程度和时间消耗。事实上,当程序中存在对时耗要求很高的部分时,数据结构的选择就显得尤为重要,有时甚至直接影响程序执行的成败。
值得一提的是,之前我们一直在不断地重复实现一些诸如链表、集合等等这些常见的数据结构,这些代码使用起来往往都十分类似,只是为了适应不同数据的变化,可能需要在一些细节上做不同的处理。
那么大家有没有想过,是不是可以重复利用那些已有的实现来完成当前的任务呢?当然是可行的,有些读者已经亲自编写并实现了动态数组类、链表类、集合类等程序,并精心维护着。其实,STL 中提供了专家级的几乎我们所需要的各种容器,功能更好,复用性更高。
简单的理解容器,它就是一些模板类的集合,但和普通模板类不同的是,容器中封装的是组织数据的方法(也就是数据结构)。STL 提供有 3 类标准容器,分别是序列容器、排序容器和哈希容器,其中后两类容器有时也统称为关联容器。它们各自的含义如表 1 所示。
容器种类 | 功能 |
---|---|
序列容器 | 主要包括 vector 向量容器、list 列表容器以及 deque 双端队列容器。之所以被称为序列容器,是因为元素在容器中的位置同元素的值无关,即容器不是排序的。将元素插入容器时,指定在什么位置,元素就会位于什么位置。 |
排序容器 | 包括 set 集合容器、multiset多重集合容器、map映射容器以及 multimap 多重映射容器。排序容器中的元素默认是由小到大排序好的,即便是插入元素,元素也会插入到适当位置。所以关联容器在查找时具有非常好的性能。 |
哈希容器 | C++ 11 新加入 4 种关联式容器,分别是 unordered_set 哈希集合、unordered_multiset 哈希多重集合、unordered_map 哈希映射以及 unordered_multimap 哈希多重映射。和排序容器不同,哈希容器中的元素是未排序的,元素的位置由哈希函数确定。 |
注意,由于哈希容器直到 C++ 11 才被正式纳入 C++ 标准程序库,而在此之前,“民间”流传着 hash_set、hash_multiset、hash_map、hash_multimap 版本,不过该版本只能在某些支持 C++ 11 的编译器下使用(如 VS),有些编译器(如 gcc/g++)是不支持的。
另外,以上 3 类容器的存储方式完全不同,因此使用不同容器完成相同操作的效率也大不相同。所以在实际使用时,要善于根据想实现的功能,选择合适的容器。
常用的迭代器按功能强弱分为输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器 5 种。
输入迭代器和输出迭代器比较特殊,它们不是把数组或容器当做操作对象,而是把输入流/输出流作为操作对象。
-
前向迭代器(forward iterator) 假设 p 是一个前向迭代器,则 p 支持 ++p,p++,*p 操作,还可以被复制或赋值,可以用 == 和 != 运算符进行比较。此外,两个正向迭代器可以互相赋值。
-
双向迭代器(bidirectional iterator) 双向迭代器具有正向迭代器的全部功能,除此之外,假设 p 是一个双向迭代器,则还可以进行 --p 或者 p-- 操作(即一次向后移动一个位置)。
-
随机访问迭代器(random access iterator) 随机访问迭代器具有双向迭代器的全部功能。除此之外,假设 p 是一个随机访问迭代器,i 是一个整型变量或常量,则 p 还支持以下操作:
-
p+=i:使得 p 往后移动 i 个元素。
-
p-=i:使得 p 往前移动 i 个元素。
-
p+i:返回 p 后面第 i 个元素的迭代器。
-
p-i:返回 p 前面第 i 个元素的迭代器。
-
p[i]:返回 p 后面第 i 个元素的引用。
-
容器 | 对应的迭代器类型 |
---|---|
array | 随机访问迭代器 |
vector | 随机访问迭代器 |
deque | 随机访问迭代器 |
list | 双向迭代器 |
set / multiset | 双向迭代器 |
map / multimap | 双向迭代器 |
forward_list | 前向迭代器 |
unordered_map / unordered_multimap | 前向迭代器 |
unordered_set / unordered_multiset | 前向迭代器 |
stack | 不支持迭代器 |
queue | 不支持迭代器 |
尽管不同容器对应着不同类别的迭代器,但这些迭代器有着较为统一的定义方式,具体分为 4 种:
迭代器定义方式 | 具体格式 |
---|---|
正向迭代器 | 容器类名::iterator 迭代器名; |
常量正向迭代器 | 容器类名::const_iterator 迭代器名; |
反向迭代器 | 容器类名::reverse_iterator 迭代器名; |
常量反向迭代器 | 容器类名::const_reverse_iterator 迭代器名; |
通过定义以上几种迭代器,就可以读取它指向的元素,*迭代器名
就表示迭代器指向的元素。其中,常量迭代器和非常量迭代器的分别在于,通过非常量迭代器还能修改其指向的元素。另外,反向迭代器和正向迭代器的区别在于:
- 对正向迭代器进行 ++ 操作时,迭代器会指向容器中的后一个元素;
- 而对反向迭代器进行 ++ 操作时,迭代器会指向容器中的前一个元素。
注意,以上 4 种定义迭代器的方式,并不是每个容器都适用。有一部分容器同时支持以上 4 种方式,比如 array、deque、vector;而有些容器只支持其中部分的定义方式,例如 forward_list 容器只支持定义正向迭代器,不支持定义反向迭代器。
//遍历 vector 容器。
#include <iostream>
//需要引入 vector 头文件
#include <vector>
using namespace std;
int main()
{
vector<int> v{1,2,3,4,5,6,7,8,9,10}; //v被初始化成有10个元素
cout << "第一种遍历方法:" << endl;
//size返回元素个数
for (int i = 0; i < v.size(); ++i)
cout << v[i] <<" "; //像普通数组一样使用vector容器
//创建一个正向迭代器,当然,vector也支持其他 3 种定义迭代器的方式
cout << endl << "第二种遍历方法:" << endl;
vector<int>::iterator i;
//用 != 比较两个迭代器
for (i = v.begin(); i != v.end(); ++i)
cout << *i << " ";
cout << endl << "第三种遍历方法:" << endl;
for (i = v.begin(); i < v.end(); ++i) //用 < 比较两个迭代器
cout << *i << " ";
cout << endl << "第四种遍历方法:" << endl;
i = v.begin();
while (i < v.end()) { //间隔一个输出
cout << *i << " ";
i += 2; // 随机访问迭代器支持 "+= 整数" 的操作
}
}
第一种遍历方法:
1 2 3 4 5 6 7 8 9 10
第二种遍历方法:
1 2 3 4 5 6 7 8 9 10
第三种遍历方法:
1 2 3 4 5 6 7 8 9 10
第四种遍历方法:
1 3 5 7 9
以下代码则不合法,因为双向迭代器不支持用“<”进行比较:
for(i = v.begin(); i < v.end(); ++i)
cout << *i;
所谓序列容器,即以线性排列(类似普通数组的存储方式)来存储某一指定类型(例如 int、double 等)的数据,需要特殊说明的是,该类容器并不会自动对存储的元素按照值的大小进行排序。
需要注意的是,序列容器只是一类容器的统称,并不指具体的某个容器,序列容器大致包含以下几类容器:
- array<T,N>(数组容器):表示可以存储 N 个 T 类型的元素,是 C++ 本身提供的一种容器。此类容器一旦建立,其长度就是固定不变的,这意味着不能增加或删除元素,只能改变某个元素的值;
- vector(向量容器):用来存放 T 类型的元素,是一个长度可变的序列容器,即在存储空间不足时,会自动申请更多的内存。使用此容器,在尾部增加或删除元素的效率最高(时间复杂度为 O(1) 常数阶),在其它位置插入或删除元素效率较差(时间复杂度为 O(n) 线性阶,其中 n 为容器中元素的个数);
- deque(双端队列容器):和 vector 非常相似,区别在于使用该容器不仅尾部插入和删除元素高效,在头部插入或删除元素也同样高效,时间复杂度都是 O(1) 常数阶,但是在容器中某一位置处插入或删除元素,时间复杂度为 O(n) 线性阶;
- list(链表容器):是一个长度可变的、由 T 类型元素组成的序列,它以双向链表的形式组织元素,在这个序列的任何地方都可以高效地增加或删除元素(时间复杂度都为常数阶 O(1)),但访问容器中任意元素的速度要比前三种容器慢,这是因为 list 必须从第一个元素或最后一个元素开始访问,需要沿着链表移动,直到到达想要的元素。
- forward_list(正向链表容器):和 list 容器非常类似,只不过它以单链表的形式组织元素,它内部的元素只能从第一个元素开始访问,是一类比链表容器快、更节省内存的容器。
注意,其实除此之外,stack 和 queue 本质上也属于序列容器,只不过它们都是在 deque 容器的基础上改头换面而成,通常更习惯称它们为容器适配器。
函数成员 | 函数功能 | array<T,N> | vector | deque |
---|---|---|---|---|
begin() | 返回指向容器中第一个元素的迭代器。 | 是 | 是 | 是 |
end() | 返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和 begin() 结合使用。 | 是 | 是 | 是 |
rbegin() | 返回指向最后一个元素的迭代器。 | 是 | 是 | 是 |
rend() | 返回指向第一个元素所在位置前一个位置的迭代器。 | 是 | 是 | 是 |
cbegin() | 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。 | 是 | 是 | 是 |
cend() | 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。 | 是 | 是 | 是 |
crbegin() | 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。 | 是 | 是 | 是 |
crend() | 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。 | 是 | 是 | 是 |
assign() | 用新元素替换原有内容。 | - | 是 | 是 |
operator=() | 复制同类型容器的元素,或者用初始化列表替换现有内容。 | 是 | 是 | 是 |
size() | 返回实际元素个数。 | 是 | 是 | 是 |
max_size() | 返回元素个数的最大值。这通常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。 | 是 | 是 | 是 |
capacity() | 返回当前容量。 | - | 是 | - |
empty() | 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。 | 是 | 是 | 是 |
resize() | 改变实际元素的个数。 | - | 是 | 是 |
shrink _to_fit() | 将内存减少到等于当前元素实际所使用的大小。 | - | 是 | 是 |
front() | 返回第一个元素的引用。 | 是 | 是 | 是 |
back() | 返回最后一个元素的引用。 | 是 | 是 | 是 |
operator | 使用索引访问元素。 | 是 | 是 | 是 |
at() | 使用经过边界检査的索引访问元素。 | 是 | 是 | 是 |
push_back() | 在序列的尾部添加一个元素。 | - | 是 | 是 |
insert() | 在指定的位置插入一个或多个元素。 | - | 是 | 是 |
emplace() | 在指定的位置直接生成一个元素。 | - | 是 | 是 |
emplace_back() | 在序列尾部生成一个元素。 | - | 是 | 是 |
pop_back() | 移出序列尾部的元素。 | - | 是 | 是 |
erase() | 移出一个元素或一段元素。 | - | 是 | 是 |
clear() | 移出所有的元素,容器大小变为 0。 | - | 是 | 是 |
swap() | 交换两个容器的所有元素。 | 是 | 是 | 是 |
data() | 返回指向容器中第一个元素的指针。 | 是 | 是 | - |
列表中 - 表明对应的容器并没有定义这个函数。
list 和 forward_list 容器彼此非常相似,forward_list 中包含了 list 的大部分成员函数,而未包含那些需要反向遍历的函数。表 3 展示了 list 和 forward_list 的函数成员。
函数成员 | 函数功能 | list | forward_list |
---|---|---|---|
begin() | 返回指向容器中第一个元素的迭代器。 | 是 | 是 |
end() | 返回指向容器最后一个元素所在位置后一个位置的迭代器。 | 是 | 是 |
rbegin() | 返回指向最后一个元素的迭代器。 | 是 | - |
rend() | 返回指向第一个元素所在位置前一个位置的迭代器。 | 是 | - |
cbegin() | 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。 | 是 | 是 |
before_begin() | 返回指向第一个元素前一个位置的迭代器。 | - | 是 |
cbefore_begin() | 和 before_begin() 功能相同,只不过在其基础上,增加了 const 属性,即不能用该指针修改元素的值。 | - | 是 |
cend() | 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。 | 是 | 是 |
crbegin() | 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。 | 是 | - |
crend() | 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。 | 是 | - |
assign() | 用新元素替换原有内容。 | 是 | 是 |
operator=() | 复制同类型容器的元素,或者用初始化列表替换现有内容。 | 是 | 是 |
size() | 返回实际元素个数。 | 是 | - |
max_size() | 返回元素个数的最大值,这通常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。 | 是 | 是 |
resize() | 改变实际元素的个数。 | 是 | 是 |
empty() | 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。 | 是 | 是 |
front() | 返回容器中第一个元素的引用。 | 是 | 是 |
back() | 返回容器中最后一个元素的引用。 | 是 | - |
push_back() | 在序列的尾部添加一个元素。 | 是 | - |
push_front() | 在序列的起始位置添加一个元素。 | 是 | 是 |
emplace() | 在指定位置直接生成一个元素。 | 是 | - |
emplace_after() | 在指定位置的后面直接生成一个元素。 | - | 是 |
emplace_back() | 在序列尾部生成一个元素。 | 是 | - |
cmplacc_front() | 在序列的起始位生成一个元索。 | 是 | 是 |
insert() | 在指定的位置插入一个或多个元素。 | 是 | - |
insert_after() | 在指定位置的后面插入一个或多个元素。 | - | 是 |
pop_back() | 移除序列尾部的元素。 | 是 | - |
pop_front() | 移除序列头部的元素。 | 是 | 是 |
reverse() | 反转容器中某一段的元素。 | 是 | 是 |
erase() | 移除指定位置的一个元素或一段元素。 | 是 | - |
erase_after() | 移除指定位置后面的一个元素或一段元素。 | - | 是 |
remove() | 移除所有和参数匹配的元素。 | 是 | 是 |
remove_if() | 移除满足一元函数条件的所有元素。 | 是 | 是 |
unique() | 移除所有连续重复的元素。 | 是 | 是 |
clear() | 移除所有的元素,容器大小变为 0。 | 是 | 是 |
swap() | 交换两个容器的所有元素。 | 是 | 是 |
sort() | 对元素进行排序。 | 是 | 是 |
merge() | 合并两个有序容器。 | 是 | 是 |
splice() | 移动指定位置前面的所有元素到另一个同类型的 list 中。 | 是 | - |
splice_after() | 移动指定位置后面的所有元素到另一个同类型的 list 中。 | - | 是 |
注意,大家没有必要死记这些表,它们仅供参考。在深入了解到容器是如何组织元素以后,你会本能地知道哪个容器能使用哪些成员函数。