顺序容器

顺序容器内的元素按其位置存储和访问。

标准库定义了三种顺序容器类型：vector、list和deque（双端队列，读“deck”）。

标准库还提供了三种容器适配器（adaptor）。包括stack、queue和priority_queue类型。

顺序容器

• vector                   支持快速随机访问
• list                        支持快速插入删除
• deque                        双端队列

顺序容器适配器

• stack                         后进先出（LIFO）栈
• queue                       先进先出（FIFL）队列
• priority_queue          有优先级管理的队列

1.顺序容器的定义

#include<vector>

#include<list>

#include<deque>

所有容器都是类模板，要定义某种特殊的容器，必须在容器名后加一对尖括号，尖括号里面提供容器中存放的元素的类型。

例如，vector<string>、list<int>、deque<Sales_item>。

注意：为了使程序更清晰、简短，容器类型最常用的构造函数是默认构造函数。在大多数的程序中，使用默认构造函数能达到最佳运行时性能，并且使容器更容易使用。

2.容器元素的初始化

（1）C<T> c;  创建一个名为c的空容器。C是容器类型名，如vector，T是元素类型，如int或string。

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

（3）C c(b,e);  创建c，其元素是迭代器b和e标示的范围内元素的副本。适用与所有容器

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

（5）C c(n);  创建n个值初始化元素的容器c，只适用与顺序容器。

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

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

3.容器内元素的类型约束

C++语言中，大多数类型都可以用作容器的元素类型。容器元素类型必须满足以下两个约束：

• 元素类型必须支持赋值运算。
• 元素类型的对象必须可以复制。

注意：IO库类型不支持复制和赋值。因此，不能创建存放IO类型对象的容器。

4.容器的容器

vector< vector<string> > lines;

 注意：必须使用空格隔开两个相邻的 > 符号，以示这是两个分开的符号，否则，系统会认为 >> 是单个符号，为右移操作符，并结果导致编译时错误。

5.迭代器和迭代范围

 常用的迭代器的运算

*iter                               返回迭代器iter所指向的元素的引用

iter->men                      对iter进行解引用，获取指定元素名为mem的成员。等效于(*iter).mem

++iter                            对iter加1，使其指向容器里的下一个元素

iter++                            

--iter                              对iter减1，使其指向容器里的前一个元素

iter--  

iter1==iter2                   比较两个迭代器是否相等（或不等）。当两个迭代器指向同一个容器中的同一个元iter1 != iter2                  素，或者当它们指向同一个容器的超出末端的下一个位置，两个迭代器相等。

注意：迭代器first和last如果满足以下条件，则可以形成一个迭代器范围：

（1）它们指向同一个容器中的元素或超出末端的位置

（2）如果这两个迭代器不相等，则对first反复做自增运算必须能够到达last。换句话说，在容器中，last绝对不能位于first之前。

6.容器定义的类型别名

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

（2）iterator                                  此容器类型的迭代器类型

（3）const_iterator                       元素的只读迭代器类型

（4）reverse_iterator                   按逆序寻址元素的迭代器

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

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

（7）value_type                           元素类型

（8）reference                             元素的左值类型，是value_type&的同义词

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

7.begin和end成员

begin和end操作产生指向容器内第一个元素和最后一个元素的下一个位置的迭代器。

（1）c.begin()        返回一个迭代器，它指向容器c的第一个位置

（2）c.end()           返回一个迭代器，它指向容器c的最后一个元素的下一个位置

（3）c.rbegin()       返回一个逆序迭代器，它指向容器c的最后一个元素
（4）c.rend()          返回一个逆序迭代器，它指向容器c的第一个元素前面的位置

注意：上述操作都有两个不同版本：一个是const成员，另一个是非const成员。如果容器不是const，则这些操作返回iterator和reverse_iterator类型。如果容器是const，则其返回类型要加上const_前缀，也就是const_iterator和const_reverse_iterator类型。

8.在顺序容器中添加元素

（1）c.push_back(t)                 在容器c的尾部添加值为t的元素，返回void类型。

（2）c.push_front(t)           在容器c的前端添加值为t的元素，返回void类型。只适用于list和deque容器类型

（3）c.insert(p,t)               在迭代器p所指向的元素前面插入值为t的新元素。返回指向新添加的元素的迭代器

（4）c.insert(p,n,t)        在迭代器p所指向的元素前面插入n个值为t的新元素，返回void类型。

（5）c.insert(p,b,e);    在迭代器p指向的元素前面插入由迭代器b和e标记的范围内的元素。返回void类型。

9.容器大小的操作

（1）c.size();              返回容器c中的元素个数。返回类型为c::size_type

（2）c.max_size();     返回容器c可容纳的最多元素个数，返回类型为c::size_type

（3）c.empty();          返回标记容器大小的是否为0的布尔值

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

（5）c.resize(n,t);       调整容器c的长度大小，使其能容纳n个元素。所有新添加的元素值都为t