C++ STL(二)序列式容器.md
什么是容器?
简单的理解容器,它就是一些模板类的集合,但和普通模板类不同的是,容器中封装的是组织数据的方法(也就是数据结构)。
STL 提供有 3 类标准容器,分别是序列容器、排序容器和哈希容器,其中后两类容器有时也统称为关联容器。
容器种类 | 功能 |
---|---|
序列容器 | 主要包括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++)是不支持的。
C++ STL迭代器(iterator)
数据的排序、查找、求和等需要对数据进行遍历的操作方法应该是类似的,利用泛型技术,将它们设计成适用所有容器的通用算法,从而将容器和算法分离开。但实现此目的需要有一个类似中介的装置,它除了要具有对容器进行遍历读写数据的能力之外,还要能对外隐藏容器的内部差异,从而以统一的界面向算法传送数据。于是乎,迭代器就产生了。
简单来讲,迭代器和 C++ 的指针非常类似,它可以是需要的任意类型,通过迭代器可以指向容器中的某个元素,如果需要,还可以对该元素进行读/写操作。
迭代器类别
STL 标准库为每一种标准容器定义了一种迭代器类型,这意味着,不同容器的迭代器也不同,其功能强弱也有所不同。
容器的迭代器的功能强弱,决定了该容器是否支持 STL 中的某种算法。
常用的迭代器按功能强弱分为输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器 5 种。
输入迭代器和输出迭代器比较特殊,它们不是把数组或容器当做操作对象,而是把输入流/输出流作为操作对象。有关这 2 个迭代器,我们会在后续章节做详细介绍。
1.
前向迭代器(forward iterator)
假设p是一个前向迭代器。那么p支持++p
,p++
,*p
操作,还可以被复制或赋值,可以用==和!=运算符进行比较。此外,两个正向迭代器可以互相赋值。
2.
双向迭代器(bidirectional iterator)
双向迭代器具有正向迭代器的全部功能,除此之外,假设p是一个双向迭代器,则还可以进行–p或者p–操作。
3.
随机访问迭代器(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个元素的引用。
表 1 所示,是 C++ 11 标准中不同容器指定使用的迭代器类型。
容器 | 对应的迭代器类型 |
---|---|
array | 随机访问迭代器 |
vector | 随机访问迭代器 |
deque | 随机访问迭代器 |
list | 双向迭代器 |
set/multiset | 双向迭代器 |
map/multimap | 双向迭代器 |
forward_list | 前向迭代器 |
unordered_map/unordered_multimap | 前向迭代器 |
unordered_set/unordered_multiset | 前向迭代器 |
stack | 不支持迭代器 |
queue | 不支持迭代器 |
注意,容器适配器 stack 和 queue 没有迭代器,它们包含有一些成员函数,可以用来对元素进行访问。
迭代器的定义方式
尽管不同容器对应着不同类别的迭代器,但这些迭代器有着较为统一的定义方式,具体分为 4 种,如表 2 所示。
迭代器定义方式 | 具体格式 |
---|---|
正向迭代器 | 容器类名::iterator 迭代器名; |
常量正向迭代器 | 容器类名::const_iterator 迭代器名; |
反向迭代器 | 容器类名::reverse_iterator 迭代器名; |
常量反向迭代器 | 容器类名::const_reverse_iterator 迭代器名; |
值得一提的是,表 2 中的反向迭代器全称为 “反向迭代器适配器”,后续章节会做详细讲解,这里读者只需要知道其用法即可。
通过定义以上几种迭代器,就可以读取它指向的元素,*迭代器名就表示迭代器指向的元素。
常量迭代器和非常量迭代器的分别在于,通过非常量迭代器还能修改其指向的元素。
反向迭代器和正向迭代器的区别在于:
- 对正向迭代器进行 ++ 操作时,迭代器会指向容器中的后一个元素;
- 而对反向迭代器进行 ++ 操作时,迭代器会指向容器中的前一个元素。
注意,以上 4 种定义迭代器的方式,并不是每个容器都适用。
迭代器示例
以vector示例:
1 | //遍历 vector 容器。 |
运行结果为:
第一种遍历方法:
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
再举一个例子,我们知道,list 容器的迭代器是双向迭代器。假设 v 和 i 的定义如下:
1 | //创建一个 v list容器 |
则以下代码是合法的:
1 | for(i = v.begin(); i != v.end(); ++i) |
以下代码则不合法,因为双向迭代器不支持用“<”进行比较:
1 | for(i = v.begin(); i < v.end(); ++i) |
以下代码也不合法,因为双向迭代器不支持用下标随机访问元素:
1 | for(int i=0; i<v.size(); ++i) |
以上有关 vector、list 容器的具体用法,后续章节会做详细讲解。
STL序列式容器
序列式容器:线性排列的存储数据,并且该类容器的数据的排序与容器内的元素无关。
序列式容器分类
序列容器是指一类容器,包含以下几类容器:
- **array<T,N>(数组容器)**:C++本身提供的容器。此类容器初始化之后,长度不可表,也就是说不可以增加和删除,只能对元素访问或修改。
- **vector(向量容器)**:长度可变,即空间不足时,会自动申请更多内存。在尾部增加或删除元素时效率最高(时间复杂度O(1) ),在其它位置插入或删除元素效率较差(时间复杂度为 O(n) 线性阶);
- deque(双端队列容器):和 vector 非常相似。头尾增加删除高效率(O(1)),其它位置效率极差(O(n))。
- list(链表容器):双向链表的存储方式,长度课表,任何位置增加删除快(时间复杂度都为常数阶 O(1)),但是访问慢。
- forward_list(正向链表容器):和list类似,但是是以单链表存储,比list快且省内存。
注意,其实除此之外,stack 和 queue 本质上也属于序列容器,只不过它们都是在 deque 容器的基础上改头换面而成,通常更习惯称它们为容器适配器,有关它们的介绍,会放到后续章节中。
容器中常见的函数成员
序列容器包含一些相同的成员函数,它们的功能也相同,本教程会在某个容器的上下文中详细介绍下面的每个函数,但对于每种类型的容器不会重复介绍它们的细节。
1.
函数成员 | 函数功能 | 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() | 返回元素个数的最大值。这通常是一个很大的值,一般是2-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() | 返回指向容器中第一个元素的指针。 | 是 | 是 | - |
列表中 - 表明对应的容器并没有定义这个函数。
2.
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() | 返回元素个数的最大值,这通常是一个很大的值,一般是2-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中。 | - | 是 |
array(STL array)序列容器
基本介绍
array 容器是 C++ 11 标准中新增的序列容器,简单地理解,它就是在 C++ 普通数组的基础上,添加了一些成员函数和全局函数。在使用上,它比普通数组更安全(原因后续会讲),且效率并没有因此变差。
array容器大小固定,无法动态扩展和收缩,只允许访问或替换。
基本使用
array 容器以类模板的形式定义在 头文件,并位于命名空间 std 中,如下所示:
1 | namespace std{ |
因此,在使用该容器之前,代码中需引入 头文件,并默认使用 std 命令空间,如下所示:
1 |
|
在 array<T,N> 类模板中,T 用于指明容器中的存储的具体数据类型,N 用于指明容器的大小,需要注意的是,这里的 N 必须是常量,不能用变量表示。
array 容器有多种初始化方式,如下代码展示了如何创建具有 10 个 double 类型元素的 array 容器:
1 | std::array<double, 10> values; |
提示,如果程序中已经默认指定了 std 命令空间,这里可以省略 std::。
由此,就创建好了一个名为 values 的 array 容器,其包含 10 个浮点型元素。但是,由于未显式指定这 10 个元素的值,因此使用这种方式创建的容器中,各个元素的值是不确定的(array 容器不会做默认初始化操作)。
通过如下创建 array 容器的方式,可以将所有的元素初始化为 0 或者和默认元素类型等效的值:
1 | std::array<double, 10> values {}; |
使用该语句,容器中所有的元素都会被初始化为 0.0。
当然,在创建 array 容器的实例时,也可以像创建常规数组那样对元素进行初始化:
1 | std::array<double, 10> values {0.5,1.0,1.5,,2.0}; |
可以看到,这里只初始化了前 4 个元素,剩余的元素都会被初始化为 0.0。图 1 说明了这一点。
除此之外,array 容器还提供有很多功能实用的成员函数,如表 2 所示。
成员函数 | 功能 |
---|---|
begin() | 返回指向容器中第一个元素的随机访问迭代器。 |
end() | 返回指向容器最后一个元素之后一个位置的随机访问迭代器,通常和begin()结合使用。 |
rbegin() | 返回指向最后一个元素的随机访问迭代器。 |
rend() | 返回指向第一个元素之前一个位置的随机访问迭代器。 |
cbegin() | 和begin()功能相同,只不过在其基础上增加了const属性,不能用于修改元素。 |
cend() | 和end()功能相同,只不过在其基础上,增加了const属性,不能用于修改元素。 |
crbegin() | 和rbegin()功能相同,只不过在其基础上,增加了const属性,不能用于修改元素。 |
crend() | 和rend()功能相同,只不过在其基础上,增加了const属性,不能用于修改元素。 |
size() | 返回容器中当前元素的数量,其值始终等于初始化array类的第二个模板参数N。 |
max_size() | 返回容器可容纳元素的最大数量,其值始终等于初始化array类的第二个模板参数N。 |
empty() | 判断容器是否为空,和通过size()==0的判断条件功能相同,但其效率可能更快。 |
at(n) | 返回容器中n位置处元素的引用,该函数自动检查n是否在有效的范围内,如果不是则抛出out_of_range异常。 |
front() | 返回容器中第一个元素的直接引用,该函数不适用于空的array容器。 |
back() | 返回容器中最后一个元素的直接应用,该函数同样不适用于空的array容器。 |
data() | 返回一个指向容器首个元素的指针。利用该指针,可实现复制容器中所有元素等类似功能。 |
fill(val) | 将val这个值赋值给容器中的每个元素。 |
array1.swap(array2) | 交换array1和array2 容器中的所有元素,但前提是它们具有相同的长度和类型。 |
除此之外,C++ 11 标准库还新增加了 begin() 和 end() 这 2 个函数,和 array 容器包含的 begin() 和 end() 成员函数不同的是,标准库提供的这 2 个函数的操作对象,既可以是容器,还可以是普通数组。当操作对象是容器时,它和容器包含的 begin() 和 end() 成员函数的功能完全相同;如果操作对象是普通数组,则 begin() 函数返回的是指向数组第一个元素的指针,同样 end() 返回指向数组中最后一个元素之后一个位置的指针(注意不是最后一个元素)。
另外,在 头文件中还重载了 get() 全局函数,该重载函数的功能是访问容器中指定的元素,并返回该元素的引用。
正是由于 array 容器中包含了 at() 这样的成员函数,使得操作元素时比普通数组更安全。
例如代码演示了表 2 中一部分成员函数的用法和功能:
1 |
|
注意,代码中的 auto 关键字,可以使编译器自动判定变量的类型。运行这段代码,输出结果为:
3
0 1 2 3
array随机访问迭代器
STL 为 array 容器配备了随机访问迭代器,该类迭代器是功能最强大的迭代器。
在 array 容器的模板类中,和随机访问迭代器相关的成员函数如表 1 所示。
成员函数 | 功能 |
---|---|
begin() | 返回指向容器中第一个元素的正向迭代器;如果是const类型容器,在该函数返回的是常量正向迭代器。 |
end() | 返回指向容器最后一个元素之后一个位置的正向迭代器;如果是const类型容器,在该函数返回的是常量正向迭代器。此函数通常和begin()搭配使用。 |
rbegin() | 返回指向最后一个元素的反向迭代器;如果是const类型容器,在该函数返回的是常量反向迭代器。 |
rend() | 返回指向第一个元素之前一个位置的反向迭代器。如果是const类型容器,在该函数返回的是常量反向迭代器。此函数通常和rbegin()搭配使用。 |
cbegin() | 和begin()功能类似,只不过其返回的迭代器类型为常量正向迭代器,不能用于修改元素。 |
cend() | 和end()功能相同,只不过其返回的迭代器类型为常量正向迭代器,不能用于修改元素。 |
crbegin() | 和rbegin()功能相同,只不过其返回的迭代器类型为常量反向迭代器,不能用于修改元素。 |
crend() | 和rend()功能相同,只不过其返回的迭代器类型为常量反向迭代器,不能用于修改元素。 |
这些成员函数的具体功能下图所示。
array容器访问元素
当 array 容器创建完成之后,最常做的操作就是获取其中的元素,甚至有时还会通过循环结构获取多个元素。本节就对获取容器中元素的方法做个汇总。
1.
访问array容器中单个元素
首先,可以通过容器名[]的方式直接访问和使用容器中的元素,这和 C++ 标准数组访问元素的方式相同,例如:
1 | values[4] = values[3] + 2.O*values[1]; |
此行代码中,第 5 个元素的值被赋值为右边表达式的值。需要注意的是,使用如上这样方式,由于没有做任何边界检查,所以即便使用越界的索引值去访问或存储元素,也不会被检测到。
为了能够有效地避免越界访问的情况,可以使用 array 容器提供的 at() 成员函数,例如:
1 | values.at (4) = values.at(3) + 2.O*values.at(1); |
这行代码和前一行语句实现的功能相同,其次当传给 at() 的索引是一个越界值时,程序会抛出 std::out_of_range 异常。因此当需要访问容器中某个指定元素时,建议大家使用 at(),除非确定索引没有越界。
读者可能有这样一个疑问,即为什么 array 容器在重载 [] 运算符时,没有实现边界检查的功能呢?答案很简单,因为性能。如果每次访问元素,都去检查索引值,无疑会产生很多开销。当不存在越界访问的可能时,就能避免这种开销。
除此之外,array 容器还提供了 get 模板函数,它是一个辅助函数,能够获取到容器的第 n 个元素。需要注意的是,该模板函数中,参数的实参必须是一个在编译时可以确定的常量表达式,所以它不能是一个循环变量。也就是说,它只能访问模板参数指定的元素,编译器在编译时会对它进行检查。
2.
访问array容器中多个元素
array 容器提供的 size() 函数能够返回容器中元素的个数(函数返回值为 size_t 类型),所以能够像下面这样去逐个提取容器中的元素,并计算它们的和:
1 | double total = 0; |
size() 函数的存在,为 array 容器提供了标准数组所没有的优势,即能够知道它包含多少元素。
并且,接受数组容器作为参数的函数,只需要通过调用容器的成员函数 size(),就能得到元素的个数。除此之外,通过调用 array 容器的 empty() 成员函数,即可知道容器中有没有元素(如果容器中没有元素,此函数返回 true),如下所示:
1 | if(values.empty()) |
然而,很少会创建空的 array 容器,因为当生成一个 array 容器时,它的元素个数就固定了,而且无法改变,所以生成空 array 容器的唯一方法是将模板的第二个参数指定为 0,但这种情况基本不可能发生。
array 容器之所以提供 empty() 成员函数的原因,对于其他元素可变或者元素可删除的容器(例如 vector、deque 等)来说,它们使用 empty() 时的机制是一样的,因此为它们提供了一个一致性的操作。
除了借助 size() 外,对于任何可以使用迭代器的容器,都可以使用基于范围的循环,因此能够更加简便地计算容器中所有元素的和,比如:
1 | double total = 0; |
读者可以这样认为,array 容器就是普通数组的“升级版”,使用普通数组能实现的,使用 array 容器都可以实现,而且无论是代码功能的实现效率,还是程序执行效率,都比普通数组更高。
vector序列容器
基本介绍
vector 容器是 STL 中最常用的容器之一,它和 array 容器非常类似,都可以看做是对 C++ 普通数组的“升级版”。
不同之处在于,array 实现的是静态数组(容量固定的数组),而 vector 实现的是一个动态数组,即可以进行元素的插入和删除,在此过程中,vector 会动态调整所占用的内存空间,整个过程无需人工干预。
vector 常被称为向量容器,因为该容器擅长在尾部插入或删除元素,在常量时间内就可以完成,时间复杂度为O(1);而对于在容器头部或者中部插入或删除元素,则花费时间要长一些(移动元素需要耗费时间),时间复杂度为线性阶O(n)。
vector 容器以类模板 vector( T 表示存储元素的类型)的形式定义在 头文件中,并位于 std 命名空间中。因此,在创建该容器之前,代码中需包含如下内容:
1 |
|
注意,std 命名空间也可以在使用 vector 容器时额外注明,两种方式都可以。
vector初始化
初始化vector容器的方式有很多,如下:
1.
创建存储 double 类型元素的一个 vector 容器
1 | std::vector<double> values; |
这时是一个空的vector容器。
调用reserve()成员函数来增加容器的容量:
1 | values.reserve(20); |
2.
除了创建空 vector 容器外,还可以在创建的同时指定初始值以及元素个数,比如:
1 | std::vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19}; |
这样就创建了一个含有 8 个素数的 vector 容器。
3.
在创建 vector 容器时,也可以指定元素个数:
1 | std::vector<double> values(20); |
如此,values 容器开始时就有 20 个元素,它们的默认初始值都为 0。
如果不想用 0 作为默认值,也可以指定一个其它值,例如:
1 | std::vector<double> values(20, 1.0); |
第二个参数指定了所有元素的初始值,因此这 20 个元素的值都是 1.0。
4.
通过存储元素类型相同的其它 vector 容器,也可以创建新的 vector 容器,例如:
1 | std::vector<char>value1(5, 'c'); |
由此,value2 容器中也具有 5 个字符 ‘c’。在此基础上,如果不想复制其它容器中所有的元素,可以用一对指针或者迭代器来指定初始值的范围,例如:
1 | int array[]={1,2,3}; |
由此,value2 容器中就包含了 {1,2,3} 这 3 个元素。
vector的成员函数
函数成员 | 函数功能 |
---|---|
begin() | 返回指向容器中第一个元素的迭代器。 |
end() | 返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和begin()结合使用。 |
rbegin() | 返回指向最后一个元素的迭代器。 |
rend() | 返回指向第一个元素所在位置前一个位置的迭代器。 |
cbegin() | 和 begin()功能相同,只不过在其基础上,增加了const属性,不能用于修改元素。 |
cend() | 和end()功能相同,只不过在其基础上,增加了const属性,不能用于修改元素。 |
crbegin() | 和rbegin()功能相同,只不过在其基础上,增加了const属性,不能用于修改元素。 |
crend() | 和rend()功能相同,只不过在其基础上,增加了const属性,不能用于修改元素。 |
size() | 返回实际元素个数。 |
max_size() | 返回元素个数的最大值。这通常是一个很大的值,一般是2-1,所以我们很少会用到这个函数。 |
resize() | 改变实际元素的个数。 |
capacity() | 返回当前容量。 |
empty() | 判断容器中是否有元素,若无元素,则返回true;反之,返回false。 |
reserve() | 增加容器的容量。 |
shrink _to_fit() | 将内存减少到等于当前元素实际所使用的大小。 |
operator[] | 重载了 []运算符,可以向访问数组中元素那样,通过下标即可访问甚至修改vector容器中的元素。 |
at() | 使用经过边界检查的索引访问元素。 |
front() | 返回第一个元素的引用。 |
back() | 返回最后一个元素的引用。 |
data() | 返回指向容器中第一个元素的指针。 |
assign() | 用新元素替换原有内容。 |
push_back() | 在序列的尾部添加一个元素。 |
pop_back() | 移出序列尾部的元素。 |
insert() | 在指定的位置插入一个或多个元素。 |
erase() | 移出一个元素或一段元素。 |
clear() | 移出所有的元素,容器大小变为0。 |
swap() | 交换两个容器的所有元素。 |
emplace() | 在指定的位置直接生成一个元素。 |
emplace_back() | 在序列尾部生成一个元素。 |
除此之外,C++ 11 标准库还新增加了 begin() 和 end() 这 2 个函数,和 vector 容器包含的 begin() 和 end() 成员函数不同,标准库提供的这 2 个函数的操作对象,既可以是容器,还可以是普通数组。当操作对象是容器时,它和容器包含的 begin() 和 end() 成员函数的功能完全相同;如果操作对象是普通数组,则 begin() 函数返回的是指向数组第一个元素的指针,同样 end() 返回指向数组中最后一个元素之后一个位置的指针(注意不是最后一个元素)。
vector容器迭代器的使用
略
vector容器访问元素
访问vector容器中单个元素
- 使用
容器名[n]
这种获取元素的方式。需要确保下标 n 的值不会超过容器的容量(可以通过 capacity() 成员函数获取),否则会发生越界访问的错误。 - vector 容器也提供了 at() 成员函数,当传给 at() 的索引会造成越界时,会抛出
std::out_of_range
异常。 - vector 容器还提供了 2 个成员函数,即 front() 和 back(),它们分别返回 vector 容器中第一个和最后一个元素的引用,通过利用这 2 个函数返回的引用,可以访问(甚至修改)容器中的首尾元素。
- vector 容器还提供了 data() 成员函数,该函数的功能是返回指向容器中首个元素的指针。通过该指针也可以访问甚至修改容器中的元素。```c
- 使用
#include
#include
using namespace std;
int main()
{
vector
//输出容器中第 3 个元素的值
cout << *(values.data() + 2) << endl;
//修改容器中第 2 个元素的值
*(values.data() + 1) = 10;
cout << *(values.data() + 1) << endl;
return 0;
}
1 |
|
2.
可以使用 vector 迭代器遍历 vector 容器,这里以 begin()/end() 为例:
1 |
|
vector容量(capacity)和大小(size
capacity和size的区别
vector 容器的容量(用 capacity 表示),指的是在不分配更多内存的情况下,容器可以保存的最多元素个数;而 vector 容器的大小(用 size 表示),指的是它实际所包含的元素个数。
修改vector容器的容量和大小
调用 reserve() 成员函数来增加容器的容量(但并不会改变存储元素的个数);而通过调用成员函数 resize() 可以改变容器的大小,并且该函数也可能会导致 vector 容器容量的增加。比如说:
1 |
|
运行结果为:
value 容量是:15
value 大小是:15
value 容量是(2):20
value 大小是(2):15
value 容量是(3):30
value 大小是(3):21
程序中给出了关于 resize() 成员函数的 3 种不同的用法,有兴趣的读者可自行查看不同用法的运行结果。
仅通过 reserve() 成员函数增加 value 容器的容量,其大小并没有改变;但通过 resize() 成员函数改变 value 容器的大小,它的容量可能会发生改变。另外需要注意的是,通过 resize() 成员函数减少容器的大小(多余的元素会直接被删除),不会影响容器的容量。
vector容器容量和大小的数据类型
在实际场景中,我们可能需要将容器的容量和大小保存在变量中,要知道 vector 对象的容量和大小类型都是 vector::size_type 类型。因此,当定义一个变量去保存这些值时,可以如下所示:
1 | vector<int>::size_type cap = value.capacity(); |
size_type 类型是定义在由 vector 类模板生成的 vecotr 类中的,它表示的真实类型和操作系统有关,在 32 位架构下普遍表示的是 unsigned int 类型,而在 64 位架构下普通表示 unsigned long 类型。
当然,我们还可以使用 auto 关键字代替 vector::size_type,比如:
1 | auto cap = value.capacity(); |
vector容器类结构
vector 是最常用的容器之一,其底层所采用的数据结构非常简单,就只是一段连续的线性内存空间(顺序存储)。
通过分析 vector 容器的源代码不难发现,它就是使用 3 个迭代器(可以理解成指针)来表示的:
1 | //_Alloc 表示内存分配器,此参数几乎不需要我们关心 |
其中,_Myfirst 指向的是 vector 容器对象的起始字节位置;_Mylast 指向当前最后一个元素的末尾字节;_myend 指向整个 vector 容器所占用内存空间的末尾字节。
演示了以上这 3 个迭代器分别指向的位置。
通过这 3 个迭代器,就可以表示出一个已容纳 2 个元素,容量为 5 的 vector 容器。
在此基础上,将 3 个迭代器两两结合,还可以表达不同的含义,例如:
- _Myfirst 和 _Mylast 可以用来表示 vector 容器中目前已被使用的内存空间;
- _Mylast 和 _Myend 可以用来表示 vector 容器目前空闲的内存空间;
- _Myfirst 和 _Myend 可以用表示 vector 容器的容量。
对于空的 vector 容器,由于没有任何元素的空间分配,因此 _Myfirst、_Mylast 和 _Myend 均为 null。
通过灵活运用这 3 个迭代器,vector 容器可以轻松的实现诸如首尾标识、大小、容器、空容器判断等几乎所有的功能,比如:
1 | template <class _Ty, class _Alloc = allocator<_Ty>> |
vector扩大容量的本质
当 vector 的大小和容量相等(size==capacity)也就是满载时,如果再向其添加元素,那么 vector 就需要扩容。vector 容器扩容的过程需要经历以下 3 步:
- 完全弃用现有的内存空间,重新申请更大的内存空间;
- 将旧内存空间中的数据,按原有顺序移动到新的内存空间中;
- 最后将旧的内存空间释放。
这也就解释了,为什么 vector 容器在进行扩容后,与其相关的指针、引用以及迭代器可能会失效的原因。
由此可见,vector 扩容是非常耗时的。为了降低再次分配内存空间时的成本,每次扩容时 vector 都会申请比用户需求量更多的内存空间(这也就是 vector 容量的由来,即 capacity>=size),以便后期使用。
vector 容器扩容时,不同的编译器申请更多内存空间的量是不同的。以 VS 为例,它会扩容现有容器容量的 50%。
vector添加元素push_back()和emplace_back()
向 vector 容器中添加元素的唯一方式就是使用它的成员函数,如果不调用成员函数,非成员函数既不能添加也不能删除元素。这意味着,vector 容器对象必须通过它所允许的函数去访问,迭代器显然不行。
- push_back():在 vector 容器尾部添加一个元素
- emplace_back():该函数是 C++ 11 新增加的,其功能和 push_back() 相同,都是在 vector 容器的尾部添加一个元素。
读者可能会发现,以上 2 段代码,只是用 emplace_back() 替换了 push_back(),既然它们实现的功能是一样的,那么 C++ 11 标准中为什么要多此一举呢?
emplace_back() 和 push_back() 的区别,就在于底层实现的机制不同。push_back() 向容器尾部添加元素时,首先会创建这个元素,然后再将这个元素拷贝或者移动到容器中(如果是拷贝的话,事后会自行销毁先前创建的这个元素);而 emplace_back() 在实现时,则是直接在容器尾部创建这个元素,省去了拷贝或移动元素的过程。
push_back() 的底层实现过程比 emplace_back() 更繁琐,换句话说,emplace_back() 的执行效率比 push_back() 高。因此,在实际使用时,建议大家优先选用 emplace_back()。
vector插入元素——insert()和emplace()
insert()
insert() 函数的功能是在 vector 容器的指定位置插入一个或多个元素。该函数的语法格式有多种,如下表:
语法格式 | 用法说明 |
---|---|
iterator insert(pos,elem) | 在迭代器pos指定的位置之前插入一个新元素elem,并返回表示新插入元素位置的迭代器。 |
iterator insert(pos,n,elem) | 在迭代器pos指定的位置之前插入n个元素elem,并返回表示第一个新插入元素位置的迭代器。 |
iterator insert(pos,first,last) | 在迭代器pos指定的位置之前,插入其他容器(不仅限于vector)中位于[first,last)区域的所有元素,并返回表示第一个新插入元素位置的迭代器。 |
iterator insert(pos,initlist) | 在迭代器pos指定的位置之前,插入初始化列表(用大括号{}括起来的多个元素,中间有逗号隔开)中所有的元素,并返回表示第一个新插入元素位置的迭代器。 |
1 |
|
emplace()
emplace() 是 C++ 11 标准新增加的成员函数,用于在 vector 容器指定位置之前插入一个新的元素。
注意,emplace() 每次只能插入一个元素,而不是多个。
该函数的语法格式如下:
1 | iterator emplace (const_iterator pos, args...); |
其中,pos 为指定插入位置的迭代器;args… 表示与新插入元素的构造函数相对应的多个参数;该函数会返回表示新插入元素位置的迭代器。
1 |
|
运行结果为:
3 1 2
vector删除元素的几种方式
vector删除元素可以借助自身的成员函数,也能使用全局函数。
函数 | 功能 |
---|---|
pop_back() | 删除vector容器中最后一个元素,该容器的大小(size)会减1,但容量(capacity)不会发生改变。 |
erase(pos) | 删除vector容器中pos迭代器指定位置处的元素,并返回指向被删除元素下一个位置元素的迭代器。该容器的大小(size)会减1,但容量(capacity)不会发生改变。 |
swap(beg)、pop_back() | 先调用swap()函数交换要删除的目标元素和容器最后一个元素的位置,然后使用pop_back()删除该目标元素。 |
erase(beg,end) | 删除vector容器中位于迭代器[beg,end)指定区域内的所有元素,并返回指向被删除区域下一个位置元素的迭代器。该容器的大小(size)会减小,但容量(capacity)不会发生改变。 |
remove() | 删除容器中所有和指定元素值相等的元素,并返回指向最后一个元素下一个位置的迭代器。值得一提的是,调用该函数不会改变容器的大小和容量。 |
clear() | 删除vector容器中所有的元素,使其变成空的vector容器。该函数会改变vector的大小(变为0),但不是改变其容量。 |
避免vector进行不必要的扩容?
vector 容器扩容的整个过程,和 realloc() 函数的实现方法类似,大致分为以下 4 个步骤:
- 分配一块大小是当前 vector 容量几倍的新存储空间。注意,多数 STL 版本中的 vector 容器,其容器都会以 2 的倍数增长,也就是说,每次 vector 容器扩容,它们的容量都会提高到之前的 2 倍;
- 将 vector 容器存储的所有元素,依照原有次序从旧的存储空间复制到新的存储空间中;
- 析构掉旧存储空间中存储的所有元素;
- 释放旧的存储空间。
vector 容器的扩容过程是非常耗时的,并且当容器进行扩容后,之前和该容器相关的所有指针、迭代器以及引用都会失效。因此在使用 vector 容器过程中,我们应尽量避免执行不必要的扩容操作。
要实现这个目标,可以借助 vector 模板类中提供的 reserve() 成员方法。强制 vector 容器的容量至少为 n。注意,如果 n 比当前 vector 容器的容量小,则该方法什么也不会做;反之如果 n 比当前 vector 容器的容量大,则 vector 容器就会扩容。
只要有新元素要添加到 vector 容器中而恰好此时 vector 容器的容量不足时,该容器就会自动扩容。
避免 vector 容器执行不必要的扩容操作的关键在于,在使用 vector 容器初期,就要将其容量设为足够大的值。换句话说,在 vector 容器刚刚构造出来的那一刻,就应该借助 reserve() 成员方法为其扩充足够大的容量。
举个例子,假设我们想创建一个包含 1~1000 的 vector,通常会这样实现:
1 | vector<int>myvector; |
值得一提的是,上面代码的整个循环过程中,vector 容器会进行 2~10 次自动扩容(多数的 STL 标准库版本中,vector 容器通常会扩容至当前容量的 2 倍,而这里 1000≈2 10),程序的执行效率可想而知。
在上面程序的基础上,下面代码演示了如何使用 reserve() 成员方法尽量避免 vector 容器执行不必要的扩容操作:
1 | vector<int>myvector; |
相比前面的代码实现,整段程序在运行过程中,vector 容器的容量仅扩充了 1 次,执行效率大大提高。
当然在实际场景中,我们可能并不知道 vector 容器到底要存储多少个元素。这种情况下,可以先预留出足够大的空间,当所有元素都存储到 vector 容器中之后,再去除多余的容量。
那么如何去除多余的容量呢?后续揭晓。
vector去除多余容量——shrink_to_fit()与swap()
shrink_to_fit()
1 | vector<int> myvector; |
swap()妙用去除多余容量
vector 模板类中提供有 swap() 成员方法,该方法的基础功能是交换 2 个相同类型的 vector 容器(交换容量和存储的所有元素),但其也能用于去除 vector 容器多余的容量。
如果想用 swap() 成员方法去除当前 vector 容器多余的容量时,可以套用如下的语法格式:
1 | vector<T>(x).swap(x); |
其中,x 指当前要操作的容器,T 为该容器存储元素的类型。
下面程序演示了此语法格式的 swap() 方法的用法和功能:
1 |
|
程序执行结果为:
1、当前 myvector 拥有 0 个元素,容量为 1000
2、当前 myvector 拥有 10 个元素,容量为 10
显然,第 16 行代码成功将 myvector 容器的容量 1000 修改为 10,此行代码的执行流程可细分为以下 3 步:
1.
先执行 vector(myvector),此表达式会调用 vector 模板类中的拷贝构造函数,从而创建出一个临时的 vector 容器(后续称其为 tempvector)。
值得一提的是,tempvector 临时容器并不为空,因为我们将 myvector 作为参数传递给了复制构造函数,该函数会将 myvector 容器中的所有元素拷贝一份,并存储到 tempvector 临时容器中。
注意,vector 模板类中的拷贝构造函数只会为拷贝的元素分配存储空间。换句话说,tempvector 临时容器中没有空闲的存储空间,其容量等于存储元素的个数。
2.
然后借助 swap() 成员方法对 tempvector 临时容器和 myvector 容器进行调换,此过程不仅会交换 2 个容器存储的元素,还会交换它们的容量。换句话说经过 swap() 操作,myvetor 容器具有了 tempvector 临时容器存储的所有元素和容量,同时 tempvector 也具有了原 myvector 容器存储的所有元素和容量。
3.
当整条语句执行结束时,临时的 tempvector 容器会被销毁,其占据的存储空间都会被释放。注意,这里释放的其实是原 myvector 容器占用的存储空间。
经过以上 3 个步骤,就成功的将 myvector 容器的容量由 100 缩减至 10。
利用swap()方法清空vector容器
在以上内容的学习过程中,如果读者善于举一反三,应该不难想到,swap() 方法还可以用来清空 vector 容器。
当 swap() 成员方法用于清空 vector 容器时,可以套用如下的语法格式:
1 | vector<T>().swap(x); |
其中,x 指当前要操作的容器,T 为该容器存储元素的类型。
注意,和上面语法格式唯一的不同之处在于,这里没有为 vector() 表达式传递任何参数。这意味着,此表达式将调用 vector 模板类的默认构造函数,而不再是复制构造函数。也就是说,此格式会先生成一个空的 vector 容器,再借助 swap() 方法将空容器交换给 x,从而达到清空 x 的目的。
下面程序演示了此语法格式的 swap() 方法的用法和功能:
1 |
|
程序执行结果为:
1、当前 myvector 拥有 0 个元素,容量为 1000
2、当前 myvector 拥有 0 个元素,容量为 0
vector<bool>
不是存储bool类型元素的vector容器!
前面章节中,已经详细介绍了vector<T>
容器的功能和用法。特别需要提醒的是,在使用 vector 容器时,要尽量避免使用该容器存储 bool 类型的元素,即避免使用vector<bool>
。
具体来讲,不推荐使用 vector 的原因有以下 2 个:
- 严格意义上讲,vector 并不是一个 STL 容器;
- vector 底层存储的并不是 bool 类型值。
读者可能会感到有些困惑,别着急,继续往下读
vector<bool>
不是容器
值得一提的是,对于是否为 STL 容器,C++ 标准库中有明确的判断条件,其中一个条件是:如果 cont 是包含对象 T 的 STL 容器,且该容器中重载了 [ ] 运算符(即支持 operator[]),则以下代码必须能够被编译:
1 | T *p = &cont[0]; |
此行代码的含义是,借助 operator[ ] 获取一个 cont 容器中存储的 T 对象,同时将这个对象的地址赋予给一个 T 类型的指针。
这就意味着,如果 vector< bool> 是一个 STL 容器,则下面这段代码是可以通过编译的:
1 | //创建一个 vector<bool> 容器 |
但不幸的是,此段代码不能通过编译。原因在于 vector< bool> 底层采用了独特的存储机制。
实际上,为了节省空间,vector< bool> 底层在存储各个 bool 类型值时,每个 bool 值都只使用一个比特位(二进制位)来存储。也就是说在 vector< bool> 底层,一个字节可以存储 8 个 bool 类型值。在这种存储机制的影响下,operator[ ] 势必就需要返回一个指向单个比特位的引用,但显然这样的引用是不存在的。
C++ 标准中解决这个问题的方案是,令 operator[] 返回一个代理对象(proxy object)。有关代理对象,由于不是本节重点,这里不再做描述,有兴趣的读者可自行查阅相关资料。
同样对于指针来说,其指向的最小单位是字节,无法另其指向单个比特位。综上所述可以得出一个结论,即上面第 2 行代码中,用 = 赋值号连接 bool *p 和 &cont[0] 是矛盾的。
由于 vector< bool> 并不完全满足 C++ 标准中对容器的要求,所以严格意义上来说它并不是一个 STL 容器。可能有读者会问,既然 vector< bool> 不完全是一个容器,为什么还会出现在 C++ 标准中呢?
这和一个雄心勃勃的试验有关,还要从前面提到的代理对象开始说起。由于代理对象在 C++ 软件开发中很受欢迎,引起了 C++ 标准委员会的注意,他们决定以开发 vector< bool> 作为一个样例,来演示 STL 中的容器如何通过代理对象来存取元素,这样当用户想自己实现一个基于代理对象的容器时,就会有一个现成的参考模板。
然而开发人员在实现 vector< bool> 的过程中发现,既要创建一个基于代理对象的容器,同时还要求该容器满足 C++ 标准中对容器的所有要求,是不可能的。由于种种原因,这个试验最终失败了,但是他们所做过的尝试(即开发失败的 vector< bool>)遗留在了 C++ 标准中。
至于将 vector< bool> 遗留到 C++ 标准中,是无心之作,还是有意为之,这都无关紧要,重要的是让读者明白,vector< bool> 不完全满足 C++ 标准中对容器的要求,尽量避免在实际场景中使用它!
如何避免使用vector<bool>
那么,如果在实际场景中需要使用 vector<bool>
这样的存储结构,该怎么办呢?很简单,可以选择使用 deque<bool>
或者 bitset 来替代 vector<bool>
。
要知道,deque 容器几乎具有 vecotr 容器全部的功能(拥有的成员方法也仅差 reserve() 和 capacity()),而且更重要的是,deque 容器可以正常存储 bool 类型元素。
有关 deque 容器的具体用法,后续章节会做详细讲解。
还可以考虑用 bitset 代替 vector<bool>
,其本质是一个模板类,可以看做是一种类似数组的存储结构。和后者一样,bitset 只能用来存储 bool 类型值,且底层存储机制也采用的是用一个比特位来存储一个 bool 值。
和 vector 容器不同的是,bitset 的大小在一开始就确定了,因此不支持插入和删除元素;另外 bitset 不是容器,所以不支持使用迭代器。
有关 bitset 的用法,感兴趣的读者可查阅 C++ 官方提供的 bitset使用手册。
deque容器
基本介绍
deque 是 double-ended queue 的缩写,又称双端队列容器。
deque 容器和 vecotr 容器有很多相似之处,比如:
- deque 容器也擅长在序列尾部添加或删除元素(时间复杂度为
O(1)
),而不擅长在序列中间添加或删除元素。 - deque 容器也可以根据需要修改自身的容量和大小。
和 vector 不同的是,deque 还擅长在序列头部添加或删除元素,所耗费的时间复杂度也为常数阶O(1)。并且更重要的一点是,deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。
deque 容器以模板类 deque(T 为存储元素的类型)的形式在 头文件中,并位于 std 命名空间中。因此,在使用该容器之前,代码中需要包含下面两行代码:
1 |
|
注意,std 命名空间也可以在使用 deque 容器时额外注明,两种方式都可以。
deque初始化
创建 deque 容器,根据不同的实际场景,可选择使用如下几种方式。
- 创建一个没有任何元素的空 deque 容器:```c
std::dequed; 1
2
3
4
和空 array 容器不同,空的 deque 容器在创建之后可以做添加或删除元素的操作,因此这种简单创建 deque 容器的方式比较常见。
2. 创建一个具有 n 个元素的 deque 容器,其中每个元素都采用对应类型的默认值:```c
std::deque<int> d(10);
此行代码创建一个具有 10 个元素(默认都为 0)的 deque 容器。
3. 创建一个具有 n 个元素的 deque 容器,并为每个元素都指定初始值,例如:```c
std::deque
1 |
|
注意,采用此方式,必须保证新旧容器存储的元素类型一致。
5. 通过拷贝其他类型容器中指定区域内的元素(也可以是普通数组),可以创建一个新容器,例如:```c
//拷贝普通数组,创建deque容器
int a[] = { 1,2,3,4,5 };
std::deque
//适用于所有类型的容器
std::array<int, 5>arr{ 11,12,13,14,15 };
std::deque
1 |
|
deque容器的底层实现
了解了 deque 容器底层存储序列的结构,以及 deque 容器迭代器的内部结构之后,接下来看看 deque 容器究竟是如何实现的。
deque 容器除了维护先前讲过的 map 数组,还需要维护 start、finish 这 2 个 deque 迭代器。以下为 deque 容器的定义:
1 | //_Alloc为内存分配器 |
其中,start 迭代器记录着 map 数组中首个连续空间的信息,finish 迭代器记录着 map 数组中最后一个连续空间的信息。另外需要注意的是,和普通 deque 迭代器不同,start 迭代器中的 cur 指针指向的是连续空间中首个元素;而 finish 迭代器中的 cur 指针指向的是连续空间最后一个元素的下一个位置。
因此,deque 容器的底层实现如图 2 所示。
借助 start 和 finish,以及 deque 迭代器中重载的诸多运算符,就可以实现 deque 容器提供的大部分成员函数,比如:
1 | //begin() 成员函数 |
deque容器访问元素(4种方法)
- 容器名[n]
- 容器名.at(n)
- deque 容器的2 个成员函数,即 front() 和 back()。
- 迭代器
deque容器添加和删除元素方法
deque 容器中,无论是添加元素还是删除元素,都只能借助 deque 模板类提供的成员函数。
成员函数 | 功能 |
---|---|
push_back() | 在容器现有元素的尾部添加一个元素,和emplace_back()不同,该函数添加新元素的过程是,先构造元素,然后再将该元素移动或复制到容器的尾部。 |
pop_back() | 移除容器尾部的一个元素。 |
push_front() | 在容器现有元素的头部添加一个元素,和emplace_back()不同,该函数添加新元素的过程是,先构造元素,然后再将该元素移动或复制到容器的头部。 |
pop_front() | 移除容器尾部的一个元素。 |
emplace_back() | C++11新添加的成员函数,其功能是在容器尾部生成一个元素。和push_back()不同,该函数直接在容器头部构造元素,省去了复制或移动元素的过程。 |
emplace_front() | C++11新添加的成员函数,其功能是在容器头部生成一个元素。和push_front()不同,该函数直接在容器头部构造元素,省去了复制或移动元素的过程。 |
insert() | 在指定的位置直接生成一个元素。和emplace()不同的是,该函数添加新元素的过程是,先构造元素,然后再将该元素移动或复制到容器的指定位置。 |
emplace() | C++11新添加的成员函数,其功能是insert()相同,即在指定的位置直接生成一个元素。和insert()不同的是,emplace()直接在容器指定位置构造元素,省去了复制或移动元素的过程。 |
erase() | 移除一个元素或某一区域内的多个元素。 |
clear() | 删除容器中所有的元素。 |
在实际应用中,常用 emplace()、emplace_front() 和 emplace_back() 分别代替 insert()、push_front() 和 push_back()。
语法格式 | 功能 |
---|---|
iterator insert(pos,elem) | 在迭代器pos指定的位置之前插入一个新元素elem,并返回表示新插入元素位置的迭代器。 |
iterator insert(pos,n,elem) | 在迭代器pos指定的位置之前插入n个元素elem,并返回表示第一个新插入元素位置的迭代器。 |
iterator insert(pos,first,last) | 在迭代器pos指定的位置之前,插入其他容器(不仅限于vector)中位于[first,last)区域的所有元素,并返回表示第一个新插入元素位置的迭代器。 |
iterator insert(pos,initlist) | 在迭代器pos指定的位置之前,插入初始化列表(用大括号{}括起来的多个元素,中间有逗号隔开)中所有的元素,并返回表示第一个新插入元素位置的迭代器。 |
list容器
基本介绍
STL list 容器,又称双向链表容器,即该容器的底层是以双向链表的形式实现的。这意味着,list 容器中的元素可以分散存储在内存空间里,而不是必须存储在一整块连续的内存空间中。
list初始化
根据不同的使用场景,有以下 5 种创建 list 容器的方式供选择。
- 创建一个没有任何元素的空 list 容器:```c
std::listvalues; 1
2
3
4
5
6
7
和空 array 容器不同,空的 list 容器在创建之后仍可以添加元素,因此创建 list 容器的方式很常用。
2.
创建一个包含 n 个元素的 list 容器:
```c
std::list<int> values(10);
通过此方式创建 values 容器,其中包含 10 个元素,每个元素的值都为相应类型的默认值(int类型的默认值为 0)。
3.
创建一个包含 n 个元素的 list 容器,并为每个元素指定初始值。例如:
1 | std::list<int> values(10, 5); |
如此就创建了一个包含 10 个元素并且值都为 5 个 values 容器。
4.
在已有 list 容器的情况下,通过拷贝该容器可以创建新的 list 容器。例如:
1 | std::list<int> value1(10); |
注意,采用此方式,必须保证新旧容器存储的元素类型一致。
5.
通过拷贝其他类型容器(或者普通数组)中指定区域内的元素,可以创建新的 list 容器。例如:
1 | //拷贝普通数组,创建list容器 |
list容器可用的成员函数
成员函数 | 功能 |
---|---|
begin() | 返回指向容器中第一个元素的双向迭代器。 |
end() | 返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。 |
rbegin() | 返回指向最后一个元素的反向双向迭代器。 |
rend() | 返回指向第一个元素所在位置前一个位置的反向双向迭代器。 |
cbegin() | 和begin()功能相同,只不过在其基础上,增加了const属性,不能用于修改元素。 |
cend() | 和end()功能相同,只不过在其基础上,增加了const属性,不能用于修改元素。 |
crbegin() | 和rbegin()功能相同,只不过在其基础上,增加了const属性,不能用于修改元素。 |
crend() | 和rend()功能相同,只不过在其基础上,增加了const属性,不能用于修改元素。 |
empty() | 判断容器中是否有元素,若无元素,则返回true;反之,返回false。 |
size() | 返回当前容器实际包含的元素个数。 |
max_size() | 返回容器所能包含元素个数的最大值。这通常是一个很大的值,一般是2-1,所以我们很少会用到这个函数。 |
front() | 返回第一个元素的引用。 |
back() | 返回最后一个元素的引用。 |
assign() | 用新元素替换容器中原有内容。 |
emplace_front() | 在容器头部生成一个元素。该函数和push_front()的功能相同,但效率更高。 |
push_front() | 在容器头部插入一个元素。 |
pop_front() | 删除容器头部的一个元素。 |
emplace_back() | 在容器尾部直接生成一个元素。该函数和push_back()的功能相同,但效率更高。 |
push_back() | 在容器尾部插入一个元素。 |
pop_back() | 删除容器尾部的一个元素。 |
emplace() | 在容器中的指定位置插入元素。该函数和insert()功能相同,但效率更高。 |
insert() | 在容器中的指定位置插入元素。 |
erase() | 删除容器中一个或某区域内的元素。 |
swap() | 交换两个容器中的元素,必须保证这两个容器中存储的元素类型是相同的。 |
resize() | 调整容器的大小。 |
clear() | 删除容器存储的所有元素。 |
splice() | 将一个list容器中的元素插入到另一个容器的指定位置。 |
remove(val) | 删除容器中所有等于val的元素。 |
remove_if() | 删除容器中满足条件的元素。 |
unique() | 删除容器中相邻的重复元素,只保留一个。 |
merge() | 合并两个事先已排好序的list容器,并且合并之后的list容器依然是有序的。 |
sort() | 通过更改容器中元素的位置,将它们进行排序。 |
reverse() | 反转容器中元素的顺序。 |
list 容器还有一个std::swap(x , y)非成员函数(其中 x 和 y 是存储相同类型元素的 list 容器),它和 swap() 成员函数的功能完全相同,仅使用语法上有差异。
list迭代器及用法
迭代器函数 | 功能 |
---|---|
begin() | 返回指向容器中第一个元素的双向迭代器(正向迭代器)。 |
end() | 返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。(正向迭代器)。 |
rbegin() | 返回指向最后一个元素的反向双向迭代器。 |
rend() | 返回指向第一个元素所在位置前一个位置的反向双向迭代器。 |
cbegin() | 和begin()功能相同,只不过在其基础上,正向迭代器增加了const属性,即不能用于修改元素。 |
cend() | 和end()功能相同,只不过在其基础上,正向迭代器增加了const属性,即不能用于修改元素。 |
crbegin() | 和rbegin()功能相同,只不过在其基础上,反向迭代器增加了const属性,即不能用于修改元素。 |
crend() | 和rend()功能相同,只不过在其基础上,反向迭代器增加了const属性,即不能用于修改元素。 |
前面章节已经详细介绍了 array、vector、deque 容器的迭代器,和它们相比,list 容器迭代器最大的不同在于,其配备的迭代器类型为双向迭代器,而不再是随机访问迭代器。
这意味着,假设 p1 和 p2 都是双向迭代器,则它们支持使用 ++p1
、 p1++
、 p1--
、 p1++
、 *p1
、 p1==p2
以及 p1!=p2
运算符,但不支持以下操作(其中 i 为整数):
- p1[i]:不能通过下标访问 list 容器中指定位置处的元素。
- p1-=i、 p1+=i、 p1+i 、p1-i:双向迭代器 p1 不支持使用 -=、+=、+、- 运算符。
- p1<p2、 p1>p2、 p1<=p2、 p1>=p2:双向迭代器 p1、p2 不支持使用 <、 >、 <=、 >= 比较运算符。
list容器底层实现原理
list容器底层存储结构
前面在讲 STL list 容器时提到,该容器的底层是用双向链表实现的,甚至一些 STL 版本中(比如 SGI STL),list 容器的底层实现使用的是双向循环链表。
使用链表存储数据,并不会将它们存储到一整块连续的内存空间中。恰恰相反,各元素占用的存储空间(又称为节点)是独立的、分散的,它们之间的线性关系通过指针(图 1 以箭头表示)来维持。
list容器节点结构
1 | template<typename T,...> |
可以看到,list 容器定义的每个节点中,都包含 _prev、_next 和 myval。其中,prev 指针用于指向前一个节点;next 指针用于指向后一个节点;myval 用于存储当前元素的值。
list容器迭代器的底层实现
和 array、vector 这些容器迭代器的实现方式不同,由于 list 容器的元素并不是连续存储的,所以该容器迭代器中,必须包含一个可以指向 list 容器的指针,并且该指针还可以借助重载的 *、++、–、==、!= 等运算符,实现迭代器正确的递增、递减、取值等操作。
因此,list 容器迭代器的实现代码如下:
1 | template<tyepname T,...> |
可以看到,迭代器的移动就是通过操作节点的指针实现的。
list容器的底层实现
本节开头提到,不同版本的 STL 标准库中,list 容器的底层实现并不完全一致,但原理基本相同。这里以 SGI STL 中的 list 容器为例,讲解该容器的具体实现过程。
SGI STL 标准库中,list 容器的底层实现为双向循环链表,相比双向链表结构的好处是在构建 list 容器时,只需借助一个指针即可轻松表示 list 容器的首尾元素。
如下是 SGI STL 标准库中对 list 容器的定义:
1 | template <class T,...> |
另外,为了更方便的实现 list 模板类提供的函数,该模板类在构建容器时,会刻意在容器链表中添加一个空白节点,并作为 list 链表的首个节点(又称头节点)。
使用双向链表实现的 list 容器,其内部通常包含 2 个指针,并分别指向链表中头部的空白节点和尾部的空白节点(也就是说,其包含 2 个空白节点)。
比如,我们经常构造空的 list 容器,其用到的构造函数如下所示:
1 | list() { empty_initialize(); } |
显然,即便是创建空的 list 容器,它也包含有 1 个节点。
除此之外,list 模板类中还提供有带参的构造函数,它们的实现过程大致分为以下 2 步:
- 调用 empty_initialize() 函数,构造带有头节点的空 list 容器链表;
- 将各个参数按照次序插入到空的 list 容器链表中。
由此可以总结出,list 容器实际上就是一个带有头节点的双向循环链表。如图 2 所示,此为存有 2 个元素的 list 容器:
在此基础上,通过借助 node 头节点,就可以实现 list 容器中的所有成员函数,比如:
1 | //begin()成员函数 |
感兴趣的读者,可下载 list 容器的实现源码。
list容器访问元素
list 容器不支持随机访问,未提供下标操作符 [] 和 at() 成员函数,也没有提供 data() 成员函数。
list添加(插入)元素
list 模板类中,与“添加或插入新元素”相关的成员方法有如下几个:
- push_front():向 list 容器首个元素前添加新元素;
- push_back():向 list 容器最后一个元素后添加新元素;
- emplace_front():在容器首个元素前直接生成新的元素;
- emplace_back():在容器最后一个元素后直接生成新的元素;
- emplace():在容器的指定位置直接生成新的元素;
- insert():在指定位置插入新元素;
- splice():将其他 list 容器存储的多个元素添加到当前 list 容器的指定位置处。
empty()和size()都可以判断容器是否为空,谁更好?
到目前为止,我们已经了解了 C++ STL 标准库中 vector、deque 和 list 这 3 个容器的功能和具体用法。学习过程中,读者是否想过一个问题,即这些容器的模板类中都提供了 empty() 成员方法和 size() 成员方法,它们都可以用来判断容器是否为空。
换句话说,假设有一个容器 cont,则此代码:
1 | if(cont.size() == 0) |
本质上和如下代码是等价的:
1 | if(cont.empty()) |
那么,在实际场景中,到底应该使用哪一种呢?
建议使用 empty() 成员方法。理由很简单,无论是哪种容器,只要其模板类中提供了 empty() 成员方法,使用此方法都可以保证在 O(1) 时间复杂度内完成对“容器是否为空”的判断;但对于 list 容器来说,使用 size() 成员方法判断“容器是否为空”,可能要消耗 O(n) 的时间复杂度。
注意,这个结论不仅适用于 vector、deque 和 list 容器,后续还会讲解更多容器的用法,该结论也依然适用。
那么,为什么 list 容器这么特殊呢?这和 list 模板类提供了独有的 splice() 成员方法有关。
深度剖析选用empty()的原因:
做一个大胆的设想,假设我们自己就是 list 容器的设计者。从始至终,我们的目标都是让 list 成为标准容器,并被广泛使用,因此打造“高效率的 list”成为我们奋斗的目标。
在实现 list 容器的过程中我们发现,用户经常需要知道当前 list 容器中存有多少个元素,于是我们想让 size() 成员方法的执行效率达到 O(1)。为了实现这个目的,我们必须重新设计 list,使它总能以最快的效率知道自己含有多少个元素。
要想令 size() 的执行效率达到 O(1),最直接的实现方式是:在 list 模板类中设置一个专门用于统计存储元素数量的 size 变量,其位于所有成员方法的外部。与此同时,在每一个可用来为容器添加或删除元素的成员方法中,添加对 size 变量值的更新操作。由此,size() 成员方法只需返回 size 这个变量即可(时间复杂度为 O(1))。
不仅如此,由于 list 容器底层采用的是链式存储结构(也就是链表),该结构最大的特点就是,某一链表中存有元素的节点,无需经过拷贝就可以直接链接到其它链表中,且整个过程只需要消耗 O(1) 的时间复杂度。考虑到很多用户之所以选用 list 容器,就是看中了其底层存储结构的这一特性。因此,作为 list 容器设计者的我们,自然也想将 splice() 方法的时间复杂度设计为 O(1)。
这里就产生了一个矛盾,即如果将 size() 设计为 O(1) 时间复杂度,则由于 splice() 成员方法会修改 list 容器存储元素的个数,因此该方法中就需要添加更新 size 变量的代码(更新方式无疑是通过遍历链表来实现),这也就意味着 splice() 成员方法的执行效率将无法达到 O(1);反之,如果将 splice() 成员方法的执行效率提高到 O(1),则 size() 成员方法将无法实现 O(1) 的时间复杂度。
也就是说,list 容器中的 size() 和 splice() 总有一个要做出让步,即只能实现其中一个方法的执行效率达到 O(1)。
值得一提的是,不同版本的 STL 标准库,其底层解决此冲突的抉择是不同的。以本教程所用的 C++ STL 标准模板库为例,其选择将 splice() 成员方法的执行效率达到 O(1),而 size() 成员方法的执行效率为 O(n)。当然,有些版本的 STL 标准库中,选择将 size() 方法的执行效率设计为 O(1)。
但不论怎样,选用 empty() 判断容器是否为空,效率总是最高的。所以,如果程序中需要判断当前容器是否为空,应优先考虑使用 empty()。
list删除元素
成员函数 | 功能 |
---|---|
pop_front() | 删除位于list容器头部的一个元素。 |
pop_back() | 删除位于list容器尾部的一个元素。 |
erase() | 该成员函数既可以删除list容器中指定位置处的元素,也可以删除容器中某个区域内的多个元素。 |
clear() | 删除list容器存储的所有元素。 |
remove(val) | 删除容器中所有等于val的元素。 |
unique() | 删除容器中相邻的重复元素,只保留一份。 |
remove_if() | 删除容器中满足条件的元素。 |
forward_list容器完全攻略
forward_list 是 C++ 11 新添加的一类容器,其底层实现和 list 容器一样,采用的也是链表结构,只不过 forward_list 使用的是单链表,而 list 使用的是双向链表。
H 表示链表的表头。
其它相关资料自行查阅cplusplus