C++ Seq Container

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

• vector：可变大小数组，支持快速随机访问
• deque：双端队列，支持快速随机访问
• list：双向链表，只支持双向顺序访问
• forward_list：单向链表，只支持单向顺序访问
• array：固定大小数组
• string：与 vector 类似，仅用于保存和字符

选取顺序容器的一些准则：

1. 与内置数组相比，array 是一种更安全，更容易使用的数组类型，现代 C++程序应该使用标准库容器，而不是更原始的数据结构比如内置数组
2. 除非有很好的理由选择其他容器，否则使用 vector
3. 其余的选择准则可以根据数组/链表/队列等数据结构的性质来判定

容器库与顺序容器操作

关于顺序容器的大部分操作都可以在 C++的 API 中查到，本文不再赘述，在这里仅谈几个注意事项： 关于迭代器：

1. 迭代器的 c.end()指向的是最后一个元素之后的位置，c.begin()与 c.end()这样一组迭代器的范围是左闭区间，右开区间
2. 单向链表 forward_list 不支持迭代器的递减操作，根据单向链表的数据结构性质很容易理解
3. begin 和 end 相等则范围为空，不等则至少包含一个元素
4. 将一个容器创建为另一个容器的拷贝的时候，需要两个容器的类型和其元素类型都一致，在传入迭代器范围进行拷贝的时候不需要元素类型一致，只要能转换成对应元素就可以。
5. 除了 string 之外，指向容器的迭代器、引用和指针在 swap 之后都不会失效，仍指向 swap 之前的那些元素，但是对于 string，它们都会失效。

关于swap：未完待续 关于forward_list：未完待续 关于string：未完待续

关于 vector 的扩容

vector 对象是连续存储的，标准库实现者采取了可以减少容器空间重新分配次数的策略，当不得不获取新的内存空间时，vector 和 string 的实现通常会分配比新的空间需求更大的内存空间，在使用该策略后，其扩张速度通常比 list 和 deque 快得多。

需要注意 capacity 和 size 的区别：容器的 size 是指它已经保存的元素的数目；而 capacity 则是在不分配新的内存空间的前提下其最多能保存的元素个数。

容器适配器

除了顺序容器外，标准库还定义了三个顺序容器适配器：stack，queue 和 priority_queue。适配器(adapter)是标准库中的一个通用概念。容器，函数和迭代器都有适配器。本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型。

例如，stack 适配器接受一种已有的容器类型，使其行为看起来像 stack 一样。可以理解为利用某种顺序容器实现的 stack 类，并且抽象出来了 pop()，push()等操作。

priority_queue 和 queue 的区别在于 priority_queue 可以为队列中的元素建立优先级。至于 stack，queue，priority_queue 三者的具体操作细节，可以查看 C++的相关 API。