C++ Primer 笔记整理(二)顺序容器介绍

1.顺序容器概述
2.容器库操作介绍
3.顺序容器操作拓展
4.vector如何自增长
5.string拓展操作
6.容器适配器

一个容器就是一些特定类型对象的集合，顺序容器为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值。而是与元素加入容器时的位置相对应。接下来我们还要介绍有序和无序的关联容器，根据关键字的值来存储元素。

1.顺序容器概述

以下容器主要在下面两方面做了一些折中处理：

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

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

• forward_list和array是新C++标准增加的类型，与内置数组相比，array是一种更安全、更容易使用的数组类型。forward_list没有size操作，增加size操作会计算size大小，导致额外的开销。

以下是选择容器的基本原则：

1.除非你有很好的理由选择其他的容器，否则使用vector
2.如果你的程序有很多小的元素，且空间的额外开销很重要，不要使用list或者forward_list
3.如果程序需要随机访问元素，应该使用vector或deque
4.如果程序需要在容器的中间插入或者删除元素，应使用list或者forward_list
5.如果程序需要在头尾位置插入或者删除元素，但不会在中间位置插入或者删除元素，使用deque

2.容器库操作介绍

要使用特定的容器，需要引入一些头文件，例如deque / list等等，容器均定义为模板类。

容器操作
a.swap(b)	交换a和b的元素
swap(a, b)	与a.swap(b)等价
c.size()	c中元素数目，不支持forward_list和list
c.max_size()	c可保存最大元素数目
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

容器定义和初始化操作

初始化操作
C c;
C c1(c2)
C c1=c2
C c{a,b,c,....}
C c={a,b,c,...}
C c(b,e)	c初始化为迭代器b和e指定范围中的元素的拷贝。范围中元素的类型必须与CD额元素类型相容（array不适合）
C seq(n)	seq包含n个元素，这些元素进行了值初始化；此构造函数是explicit（string不适用）
C seq(n, t)	seq包含n个初始化值为t的元素

容器赋值操作：assign操作不适用于关联容器和array

容器赋值操作
seq.assign(b, e)	将seq中的元素替换为迭代器b和e所表示的范围中的元素，迭代器b和e不能指向seq中的元素
seq.assign(i1)	将seq中的元素替换为初始化列表i1中的元素
seq.assign(n, t)	将seq中的元素替换为n个值为t的元素

3.顺序容器操作拓展

操作函数
c.push_back(t)	在c的尾部创建一个值为t的元素，返回void
c.emplace_back(t)	同上
c.push_front(t)	在c的头部创建一个值为t的元素，返回void
c.emplace_front(t)	同上
c.insert(p, t)	在迭代器p指向的元素之前创建一个值为t的元素，返回指向新添加元素的迭代器。
c.emplace(p, t)	同上
c.insert(p, n, t)	在迭代器p指向的元素之前插入n个值为t的元素，返回指向新添加的第一个元素的迭代器，若n为0，则返回p
c.insert(p, b, e)	将迭代器b和e指定的范围内的元素插入到迭代器p指向的元素之前。b和e不能指向c中的元素。返回指向新添加第一个元素的迭代器；若范围为空，则返回p
c.insert(p, i1)	i1是一个花括号包围的元素值列表。将这些给定值插入到迭代器p指向的元素之前。返回指向新添加的第一个元素的迭代器，若列表为空，则返回p

• 1.上面这些操作会改变容器的大小；array不支持这些操作。
• 2.forward_list有自己专有版本的insert和二面place。
• 3.forward_list不支持push_back和emplace_back
• 4.vector和string不支持push_front和emplace_front

访问元素的函数
c.back()	返回c中尾元素的引用。若c为空，函数行为未定义
c.front()	返回c中首元素的引用。若c为空，函数行为未定义
c[n]
c.at(n)	返回下标为n的元素的引用。如果下标越界，则抛出out_of_range异常

4.vector如何自增长

vector与string类型提供了一些成员变量，允许我们利用这些函数来实现内存分配。capacity表示容器在不扩张内存空间的情况下可以容纳多少个元素。reverse允许我们通知容器它应该准备保存多少个元素。

容器大小管理操作
c.shrink_to_fit()	请将capacity()减少为与size()相同大小
c.capacity()	c可以保存多少个元素
c.reserve(n)	分配至少能容纳n个元素的内存空间

• 1. shrink_to_fit 只适用于vector、string和deque
• 2.capacity和reserve只适用于vector和string
  reverse并不改变容器中元素的数量，它仅影响vector预先分配多大的内存空间。
• 3.调用reverse永远也不会减少容器占用的内存空间，resize成员函数只改变容器中元素的数目，而不是容器的容量。

vector自动分配的原则是找到比size大的最近的2的幂次方。当然也可以用reverse来自动分配。

5.string拓展操作

substr函数返回一个string，它是原始string的一部分或全部的拷贝，传递给substr一个可选的开始位置和计数值。
string s("hello, world");
string s2 = s.substr(0, 5); // s2 = "hello"
如果开始位置超过了string的大小，则substr函数抛出了一个out_of_range异常。

修改string的操作
s.insert(pos, args)	在pos之前插入args字符串。pos可以是一个下标或者一个迭代器。
s.erase(pos, len)	删除从pos位置开始的len个字符。len没写，则删除从pos开始到末尾的所有字符。
s.assign(args)	s替换为args
s.append(args)	追加在s后面
s.replace(range, args)

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中的字符

compare操作
s2	比较s和s2
pos1, n1, s2	将s中从pos1开始的n1个字符与s2进行比较
pos1, n1, s2, pos2, n2	将s中从pos1开始的n1个字符与s2中从pos2开始的n2的字符进行比较

6.容器适配器

栈适配器；
队列适配器。