Skip to content

Latest commit

 

History

History
178 lines (154 loc) · 8.91 KB

ch09.md

File metadata and controls

178 lines (154 loc) · 8.91 KB
Raw

第九章 顺序容器

顺序容器概述

  • 顺序容器（sequential container）：为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

顺序容器类型

容器类型 介绍
vector 可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢。
deque 双端队列。支持快速随机访问。在头尾位置插入/删除速度很快。
list 双向链表。只支持双向顺序访问。在list中任何位置进行插入/删除操作速度都很快。
forward_list 单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快。
array 固定大小数组。支持快速随机访问。不能添加或者删除元素。
string 与vector相似的容器，但专门用于保存字符。随机访问块。在尾部插入/删除速度快。
  • 除了固定大小的array外，其他容器都提供高效、灵活的内存管理。
  • forward_list和array是新C++标准增加的类型。
  • 通常使用vector是最好的选择，除非你有很好的理由选择其他容器。
  • 新标准库的容器比旧版的快得多。

容器库概览

容器操作

操作 解释
类型别名
iterator 此容器类型的迭代器类型
const_iterator 可以读取元素但不能修改元素的迭代器类型
size_type 无符号整数类型，足够保存此种容器类型最大可能的大小
difference_type 带符号整数类型，足够保存两个迭代器之间的距离
value_type 元素类型
reference 元素的左值类型；和value_type &含义相同
const_reference 元素的const左值类型，即const value_type &
构造函数
C c; 默认构造函数，构造空容器
C c1(c2); 构造c2的拷贝c1
C c(b, e) 构造c，将迭代器b和e指定范围内的所有元素拷贝到c
C c(a, b, c...) 列表初始化c
赋值和swap
c1 = c2; 将c1中的元素替换成c2中的元素
c1 = {a, b, c...} 将c1中的元素替换成列表中的元素（不适用于array）
a.swap(b) 交换a和b的元素
swap(a, b) 等价于a.swap(b)
大小
c.size() c中元素的数目（不支持forward_list）
c.max_size() c中可保存的最大元素数目
c.empty() 若c中存储了元素，返回false，否则返回true
添加/删除元素 不使用于array，在不同容器中，下面的借口都不同
c.insert(args) 将args里面的元素拷贝进c
c.emplace(inits) 使用inits构造c中的一个元素
c.erase(args) 删除args指定的元素
c.clear() 删除c中所有元素，返回void
获取迭代器
c.begin(), c.end() 返回指向c的首元素和尾元素之后位置的迭代器
c.cbegin(), c.cend() 返回const_iterator
反向容器的额外成员 不支持forward_list
reverse_iterator 按逆序寻址元素的迭代器
const_reverse_iterator 不能修改元素的逆序迭代器
c.rbegin(), c.rend() 返回指向c的尾元素和首元素之前位置的迭代器
c.crbegin(), c.crend() 返回const_reverse_iterator

迭代器

  • 迭代器范围：begin到end，即第一个元素到最后一个元素的后面一个位置。

  • 左闭合区间：[begin, end)

  • 左闭合范围蕴含的编程设定：

    • 如果begin和end相等，则范围为空。
    • 如果二者不等，则范围至少包含一个元素，且begin指向该范围中的第一个元素。
    • 可以对begin递增若干次，使得begin == end。

  • 顺序容器适配器（adapter）：stack，queue，priority_queue。

  • 直接复制：将一个容器复制给另一个容器时，类型必须匹配：容器类型和元素类型都必须相同。

  • 使用迭代器复制：不要求容器类型相同，容器内的元素类型也可以不同。

  • 接受容器大小做形参的构造函数只适用于顺序容器，而关联容器不支持这种初始化。

容器内元素的类型约束：

  • 元素类型必须支持赋值运算；
  • 元素类型的对象必须可以复制。
  • 除了输入输出标准库类型外，其他所有标准库类型都是有效的容器元素类型。

begin和end：

  • c.begin()：返回一个迭代器，它指向容器 c 的第一个元素。
  • c.end()：返回一个迭代器，它指向容器 c 的最后一个元素的下一位置。
  • c.rbegin()：返回一个逆序迭代器，它指向容器 c 的最后一个元素。
  • c.rend()：返回一个逆序迭代器，它指向容器 c 的第一个元素前面的位置。

顺序容器中添加元素的操作：

  • c.push_back(t)：在容器尾部添加t，返回void。
  • c.push_front(t)：在容器前端添加t，返回void，只适用于list和deque。
  • c.insert(p, t)：在迭代器p所指向的元素前插入t，返回指向新元素的迭代器。
  • c,insert(p, n, t)：在迭代器p所指向的元素前插入n个t的新元素，返回void。
  • c.insert(p, b, e)：在迭代器p偶只想的元素前插入由迭代器b和e标记的范围内的元素，返回void。

顺序容器的大小操作：

  • c.size()：返回容器中c的元素个数，类型：c::size_type。
  • c.max_size()：返回容器c可容纳的最多元素个数。
  • c.empty()：返回容器大小是否为0。
  • c.resize(n)：调整c的长度大小为n，多删少增。
  • c.resize(n,t)：调整长度为n，新增的元素值是t。

顺序容器访问元素：

  • c.back()：返回最后一个元素的引用，前提是c非空。
  • c.front()：返回第一个元素的引用，前提是c非空。
  • c[n]：返回下标是n的引用，只适用于vector和deque。
  • c.at(n)：返回下标是n的引用，只适用于vector和deque。

顺序容器删除元素：

  • c.erase(p)：删除迭代器p所指的元素。
  • c.erase(b, e)：删除迭代器b到e内的所有元素。
  • c.clear()：删除c内所有元素。
  • c.pop_back()：删除c的最后一个元素，返回void。
  • c.pop_front()：删除c的第一个元素，返回void，只适用于list和deque。

顺序容器的赋值操作：

  • c1=c2：删除c1所有元素，将c2的元素复制给c1。
  • c1.swap(c2)：交换内容。
  • c.assign(b, e)：先删除c所有元素，将迭代器b到e标记范围内所有元素复制到c中。
  • c.assign(n, t)：先删除c所有元素，将c中心设置为存储n个值为t的元素。

vector vs. list：

  • vector容器的元素是连续存放的；
  • list容器的元素是非连续存放（链表）；
  • vector和deque支持快速随机访问；
  • list类型可以支持

string：

  • s.insert(p, t)：在迭代器p指向的元素之前插入t，返回指向t的迭代器。
  • s.insert(p, n, t)：在迭代器p指向的元素之前插入n个值为t的新元素，返回void。
  • s.insert(p, b, e)：在迭代器p指向的元素之前插入迭代器b到e范围内所有元素，返回void。
  • s.assign(b, e)：用b到e的元素替换s，返回s。
  • s.assign(n, t)：用值为t的n个副本替换s，返回s。
  • s.erase(p)：删除迭代器p指向的元素，返回下一个元素的迭代器。
  • s.erase(b, e)：删除从b到e的所有元素，返回下一个元素的迭代器。
  • 还可以用pos 和 len表示下标和长度，代替上面的b，e。
  • s.substr(pos, len)：返回当前对象的子串。
  • s.append(args)：将args串接在s后面，返回s引用。
  • s.replace(pos, len, args)：删除s中从下标pos开始的len个字符，并用args替换。
  • s.find(args)：args在s中的第一次出现。
  • s.rfind(args)：最后一次出现。
  • string采用字典顺序比较。

适配器：

  • 适配器是使一事物的行为类似于另一事物的行为的一种机制，例如stack可以使任何一种顺序容器以栈的方式工作。
  • 初始化 deque<int> deq; stack<int> stk(deq);
  • 默认的stack和queue都是基于deque实现，priority_queue是基于vector实现。
  • 创建适配器时，指定一个顺序容器，可以覆盖默认的基础容器： stack<string, vector<string> > str_stk;。

stack：

  • s.pop()：删除栈顶元素，不返回。
  • s.top()：返回栈顶元素，不删除。
  • s.push(item)：雅俗新元素。

queue和priority_queue：

  • q.pop()：删除队首元素，但不返回。
  • q.front()：返回队首元素的值，不删除。
  • q.top()：返回具有最高优先级的元素值，不删除。
  • q.push(item)：在队尾压入一个新元素。
  • ****：
  • ****：
  • ****：
  • ****：
  • ****：
  • ****：
  • ****：
  • ****：