顺序容器

顺序容器提供了控制元素存储和访问顺序的能力。

顺序容器

vector 容器大小可变，支持随机访问，在头部或中间插入元素很慢

string 仅用于保存字符，其余同上

list 双向链表，方便元素的插入，但不支持随机访问

forward_list 单向链表，其余同上

deque 双端队列，支持快速访问，头尾插入效率高

arrry 不支持添加和删除元素以及改变容器大小的操作。

原则上来说时根据用途来选择用的容器，但一般情况下都使用vector.

例如：程序在读取数据时需要在中间插入元素，随后随机访问元素时，可以使用一下两种方法：

直接在vector尾部追加数据，再调用sort重排容器内元素

  输入阶段使用list,输入成功后将list内容拷贝到vector

容器库概览

一般来说，每个容器都定义在一个头文件里，文件名与类型名相同，即使用vector必须添加<vector>头文件。

顺序容器可以保存任意类型的元素，此类型可以是另一容器。

迭代器

标准容器类型上的所有迭代器都允许我们访问容器中的元素，所有迭代器都定义了递增运算符。（特殊的：forward_list迭代器不支持递减运算符 ）。

一般由一对迭代器（begin和end或first和last ） 构成一个迭代器范围，第二个一般指向尾元素之后的位置，这种元素范围被称为左闭合区间。

[ begin, end )

end可以与begin指向相同的位置，但不能指向begin之前。

当begin!=end时，则范围内至少包含一个元素，此时对end叠加若干次，即可使begin==end.

此外，大多数容器还提供反向迭代器，与正向相比，各种操作都发生了颠倒，对反向迭代器执行++操作，会得到上一个元素。

begin和end也有别的版本，一般带r开头的版本返回反向迭代器，以c开头的版本返回const迭代器。一个普通的iterator可以转换为对应的const_iterator。

容器定义和初始化

有容器的使用就必须对容器进行定义和初始化：每个容器类型都定义了一个默认构造函数，除array外，其他容器的默认构造函数都会创建一个指定类型的容器，且都可以接受指定容器大小和元素初始化的参数。

容器初始化时，可以：

将一个容器初始化为另一个容器的拷贝，拷贝时可以拷贝整个容器，此时两容器类型和元素类型必须完全相同。 也可以只拷贝由迭代器指定的范围，当传递迭代器参数来拷贝一个范围时，不要求必须相同，只要能将拷贝元素转换为相同的类型即可。

还有就是列表初始化，如

list<string > authors = {"Milton ","Shakespe ","Austen " }; 此时不仅显式的指定了容器中每个元素的值，而且隐含的指定了容器的大小。

如果不提供元素初始值，则标准库会创建一个值初始化器。

标准库array

array在顺序容器中比较特殊， array不支持普通的容器构造函数，因为这些构造函数总是会切丁容器大小，而array在定义时已经指定了容器大小。在定义时，如果定义成如下形式：

       array<int >:: size_type j;

就是错误的，必须在定义时指定大小：

       array<int, 10 > :: size_type j;

赋值和swap

c1 = c2;  //将c1的内容替换为c2中元素的拷贝,如果此时两容器大小不同，赋值后都为c2的大小。

赋值相关运算会导致指向左边容器内部的迭代器，引用，指针等全部失效，而swap不会。

顺序容器还定义了一个名为assign的成员，允许我们从一个不同但相容的类型赋值，或从容器的一个子序列赋值，

names.assign(oldstyle.cbegin(), oldstyle.cend() );   //将names中的元素替换为迭代器指定的范围中的元素。

使用swap后，元素不会被移动，即指向容器的迭代器，引用和指针在swap后都不会失效。

容器大小操作

除array外，每个容器都有三个与大小相关的操作：

成员函数size返回容器中元素的数目。

empty当size为０时返回布尔值true,否则返回false.

max_size返回一个大于或等于该类型容器所能容纳的最大元素数的值。

容器之间是可以比较大小的：

等于是最容易判断的，即容器大小相同并且所含元素一一 相同。

若较小容器是较大容器的前缀子序列， 那么较大容器大于较小容器。

若不是前缀子序列，则他们的比较结果取决于第一个不相等的元素的比较结果。

注意：只有当元素类型定义了相应的　比较运算符时，我们才可以使用关系运算符来比较两个容器。

顺序容器和关联容器的不同之处在于两者组织元素的方式不同，这些不同直接影响元素的存储，访问，添加以及删除，下面介绍的是顺序容器所特有的操作。

除array外，所有标准库容器都提供灵活的内存管理，在运行时可以动态添加或删除元素来改变容器大小。注意插入元素后会使所有指向容器的迭代器，指针，引用失效。 因为不同容器使用不同的策略来分配元素空间，所以很多时候需要移动元素，而且向vector或string插入还有可能引起内存分配。

插入元素时，可以使用push_back追加到容器尾部，也可以使用push_front插入到容器头部，也可以使用insert函数插入指定位置。

insert

此函数可以接受迭代器参数， 将元素插入到迭代器所指位置之前。 如果范围为空，不插入任何元素，insert操作将第一个参数返回； 插入成功后返回第一个新加入元素的迭代器。根据这个特点，可以通过insert函数的返回值在容器中特定的位置反复插入元素。

emplace

新标准引入三个新成员，emplace_front、emplace、emplace_back，分别用来在容器头部，指定位置前和尾部添加元素。

emplace与push的区别：

push必须创建一个局部临时对象，然后将其压入容器，而emplace会在容器管理的内存空间中直接创建 对象。

假定c保存Sales_data元素，

c.emplace_back("029-048012", 25, 15.25);  　//使用参数的Sales_data构造函数

c.push_back("029-048012 ", 25, 15.25 );     //错误，没有接受三个参数的push_back版本

c.push_back(Sales_data("029-048012", 25, 15.25 ));    //正确，使用临时对象

访问元素

在容器中访问元素的成员函数返回的都是引用，如果容器是一个const对象，则返回值也是const引用。

获取容器中首元素和尾元素的方法有两种：

直接使用 f ront 和back成员 函数。 (特殊的，forward_list没有back函数 )，这两个操作分别返回首元素和尾元素的引用。

通过解引用begin和end 返回的迭代器来获取。注意end前先递减。

除了首尾访问，(string, vector, deque, array)都提供随机访问

随机访问一般只要注意不要使用越界的下标即可。如果我们希望确保使用的下标合法，可以使用at成员函数，如果下标越界，at会抛出一个out_of_range异常。

删除元素
pop_front和pop_back成员函数分别删除首元素和尾元素，vector和string不支持pop _front，forward_list不支持pop_back;

同样，可以删除首尾就有删除指定位置元素 的函数－－成员函数erase可以删除一个迭代器指定的元素，也可以删除一对迭代器范围内的元素，两种删除方式都返回指向删除的最后一个元素之后位置的迭代器。

若要删除容器内所有元素，我们可以使用clear也可以使用begin和end作为迭代器调用erase.

特殊的forward_list操作

前面已经发现，一些添加删除的函数避开了forward_list, 因为当我们添加删除元素时，为了使元素间不断开，往往是先访问其前驱，但单向链表没有简单的方法来访问前驱。所以为forward_list定义了一些特殊的函数诸如：insert_after, emplace_after, erase_after调用时处理该元素之后的元素。所以理所当然定义了before_begin,它返回一个首前迭代器， 用来处理他之后的首元素。

改变容器大小

使用函数resize来增大或缩小容器。

list<int >  ilist(10, 24 );  //ilist.size() = 10

ilist.resize(15, -1 ) ;   //在原容器后添5个-1.　-1省略时添0, 15改为5时意味着从ilist末尾删去5个24.

注意：如果是缩小容器，其内的迭代器，指针引用等失效。

编写改变程序的循环程序

如果程序调用的是erase或insert, 他们都返回迭代器，我们可以用其做参来实现循环更新。

但注意，不要保存end返回的迭代器，因为在循环体中，向容器的每一次添加元素都可能 造成迭代器的失效，end迭代器应在每次循环开始前重新获取。

vector对象是如何增长的

vector和string的实现通常会分配比新空间需求更大的空间，空间预留这些空间给新元素备用。

主要函数：

c.size()     //c中现在保存的元素多少

c.capacity()   //不重新分配内存空间的话，c可以保存多少元素

c.shrink_to_fit()     //请将capacity()减少为与size()相同大小

c.reserve(n )      //分配至少能容纳n个元素的内存空间

在执行insert操作时如果size与capacity相等，　或者调用resize和reserve时给定的大小超过当前capacity,　vector就会重新分配内存空间。

额外的string操作

三个构造函数 :

string s (cp, n );     //s是cp指向的数组中前n个元素的拷贝。

string s(s2, pos2 );   //s是string s2从下标s2开始的字符串的拷贝。

string s(s2, pos2, len2 );  //s是string s2从下标s2开始len2个字符串的拷贝。

这些构造函数接受一个string或const char*参数，但指针指向的数组不许以空字符结尾。

s.substr(pos, n); 返回一个string，包含s中从pos开始的n个值的拷贝，pos默认为0,n默认为s.size-pos.

除了迭代器的insert和erase版本外，string还提供了接受下标的版本。

s.insert(s.size(), 5, '!' );  //在s末尾插入5个！.

string 还有两个额外的成员函数：append和replace

append是在string末尾插入操作.  s.insert(s.size(), "qqq " ); 相当于s.append("qqq " );

replace实际上是调用erase和 insert的一种简写形式。

s.erase(11, 3);   //删除从11开始的３个字符

s.insert(11, "5th " );   //在11之前插入5th

相当于 s.replace(11, 3, "5th " );

string搜索操作

string类定义了６个不同的搜索函数，每个搜索操作都返回一个srting::size_type值，表示匹配发生位置的下标，搜索失败时，返回名为string :: npos的static成员，npos为unsigned类型，此初始值意味着npos等于任何string最大的可能大小。所有不能用int型或其他带符号类型来保存这些函数的返回值。

compare函数

根据s是等于，大于，还是小于参数指定的字符串，s.compare返回0, 整数或负数。

数值转换

新标准引入多个函数来实现数值的转换。

容器适配器

标准库定义了三个容器适配器stack, queue和priority_queue.

定义一个适配器

每个适配器都定义两个构造函数：默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器。

所有适配器都要要求容器具有添删能力。

stack只要求push_back、pop_back和back操作，因此可以使用除array和forward_list之外的任何容器类型来构造stack.

queue适配器要求back, push_back, front和push_front，因此可以构造于list或deque之上，但vector不能。

priority_queue除了front, push_back, 和pop_back外还要求随机访问能力，因此构造于vector或deque之上，但不可基于list构造。它允许我们为队列中的元素建立优先级，默认使用<来确定优先级。

我们只可以使用适配器操作，不能使用底层容器类型的操作。例如stack基于deque创造，却不能使用push_back而只能用push.