8、C++ Primer 4th 笔记，顺序容器(1)-阿里云开发者社区

1、所谓泛型，指的是两个方面：这些算法可作用于各种不同的容器类型，而这些容器又可以容纳多种不同类型的元素。

2、顺序容器：将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素。

顺序容器

vector

支持快速随机访问

list

支持快速插入/删除

deque

双端队列

顺序容器适配器

stack

后进先出（LIFO）堆栈

queue

先进先出（FIFO）队列

priority_queue

有优先级管理的队列

3、容器元素的初始化

容器构造函数

C<T> c;

创建一个名为 c 的空容器。C 是容器类型名，如 vector，T 是元素类型，如 int 或 string 适用于所有容器。

C c(c2);

创建容器 c2 的副本 c；c 和 c2 必须具有相同的容器类型，并存放相同类型的元素。适用于所有容器。

C c(b,e);

创建 c，其元素是迭代器 b 和 e 标示的范围内元素的副本。适用于所有容器。

C c(n,t);

用 n 个值为 t 的元素创建容器 c，其中值 t 必须是容器类型 C 的元素类型的值，或者是可转换为该类型的值。只适用于顺序容器。

C c(n);

创建有 n 个值初始化（第 3.3.1 节）（value-initialized）元素的容器 c。只适用于顺序容器。

接受容器大小做形参的构造函数只适用于顺序容器。

4、容器元素必须满足以下两个约束：

• 元素类型必须支持赋值运算。

• 元素类型的对象必须可以复制。

引用不支持一般意义的赋值运算，因此没有元素是引用类型的容器。

除输入输出(IO)标准库类型（及auto_ptr类型）之外，所有其它标准库类型都是有效的容器元素类型。因为IO库不支持复制或赋值，因此不能创建存放IO类型对象的容器。

特别地，容器本身也满足上述定义，所以可以定义元素本身就是容器类型的容器。

vector< vector<string> > lines; // ok: space required between close >

5、C++ 定义的容器类型中，只有 vector 和 deque 容器提供下面两种重要的运算集合：迭代器算术运算，以及使用除了 == 和 != 之外的关系操作符来比较两个迭代器（== 和 != 这两种关系运算适用于所有容器）。P269

关系操作符只适用于vector,deque容器。list 容器的迭代器既不支持算术运算（加法或减法），也不支持关系运算（<=, <, >=, >），它只提供前置和后置的自增、自减运算以及相等（不等）运算。

6、使用迭代器，必须注意哪些操作会使迭代器失效。使用无效迭代器将会导致严重的运行时错误。

insert,push等操作将引起迭代器失效，使得不再指向容器中元素，为未定义行为。

7、容器定义的类型别名

size_type

无符号整型，足以存储此容器类型的最大可能容器长度

iterator

此容器类型的迭代器类型

const_iterator

元素的只读迭代器类型

reverse_iterator

按逆序寻址元素的迭代器

const_reverse_iterator

元素的只读（不能写）逆序迭代器

difference_type

足够存储两个迭代器差值的有符号整型，可为负数

value_type

元素类型

reference

元素的左值类型，是 value_type& 的同义词

const_reference

元素的常量左值类型，等效于 const value_type&

8、在容器中添加元素的操作

c.push_back(t)

在容器 c 的尾部添加值为 t 的元素。返回 void 类型

c.push_front(t)

在容器 c 的前端添加值为 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 类型

在容器中添加元素时，系统是将元素值复制到容器里。类似地，使用一段元素初始化新容器时，新容器存放的是原始元素的副本。被复制的原始值与新容器中的元素各不相关，此后，容器内元素值发生变化时，被复制的原值不会受到影响，反之亦然。

9、避免存储end操作返回的迭代器

示例程序

vector<int>::iterator first = v.begin(),
last = v.end(); // cache end iterator
// diaster: behavior of this loop is undefined
while (first != last) {}
应写成如下
// safer: recalculate end on each trip whenever the loop adds/erases
elements
while (first != v.end()) {
// do some processing
}

10、使用元素提供的关系操作符实现容器的关系运算。

11、容器大小

c.size()

返回容器 c 中的元素个数。返回类型为 c::size_type

c.max_size()

返回容器 c 可容纳的最多元素个数，返回类型为c::size_type

c.empty()

返回标记容器大小是否为 0 的布尔值

c.resize(n)

调整容器 c 的长度大小，使其能容纳 n 个元素，如果 n < c.size()，则删除多出来的元素；否则，添加采用值初始化的新元素

c.resize(n,t)

调整容器 c 的长度大小，使其能容纳 n 个元素。所有新添加的元素值都为 t

resize操作可能会使迭代器失效。

12、访问元素

c.back()

返回容器 c 的最后一个元素的引用。如果 c 为空，则该操作未定义

c.front()

返回容器 c 的第一个元素的引用。如果 c 为空，则该操作未定义c[n] 返回下标为 n 的元素的引用如果 n <0 或 n >= c.size()，则该操作未定义。只适用于 vector 和 deque 容器

c.at(n)

返回下标为 n 的元素的引用。如果下标越界，则该操作未定义。只适用于 vector 和 deque 容器

13、删除元素

c.erase(p)

删除迭代器p所指向的元素返回一个迭代器，它指向被删除元素后面的元素。如果p指向容器内的最后一个元素，则返回的迭代器指向容器的超出末端的下一位置。如果p本身就是指向超出末端的下一位置的迭代器，则该函数未定义

c.erase(b,e)

删除迭代器 b 和 e 所标记的范围内所有的元素返回一个迭代器，它指向被删除元素段后面的元素。如果 e 本身就是指向超出末端的下一位置的迭代器，则返回的迭代器也指向容器的超出末端的下一位置

c.clear()

删除容器 c 内的所有元素。返回 void

c.pop_back()

删除容器c的最后一个元素。返回 void。如果 c 为空容器，则该函数未定义

c.pop_front()

删除容器 c 的第一个元素。返回 void。如果 c 为空容器，则该函数未定义只适用于 list 或 deque 容器

都将使迭代器失效。

14、赋值操作首先删除其左操作数容器中的元素，然后将右操作数容器的所有元素插入到左边容器中。

示例程序

c1 = c2; // replace contents of c1 with a copy of elements in c2
// equivalent operation using erase and insert
c1.erase(c1.begin(), c1.end()); // delete all elements in c1
c1.insert(c1.begin(), c2.begin(), c2.end()); // insert c2

赋值和 assign 操作使左操作数容器的所有迭代器失效。swap操作则不会使迭代器失效。完成 swap 操作后，尽管被交换的元素已经存放在另一容器中，但迭代器仍然指向相同的元素，因位任何元素的位置都没有移动，只不过指向的容器不一样了，因此不会失效。

c1 = c2

删除容器 c1 的所有元素，然后将 c2 的元素复制给 c1。c1 和c2 的类型（包括容器类型和元素类型）必须相同

c1.swap(c2)

交换内容：调用完该函数后，c1 中存放的是 c2 原来的元素，c2 中存放的则是 c1 原来的元素。c1 和 c2 的类型必须相同。该函数的执行速度通常要比将 c2 复制到 c1 的操作快。