春暖花开

C++中三种顺序容器的总结

在 C++ 中,标准库提供了三种顺序容器:vector, list, deque,还有三种顺序容器适配器:stack, queue, priority_queue,要使用这些容器,需要在源程序中包含对应的头文件,如 include<vector>。本文主要总结容器的操作。

容器类型:

  • vector: 支持快速随机访问(顺序存储)
  • list : 支持快速插入、删除(非顺序存储)
  • deque : 双端队列
  • stack : 后进先出堆栈
  • queue : 先进先出队列
  • priority_queue : 有优先级管理的队列

容器构造函数

迭代器

每种容器类型都提供若干共同工作的迭代器类型。与容器类型一样,所有迭代器具有相同的接口:如果某种迭代器支持某种操作,那么支持这种操作的其他迭代器也会以相同的方式支持这种操作。

1
container<elemtype>::iterator iter; //声明一个迭代器

所有容器均支持的迭代器操作:

1
2
3
4
5
*iter 返回迭代器 iter 所指向的元素的引用
iter->mem iter 进行解引用,获取指定元素中名为 mem 的成员。等效于(*iter).mem
++iter/iter++ : 给 iter 1,使其指向容器里的下一个元素
--iter/iter-- : 给 iter 1,使其指向容器里的前一个元素
iter1 == iter2/iter1 != iter2 : 比较两个迭代器是否相等(或不等)。当两个迭代器指向同一个容器中的同一个元素,或者当它们都指向同一个容器的超出末端的下一位置时,两个迭代器相等

另外,vector 和 deque 的迭代器还提供额外的运算:

1
2
3
iter + n / iter - n : 在迭代器上加(减)整数值 n,将产生指向容器中前面(后面)第 n个元素的迭代器。新计算出来的迭代器必须指向容器中的元素或超出容器末端的下一位置
iter1 += iter2 / iter1 -= iter2
>, >=, <, <= 操作符

以上运算符仅适用于 vector 和 deque 的迭代器,因为这两种容器是顺序存储的,能够为元素提供快速,随机的访问它们确保可根据元素位置直接有效地访问指定的容器元素。这两种容器都支持通过元素位置实现的随机访问,因此它们的迭代器可以有效地实现算术和关系运算。

迭代器范围

左闭右开:[first, last)

编程意义:

  1. 当 first 与 last 相等时,迭代器范围为空;
  2. 当 first 与不相等时,迭代器范围内至少有一个元素,而且 first 指向该区间中的第一元素。此外,通过若干次自增运算可以使 first 的值不断增大,直到 first == last 为止。

容器定义的类型别名

容器的begin和end操作

另外,每个操作都有两个版本:const 和 非const,取决于容器的类型是 const 还是 非const

添加元素

正如上图所示,push_front 仅适用于 list 和 deque 。

另外,需要注意的是,插入元素之后可能会使之前的迭代器失效,需要谨慎考虑。

容器大小操作

访问元素

vector, deque 是顺序存储的,因此可通过下标访问。

删除元素

赋值与交换

swap 相当于先删除,然后再赋值,使用swap可以节省删除的成本。

容器自增长

对于大部分应用,使用 vector 容器是最好的。原因在于,标准库的实现者使用这样内存分配策略:以最小的代价连续存储元素。由此而带来的访问元素的便利弥补了其存储代价。

为了使 vector 容器实现快速的内存分配,其实际分配的容量要比当前所需的空间多一些。vector 容器预留了这些额外的存储区,用于存放新添加的元素。于是,不必为每个新元素重新分配容器。所分配的额外内存容量的确切数目因库的实现不同而不同。比起每添加一个新元素就必须重新分配一次容器,这个分配策略带来显著的效率。

capacity 和 reserve 成员

1
2
c.capacity() : 返回容器容量, capacity >= size
c.reserve(n) : 将容器的预留量设为 n

string 类型

在某些方面,可以将 string 看成是字符的容器,因此,大多数的容器操作也适合于 string 。


string 特有的插入和删除操作


子串操作


append/replace


append/replace 的参数 args


string 查找operator


args


string compare operator

容器适配器

除了顺序容器,标准库还提供了三种顺序容器适配器:queue、priority_queue 和 stack。

通用操作和类型:

stack

queue/priority queue

0%