Featured image of post C++ Primer Ch09

C++ Primer Ch09

Sequence Container

# 顺序容器

一个容器就是一些特定类型对象的集合,顺序容器(sequence container) 为程序员提供了控制元素存储和访问顺序的能力。

# 顺序容器概述

下面列出了标准库中的顺序容器,不同容器有不同的性能折中:

  • 想容器添加或从容器删除元素的代价。
  • 非顺序访问容器中元素的代价。
容器类型 介绍
vector 可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢。
deque 双端队列。支持快速随机访问。在头尾位置插入/删除速度很快。
list 双向链表。只支持双向顺序访问。在list中任何位置进行插入/删除操作速度都很快。
forward_list 单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快。
array 固定大小数组。支持快速随机访问。不能添加或者删除元素。
string vector相似的容器,但专门用于保存字符。随机访问块。在尾部插入/删除速度快。
  • 除了固定大小的 array 外,其他容器都提供高效、灵活的内存管理。
  • 通常使用 vector 是最好的选择,除非你有很好的理由选择其他容器。
  • 如果程序中有很多小的元素,且空间的额外开销很重要,则不要使用 listforward_list
  • 如果程序要求随记访问元素,应使用 vectordeque
  • 如果程序要求在容器的中间插入或删除元素,应使用 listforward_list
  • 如果程序需要再头尾位置插入或删除元素,但不会再中间位置进行操作,应使用 deque

# 容器库概念

容器类型操作上形成了一种层次:

  • 某些操作是所有容器类型都提供的。
  • 另一些操作仅针对顺序容器、关联容器或无序容器。

# 类型

操作 解释
iterator 此容器类型的迭代器类型
const_iterator 可以读取元素但不能修改元素的迭代器类型
size_type 无符号整数类型,足够保存此种容器类型最大可能的大小
difference_type 带符号整数类型,足够保存两个迭代器之间的距离
value_type 元素类型
reference 元素的左值类型;和value_type &含义相同
const_reference 元素的const左值类型,即const value_type &

# 构造函数

操作 解释
C c; 默认构造函数,构造空容器
C c1(c2);C c1 = c2; 构造c2的拷贝c1
C c(b, e) 构造c,将迭代器be指定范围内的所有元素拷贝到c
C c(a, b, c...) 列表初始化c
C c(n) 只支持顺序容器,且不包括array,包含n个元素,这些元素进行了值初始化
C c(n, t) 包含n个初始值为t的元素
  • 只有顺序容器的构造函数才接受大小参数,关联容器并不支持。
  • array具有固定大小。
  • 和其他容器不同,默认构造的array是非空的。
  • 直接复制:将一个容器复制给另一个容器时,类型必须匹配:容器类型和元素类型都必须相同。
  • 使用迭代器复制:不要求容器类型相同,容器内的元素类型也可以不同。

# 赋值和swap

操作 解释
c1 = c2; c1中的元素替换成c2中的元素
c1 = {a, b, c...} c1中的元素替换成列表中的元素(不适用于array
c1.swap(c2) 交换c1c2的元素
swap(c1, c2) 等价于c1.swap(c2)
c.assign(b, e) c中的元素替换成迭代器be表示范围中的元素,be不能指向c中的元素
c.assign(il) c中的元素替换成初始化列表il中的元素
c.assign(n, r) c中的元素替换为n个值是t的元素
  • 使用非成员版本的swap是一个好习惯。
  • assign操作不适用于关联容器和array

# 大小

操作 解释
c.size() c中元素的数目(不支持forward_list
c.max_size() c中可保存的最大元素数目
c.empty() c中存储了元素,返回false,否则返回true

# 添加元素

操作 解释
c.push_back(t) c尾部创建一个值为t的元素,返回void
c.emplace_back(args) 同上
c.push_front(t) c头部创建一个值为t的元素,返回void
c.emplace_front(args) 同上
c.insert(p, t) 在迭代器p指向的元素之前创建一个值是t的元素,返回指向新元素的迭代器
c.emplace(p, args) 同上
c.insert(p, n, t) 在迭代器p指向的元素之前插入n个值为t的元素,返回指向第一个新元素的迭代器;如果n是0,则返回p
c.insert(p, b, e) 将迭代器be范围内的元素,插入到p指向的元素之前;如果范围为空,则返回p
c.insert(p, il) il是一个花括号包围中的元素值列表,将其插入到p指向的元素之前;如果il是空,则返回p
  • 因为这些操作会改变大小,因此不适用于array
  • forward_list有自己专有版本的insertemplace
  • forward_list不支持push_backemplace_back
  • 当我们用一个对象去初始化容器或者将对象插入到容器时,实际上放入的是对象的拷贝。
  • emplace开头的函数是新标准引入的,这些操作是构造而不是拷贝元素。
  • 传递给emplace的参数必须和元素类型的构造函数相匹配。

# 访问元素

操作 解释
c.back() 返回c中尾元素的引用。若c为空,函数行为未定义
c.front() 返回c中头元素的引用。若c为空,函数行为未定义
c[n] 返回c中下标是n的元素的引用,n时候一个无符号证书。若n>=c.size(),则函数行为未定义
c.at(n) 返回下标为n的元素引用。如果下标越界,则抛出out_of_range异常
  • 访问成员函数返回的是引用。
  • at和下标操作只适用于stringvectordequearray
  • back不适用于forward_list
  • 如果希望下标是合法的,可以使用at函数。

# 删除元素

操作 解释
c.pop_back() 删除c中尾元素,若c为空,则函数行为未定义。函数返回void
c.pop_front() 删除c中首元素,若c为空,则函数行为未定义。函数返回void
c.erase(p) 删除迭代器p指向的元素,返回一个指向被删除元素之后的元素的迭代器,若p本身是尾后迭代器,则函数行为未定义
c.erase(b, e) 删除迭代器be范围内的元素,返回指向最后一个被删元素之后元素的迭代器,若e本身就是尾后迭代器,则返回尾后迭代器
c.clear() 删除c中所有元素,返回void
  • 会改变容器大小,不适用于array
  • forward_list有特殊版本的erase
  • forward_list不支持pop_back
  • vectorstring不支持pop_front

# 特殊的 forwad_list操作

  • 链表在删除元素时需要修改前置节点的内容,双向链表会前驱的指针,但是单向链表没有保存,因此需要增加获取前置节点的方法。
  • forward_list定义了before_begin,即首前(off-the-begining)迭代器,允许我们再在首元素之前添加或删除元素。
操作 解释
lst.before_begin() 返回指向链表首元素之前不存在的元素的迭代器,此迭代器不能解引用。
lst.cbefore_begin() 同上,但是返回的是常量迭代器。
lst.insert_after(p, t) 在迭代器p之后插入元素。t是一个对象
lst.insert_after(p, n, t) 在迭代器p之后插入元素。t是一个对象,n是数量。若n是0则函数行为未定义
lst.insert_after(p, b, e) 在迭代器p之后插入元素。由迭代器be指定范围。
lst.insert_after(p, il) 在迭代器p之后插入元素。由il指定初始化列表。
emplace_after(p, args) 使用argsp之后的位置,创建一个元素,返回一个指向这个新元素的迭代器。若p为尾后迭代器,则函数行为未定义。
lst.erase_after(p) 删除p指向位置之后的元素,返回一个指向被删元素之后的元素的迭代器,若p指向lst的尾元素或者是一个尾后迭代器,则函数行为未定义。
lst.erase_after(b, e) 类似上面,删除对象换成从be指定的范围。

# 改变容器大小

操作 解释
c.resize(n) 调整c的大小为n个元素,若n<c.size(),则多出的元素被丢弃。若必须添加新元素,对新元素进行值初始化
c.resize(n, t) 调整c的大小为n个元素,任何新添加的元素都初始化为值t

# 获取迭代器

操作 解释
c.begin(), c.end() 返回指向c的首元素和尾元素之后位置的迭代器
c.cbegin(), c.cend() 返回const_iterator
  • c开头的版本是C++11新标准引入的
  • 当不需要写访问时,应该使用cbegincend

# 反向容器的额外成员

操作 解释
reverse_iterator 按逆序寻址元素的迭代器
const_reverse_iterator 不能修改元素的逆序迭代器
c.rbegin(), c.rend() 返回指向c的尾元素和首元素之前位置的迭代器
c.crbegin(), c.crend() 返回const_reverse_iterator
  • 不支持forward_list
Built with Hugo
Theme Stack designed by Jimmy