explorer

万丈高楼平地起,勿在浮沙筑高台

0%

[What] c++ 顺序容器

学习书籍:

学习 c++ 标准库下的顺序容器(sequential container)的操作。

顺序容器

顺序容器提供了快速顺序访问元素的能力,这种顺序不依赖于元素的值,而是与元素加入容器时的位置对应。

但这些顺序容器在以下方面都有不同的性能折中:

  • 向容器添加或从容器中删除元素的代价
  • 非顺序访问容器中元素的代价

标准库提供了下面这些容器:

类名 说明
vector 可变大小数组,支持快速随机访问。 但在尾部之外的位置插入或删除元素可能很慢!
deque 双端队列,支持快速随机访问,且在头尾位置插入/删除速度很快
list 双向链表,只支持双向顺序访问,在任何位置插入/删除速度都很快
forward_list 单向链表,只支持单向顺序访问,在任何位置插入/删除操作都很快
array 固定大小数组,支持快速随机访问,不能添加或删除元素
string 与 vector 类似,专用户保存字符

string 和 vector 将元素保存在连续的内存空间中,所以可以通过下标来快速寻址,但如果在中间位置添加或删除元素,则涉及到内存搬移,效率就低下。

  • 添加一个元素当遇到需要分配额外空间时,也会由于申请新的空间而变慢

list 和 forward_list 可以很快在任意位置添加和删除元素,但由于内存不连续无法通过下标随机访问,只能遍历。

deque 与 string 和 vector 类似,也支持快速随机访问,并且在头尾添加或删除元素速度很快,但在中间添加或删除元素依然很慢。

array 相比内置数组而言更加安全和容易使用。

顺序容器的选择原则如下:

  • 除非有更好的理由选择其他容器,否则应该使用 vector
  • 如果元素很小且内存空间很敏感,则不要使用 listforward_list
  • 如果程序要求随机访问,应该使用 vectordeque
  • 如果程序要求在容器中间插入或删除元素,应该使用 listforward_list
  • 如果程序需要在头尾位置插入或删除元素,但不会在中间位置进行插入或删除操作,应该使用 deque
  • 如果程序只有在读取输入时才需要在容器中间位置插入元素,随后需要随机访问元素,那么
    • 可以考虑先使用 vector 在尾部追加数据,然后使用 sort 函数来排序,而避免中间插入的低效性
    • 如果必须在中间插入,考虑在输入时使用 list ,输入完成后,将 list 内容拷贝到 vector 以提高访问效率

当需要编写 vectorlist 的公共操作函数时,可以使用迭代器而不是下标来访问元素。

容器库通用操作概览

每个容器都定义在一个头文件中,文件名与类型相同,并且 容器类均是模板类

既然是模板类,就需要在创建对象时为其指定元素的类型:

1
2
3
list<int> int_list;//元素类型为 int 的 List
deque<double> dq;//元素类型为 double 的 deque
vector<vector<string>> lines;//元素类型是 vector<string> 的 vector,其元素是内容为 string 的 vector

标准库提供的容器操作如下:

操作 说明
[类型别名] 习惯使用类型别名,而不去关注具体的类型
iterator 此容器类型的迭代器类型
const_iterator 此容器类型的只读迭代器类型
size_type 无符号整型,足够保存此容器类型最大可能容器的大小
difference_type 带符号整型,足够保存两个迭代器之间的距离
value_type 元素类型
reference 元素的左值引用,等同于 value_type &
const_reference 元素的 const 引用,等同于 const value_type &
[构造函数]  
C<type> c; 使用默认构造函数,容器内容为空
C<type> c1(c2); 当 c2 是对象时,c2 的内容拷贝到 c1 ,构造对象。当 c2 是数值时,创建 c2 个元素的对象
C<type> c(b,e) 当为迭代器时,将迭代器 b 和 e 指定的范围内的元素(不包括 e)拷贝到 c( array不支持 )。当 b 为数值, e 为值时,创建 b 个元素值为 e 的对象
c<type> c{a,b,c…} 列表初始化 c
[赋值与 swap]  
c1 = c2; c1 中的元素替换为 c2 中的元素
c = {a,b,c…} c1 中的元素替换为列表中的元素( 不适用于 array
a.swap(b) 交换 a 和 b 的元素
swap(a,b) 同上
[assgan] (不适用于 array)  
a.assign(b,e) 将 a 中的元素替换为迭代器 b 和 e 所表示的范围中的元素。 迭代器 b 和 e 不能指向 a 中的元素
a.assign(il) 将 a 中的元素替换为初始化列表 il 中的元素
a.assign(n,t) 将 a 中的元素替换为 n 个值为 t 的元素
[大小]  
c.size() 返回 c 中元素的数目( 不支持 forware_list
c.max_size() 返回 c 可以存放最大元素的数目
c.empty() 当 c 为空返回 true
[添加/删除元素](不适用于 array) 在不同容器中,这些操作的接口都不同
c.insert(args) 将 args 中的元素拷贝进 c
c.emplace(inits) 使用 inits 构造 c 中的一个元素
c.erase(args) 删除 args 指定的元素
c.clear() 删除 c 中的所有元素
[关系运算符]  
(==,!=) 所有容器都支持
(<,<=,>,>=) 无序关联容器不支持
[获取迭代器]  
c.begin(),c.end() 返回指向 c 的首元素和 尾元素之后位置 的迭代器
c.cbegin(),c.cend() 同上,但此迭代器是只读的
[反向容器的额外成员](不支持 forward_list)  
reverse_iterator 按逆序寻址元素的迭代器
const_reverse_iterator 按逆序寻址元素的只读迭代器
c.rbegin(),c.rend() 返回指向 c 的尾元素和 首元素之前位置 的迭代器
c.crbegin(),c.crend() 同上,只是返回的迭代器是只读的

迭代器

迭代器允许通过解引用运算符来实现访问容器内容的功能,标准库容器的所有容器都定义了递增运算符,其中 forward_list 不支持递减运算符。

迭代器的 begin()end() 方法表示了容器的范围,它们是左闭合区间:

[begin, end)
  • end 与 begin 指向相同的位置,但不能指向 begin 之前的位置
  • 如果 begin 与 end 相等,则容器为空
  • 如果 begin 与 end 不等,则容器至少包含一个元素,且 begin 指向该范围中的第一个元素
  • 可以对 begin 递增若干次,使得 begin == end

容器類型成員

使用容器的類型成員需要顯示的使用其类型名:

1
2
3
4
//定义类型为 list<string> 的迭代器
list<string>::iterator iter;
//定义类型为 vector<int>::differenct_type 的值
vector<int>::difference_type count;

begin 和 end 成员

begin 和 end 成员带 r 的版本返回反向迭代器,带 c 开头的版本返回 const 迭代器.

1
2
3
4
5
list<string> a = {"a", "b", "c"};
auto it1 = a.begin(); //list<string>::iterator
auto it2 = a.cbegin();//list<string>::const_iterator
auto it3 = a.rbegin();//list<string>::reverse_iterator
auto it4 = a.crbegin();//list<string>::const_reverse_iterator

容器的定义与初始化

array 之外,其他容器的默认构造函数都会创建一个指定类型的空容器,且都可以接受指定容器大小和元素初始值的参数.

将一个容器初始化为另一个容器的拷贝

将一个新容器创建为另一个容器的拷贝方法有两种:

  • 直接拷贝整个容器
  • 拷贝由一个迭代器对指定的元素范围(array 除外)

为了创建一个容器为另一个容器的拷贝,两个容器的类型及其元素类型必须匹配。

但当传递迭代器参数来拷贝一个范围时,新容器和原容器的容器类型和元素类型都可以不同,只要能够元素转换即可:

1
2
3
4
5
6
7
8
9
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};

list<string> list2(authors);//正确,类型匹配
deque<string> authList(authors);//错误,容器的类型不匹配
vector<string> words(articles);//错误,容器的元素类型不匹配

//正确,取出原容器的值进行依次初始化,且const char * 可以转换为 string
forward_list<string> words(articles.begin(), articles.end());

列表初始化

除 array 之外的容器类型,初始化列表还隐含地指定了容器的大小,容器将包含与初始值一样多的元素。

标准库的 array 具有固定大小

定义一个 array 时,必须指定容器的大小:

1
2
array<int, 42>;//创建大小为 42 个 int 类型元素的数组
array<string, 10>;//创建大小为 10 个 string 类型元素的数组

同理,在使用 array 的类型别名时,除了指定元素类型,还要指定其大小

  • 所以啊,能用 vector 就尽量用 vector 吧
1
2
array<int, 10>::size_type i;//正确
array<int>::size_type j;//错误

由于 array 在定义时指定了其大小,那么一个默认构造的 array 就是非空的。

如果对 array 进行列表初始化,那么初始值的数目必须等于或小于 array 的大小。

虽然内置数组类型不行直接进行拷贝和对象赋值操作,但 array 确可以:

1
2
3
4
5
int digs[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int cpy[10] = digs;//错误,内置数组无法直接拷贝

array<int, 10> digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
array<int, 10> copy = digits;//正确,类型和大小一样,可以直接拷贝

赋值和 swap

需要注意的是: 当使用直接拷贝的形式赋值时,如果两个容器原来的大小不同,而赋值运算后两者的大小都与右边容器的原大小相同。

除 array 外,swap 不对任何元素进行拷贝、删除或插入操作,而是交换两个容器的内部数据结构,因此操作很快。

  • 除 string 外,指向容器的迭代器、引用和指针在 swap 操作之后都不会失效,仍然指向 swap 操作之前所指向的那些元素
  • swap 两个 array 会真正交换它们的元素,因此交换两个 array 所需要的时间与 array 中元素的数目成正比

关系运算符

比较两个容器实际上是进行元素的逐对比较,工作方式与 string 类似:

  • 如果两个容器具有相同大小且所有元素都相等,则两个容器相等。
  • 如果两个容器大小不同,但较小容器中每个元素都等于较大容器中的对应元素,则较小容器小于较大容器
  • 如果两个容器的都不是另一个容器的前缀子序列,则它们的比较结果取决于第一个不相等的元素的比较结果

顺序容器操作

向顺序容器添加元素

除 array 外,所有标准库容器都可以动态的添加或删除元素来改变容器的大小:

  • forward_list 不支持 push_back 和 emplace_back,有自己专有的 insert 和 emplace
  • vector 和 string 不支持 push_front 和 emplace_front
  • 向一个 vector、string 或 deque 插入元素会使所有指向容器的迭代器、引用和指针失效
操作 说明
c.push_back(t) / c.emplace_back(args) 在 c 尾部创建一个值为 t 或由 args 创建的元素
c.push_front(t) / c.emplace_front(args) 在 c 头部创建一个值为 t 或由 args 创建的元素
c.insert(p,t) / c.emplace(p,args) 在迭代器 p 指向的元素之前创建一个值为 t 或由 args 创建的元素
c.insert(p,n,t) 在迭代器 p 指向的元素之前插入 n 个值为 t 的元素
c.insert(p,b,e) 将迭代器 b,e 指定范围内的元素插入到迭代器 p 指向的元素之前。 b,e不能指向 c 中的元素
c.insert(p,il) il是一个花括号包围的元素值列表,将这些值插入到迭代器 p 指向的元素之前

大部分情况下向 vector 和 string 尾部添加元素,或向 deque 首尾添加元素效率都很高。 但当原有的内存占满以后,那就需要重新分配一块更大的内存,然后将元素从旧空间移动到新的空间中,这个时候消耗的时间就比较多。

insert 方法通过迭代器来决定插入元素的位置,由于迭代器可能指向容器尾部之后不存在的元素的位置,所以 insert 函数将元素插入到迭代其所指定的位置之前。

  • vector 不支持 push_front 方法,但可以使用 insert 达到同样的效果 : c.insert(c.begin(), val)

当调用 push 或 insert 成员函数时,实际上是将元素类型的对象进行传递,这些对象被拷贝到容器中。

  • 这些方法会将值进行一次拷贝

当调用 emplace 成员函数时,则是将参数传递给 元素类型的构造函数 ,在容器管理的内存空间中直接创建对象。

  • 也就是说,使用 emplace 方法的参数必须与元素类型的构造函数相匹配。

访问元素

操作 说明
c.back() 返回 c 中的尾元素的引用,越界则行为未定义
c.front() 返回 c 中首元素的引用,越界则行为未定义
c[n] 返回 c 中下标为 n 的元素的引用,若 n 超出范围,则函数行为未定义
c.at(n) 返回下标为 n 的元素的引用,若 n 超出范围,则抛出 out_of_range 异常,使用 at 要比直接使用下标要更好

在使用访问元素操作时,要养成好的习惯,先使用 empty() 方法确认容器非空后再进行访问。

以上操作返回的都是 引用 ,可以用来改变元素的值:

1
2
3
4
5
6
7
8
if(!c.empty())
{
c.front() = 42;//修改 c 中第一个元素的值为 42
auto &v = c.back();
v = 1024; //修改 c 中最后一个元素的值为 1024
auto v2 = c.back();
v2 = 0;//此时 v2 是最后一个元素的拷贝
}

删除元素

操作 说明
c.pop_back() 删除 c 中尾元素
c.pop_front() 删除 c 中首元素
c.erase(p) 删除迭代器 p 所指定的元素,返回指向被删元素之后元素的迭代器
c.erase(b,e) 删除迭代器 b 和 e 所指定范围内的元素。
c.clear() 删除 c 中的所有元素,等价于 c.erase(c.begin(), s.end())

删除元素的操作会改变容器的大小,所以不适用于 array。

同样的,在删除元素之前,必须先检查容器中是否有该元素。

forward_list 的特殊方法

单向链表的删除操作除了删除当前节点,还要修改前驱节点的 next 指针,但由于单向链表无法获取其前驱节点,所以一般是在当前节点上删除下一个节点。

所以针对 forward_list 具有其独有的方法:

操作 说明
lst.before_begin() 返回链表的表头(首元素之前的位置)的迭代器,此迭代器不能解引用
lst.cbefore_begin() 同上,但返回的是 const_iterator
lst.insert_after(p,t) 在迭代器 p 之后的位置插入对象 t
lst.insert_after(p,n,t) 在迭代器 p 之后的位置插入 n 个对象 t
lst.insert_after(p,b,e) 在迭代器 p 之后的位置插入迭代器 b,e 之间的值
lst.insert_after(p,il) 在迭代器 p 之后的位置插入列表 il
emplace_after(p,args) 使用 args 在 p 指定的位置之后创建一个元素
lst.erase_after(p) 删除 p 之后的元素
lst.erase_after(b,e) 删除从 b 到 e 之间的元素,返回被删元素之后的迭代器

改变容器大小

操作 说明
c.resize(n) 调整 c 的大小为 n 个元素,若 n < c.size() 则多的元素会被丢弃
c.resize(n,t) 调整 c 的大小为 n 个元素, 新添加的元素 都初始化为 t

当然,这些操作无法适用于 array。

vector 和 string 还提供了管理容量的成员函数。 vector 和 string 为了提高扩容操作的效率,就在容器容量不够时,一次性申请足够大的多内存,然后进行一次性内存搬移。

  • 一般是申请原来空间两倍大的内存
操作 说明
c.capacity() 在不扩张内存空间的情况下,可以容纳的元素个数,适用于 vector、string
c.reserve(n) 分配至少能容纳 n 个元素的内存空间,适用于 vector、string
c.shrink_to_fit() 将 capacity() 减小为与 size() 相同的大小,适用于 vector、string、deque

需要注意:

  • reserve 的参数只能扩大内存空间,不能减小, resize()只改变元素的数目,而不是容器的容量!
    • 当 resize() 的值大于 capacity() 时,才会扩大内存空间
  • size() 指的是已保存元素的数目,而 capacity() 则是在不分配新内存空间的前提下,最多可以保存元素的数目

额外的 string 操作

string 在顺序容器的基础上提供了以下额外操作:

构造 string

操作 说明
string s(cp,n) cp 数组中前 n 个字符的拷贝初始化 s
string s(s2,pos2) string s2 从下标 pos2 开始的字符拷贝初始化 s
string s(s2,pos2,len2) string s2 从下标 pos2 开始拷贝 len2 个字符初始化 s
s.substr(pos,n) 返回一个 string,s 中从 pos 开始的 n 个字符拷贝

改变 string

操作 说明
s.insert(pos,args) 在 pos 之前插入 args 指定的字符
s.erase(pos,len) 删除从位置 pos 开始的 len 个字符
s.assign(args) 将 s 中的字符替换为 args 指定的字符
s.append(args) 将 args 追加到 s
s.replace(range,args) 删除 s 中范围 range 内的字符,替换为 args 指定的字符

args 可以是下列形式之一,append() 和 assign() 可以使用所有形式:

形式 说明
str 字符串 str
str,pos,len str 中从 pos 开始最多 len 个字符
cp,len 从 cp 指向的字符数组的前 len 个字符
cp cp 指向的以空字符结尾的字符数组
n,c n个字符 c
b,e 迭代器 b 和 e 指定的范围内的字符
初始化列表 花括号包围的,以逗号分隔的字符列表

replace() 和 insert() 所允许的 args 形式依赖于 range 和 pos 是如何指定的:

replace replace insert insert args 可以是
(pos,len,args) (b,e,args) (pos,args) (iter,args  
str
str,pos,len
cp,len
cp
n,c
b2,e2
初始化列表

string 内搜索

操作 说明
s.find(args) 查找 s 中 args 第一次出现的位置
s.rfind(args) 查找 s 中 args 最后一次出现的位置
s.find_first_of(args) 在 s 中查找 args 中任何一个字符第一次出现的位置
s.find_last_of(args) 在 s 中查找 args 中任何一个字符最后一次出现的位置
s.find_first_not_of(args) 在 s 中查找第一个不在 args 中的字符
s.find_last_not_of(args) 在 s 中查找最后一个不在 args 中的字符

args 必须是以下形式之一:

形式 说明
c,pos 从 s 中位置 pos 开始查找字符 c
s2,pos 从 s 中位置 pos 开始查找字符串 s2
cp,pos 从 s 中位置 pos 开始查找指针 cp 指向的以空字符结尾的 c 风格字符串
cp,pos,n 从 s 中位置 pos 开始查找指针 cp 指向的数组前 n 个字符

比较

操作 说明
s.compare(s2) 比较 s 和 s2
s.compare(pos1,n1,s2) 将 s 中从 pos1 开始的 n1 个字符与 s2 进行比较
s.compare(pos1,n1,s2,pos2,n2) 将 s 中从 pos1 开始的 n1 个字符与 s2 中从 pos2 开始的 n2 个字符比较
s.compare(cp) 比较 s 与 cp 指向的字符数组
s.compare(pos1,n1,cp) 同 s.compare(pos1,n1,s2)
s.compare(pos1,n1,cp,n2) 将 s 中从 pos1 开始的 n1 个字符与指针 cp 指向地址开始的 n2 个字符进行比较

数值转换

操作 说明
to_string(val) 返回数值 val 的string
stoi(s,p,b) 返回 s 的起始子串表示整数内容的数值,p保存第一个非数值字符下标,b表示转换所用基数
stol(s,p,b) long 版本
stoul(s,p,b) unsigned long
stoll(s,p,b) long long
stoull(s,p,b) unsigned long long
stof(s,p) float
stod(s,p) double
stold(s,p) long double

容器适配器

除了顺序容器外,标准库还定义了 3 个顺序容器适配器:stack、queue、priority_queue。

  • 适配器(adaptor):能使某种事物的行为看起来像另外一种事物一样
    • 比如可以用 vector<int> 来初始化一个 stack ,让其像栈一样被操作
  • 所有适配器都要求容器具有添加、删除、访问尾元素的能力,所以 array,forward_list 不能用来构造适配器
  • stack 只要求 push_back、pop_back、back操作,可以用 deque、list、vector 构造
  • queue 要求 back、push_back、front、push_front,所以只能构造于 list 或 deque 之上
  • priority_queue 除了 front、push_back、pop_back 要求之外还需要有随机访问能力,所以只能构造于 vector 或 deque 之上
操作 说明
size_type 保存当前类型的最大对象的大小
value_type 元素类型
container_type 底层容器类型
A a; 创建一个空适配器
A a(c); 容器 c 初始化 a
a.empty() 为空返回真
a.size() 元素的数目
swap(a,b) / a.swap(b) 交换 a 和 b 的内容

可以使用一个容器来初始化一个新的栈,也可以创建一个空的适配器时来重载默认的容器类型:

1
2
3
4
5
6
7
8
deque<int> deq;
//创建一个元素是 int 的栈,并使用 deq 初始化它
stack<int> stk(deq);

//在 vector 上实现空栈,元素类型是 string
stack<string, vector<string>> str_stk;
//str_stk2 在 vector 上实现,初始化时保存 svec 的拷贝
stack<string, vector<string>> str_stk2(svec);
操作 说明
s.pop() 删除栈顶,但不返回元素值
s.push(item) 插入新元素到栈顶
s.emplace(args) args 构造元素到栈顶
s.top() 返回栈顶元素,但不弹出元素

队列

操作 说明
q.pop() 返回queue的首元素,或 priority_queue 的最高优先级元素,但不删除元素
q.front() 返回首元素,但不删除此元素
q.back() 返回尾元素,但不删除此元素( 只适用于queue
q.top() 返回最高优先级元素,但不删除该元素( 只适用于 priority_queue
q.push(item) /q.emplace(args) 在 queue 末尾或 priority_queue 中恰当位置创建一个元素
Last Updated 2020-06-28 Sun 11:59.
Render by hexo-renderer-org with Emacs 26.3 (Org mode 9.3.7)