c++顺序容器

定义和初始化
#include<vector>
#include<list>
#inlcude<deque>
初始化：

C<T> c;	空容器，如vector<int> ivec;
C c(c2);	创建容器c2的副本c
C c(b,e);	由迭代器b,e标识的范围内的元素的副本，如list<int> ilist(ivec.begin(),ivec.end());
C c(n,t);	用n个值为t 的元素创建容器c
C c(n);	创建有n个值初始化元元素的容器

string strings[]={"abc","def",ghi"};
deque<string> sdeq(strings,strings+sizeof(strings)/sizeof(string));

容器元素类型必须满足以下两个条件：
元素类型必须支持赋值运算；
元素类型的对象必须可以复制；

除了引用类型外，所有的内置类型或复合类型都可以用做元素类型。（引用不支持一般意义上的赋值运算），另外，IO类型不支持复制或赋值，故不能创建存放IO类型对象的容器。

容器存放的是复本，对于由其它容器或对象初始化的容器来说，更改其值不会影响被复制的原值。
容器的容器：
vector<vector<string> > lines;
>>中间要使用空格：
vector<vector<string>> lines;//error

迭代器
迭代器为所有标准库容器类型所提供的运算：
*iter iter->item ++iter iter1==iter2 iter1!=iter2
vector和deque容器的迭代器提供的额外运算：(迭代器算术运算)
iter + n
iter - n
iter1+=iter2
>,>=,<,<=
上述只用于vector和deque容器，因为只有这两种容器为其元素提供快速，随机的访问。

容器操作
容器定义的类型别名：

size_type	UL，最大可能长度,作为索引的类型
iterator	此容器类型的迭代器类型
const_iterator	只读迭代器
reverse_iterator	按逆序寻址元素的迭代器
const_reverse_iterator	只读逆序迭代器
difference_type	足够存储两个迭代器差值的有符号整型，可负
value_type	元素类型
reference	元素左值类型，是value_type&的同义词
const_reference	元素常量左值类型，等效于const value_type&

关系操作符：
所有容器都支持关系操作符来实现来个容器的比较。比较的容器必须要有相同的容器类型，且元素类型也要相同。容器的比较是基于容器内元素的比较，故元素应要支持关系操作。

容器大小操作：
c.size()//当前大小
c.max_size()//可容纳最大数
c.empty()
c.resize(n)//调整大小为n，若n>c.size(),添加值采用初始化方法，否则删除多余值
c.resize(n,t)//调整大小为n，若n>c.size(),添加值为t，否则删除多余值

元素访问：
如果容器非空，则front和back成员将返回容器内第一个或最后一个元素引用：
if(!ilist.empty())
{
  list<int>::reference val=*ilist.begin();//引用
  list<int>::reference val2=ilist.front();//和val相同
  list<int>::reference last=*--ilist.end();
  list<int>::reference last2=ilist.back();
}
汇总：
c.back()
c.front()
c[n]      //only vector and deque suported ,no list
c.at(n)   //only vector and deque suported ,no list

删除元素：

c.erase(p)	删除迭代器指向的元素，返回指向删除元素的下个元素的迭代器，若p为c.end()则函数未定义
c.erase(b,e)	删除迭代器b和e范围内的元素，返回指向删除元素段的下个元素的迭代器，若e为c.end()，则返回c.end()
c.clear()	删除c中所有元素，返回void
c.pop_back()	删除最后一个元素，返回void,若c为空，则函数未定义
c.pop_front()	删除第一个元素，返回void,若c为空，则函数未定义，只适用于list或deque

一般来说，需要先找到要删除的元素后才能使用erase方法，寻找一个指定元素最简单的方法是使用标准库里的find方法。<algorithm>
string searchValue("Quasimodo");
list<string>::iterator iter=find(slist.begin(),slist.end(),searchValue);
if(iter!=slist.end())
slist.erase(iter);

赋值与swap

c1=c2	删除c1中所有内容，将c2的元素复制给c1。c1和c2的类型必须相同
c1.swap(c2)	交换内容：类型要相同。执行速度通常比将c2的元素复制到c1的操作快
c.assign(b,e)	重设c的元素：将迭代器b和e标记的范围内的元素复制到c中。b和e不能指向c中的元素
c.assign(n,t)	将c重设为存储n个值为t 的元素

    当在不同或相同的容器中，元素类型不相同但是相互兼容，则其不能用=进行赋值，要用assign赋值。
swap:容器类型相同，元素类型相同。
   c1.swap(c2);
swap操作没有移动元素，因此迭代器没有失效。比如在交换前，一个迭代器指向c1[2],实现交换后，该迭代器指向c2[2],指向的仍是同一个对象。

容器自增长
为了使vector容器实现快速的内存分配，vector容器预留了额外的存储区用于存放新加的元素。
由于vector是在内存中连续存放的，vector容器处理内存分配的细节是其实现的一部分，该部分是由vector的接口去持的。vector类提供了两个成员函数：capacity和reserve,使程序员可与vector容内存分配的实现部分的交互工作。capacity操作获取在容器需要分配更多的存储空间之前能够存储的元素总数，而reserve操作告诉vector容器应该预留多少个元素的存储空间。
size是指容器当前拥有的元数总数，而capacity是指容器在必须分配新的存储空间之前可以存储的元素总数。
vector<int> ivec;
cout<<"ivec:size: "<<ivec.size()<<endl; //0
cout<<"ivec:capacity:"<<ivec.capacity()<<endl; //0
//加入24个元素后
size:24
capacity:32

ivec.reserve(64);
size:24
capacity:64
//再加入24个元素后
size:48
capacity:64 //使用了预留的容量，不分配空间
//再加入24个元素
size:7
capacity:128//重新分配存储空间，以加倍当前容量的分配策略分配（依编译器变化）

容器选择

	Vector	Deque	List
随机访问	快速	快速	不支持
insert/erase	效率低	效率最低	快速
push_front()	不支持	快速	快速
push_back()	快速	快速	快速
pop_front()	不支持	快速	快速
pop_back()	快速	快速	快速

list不支持随机元素访问：
ilist.at(0);//error
ilist[0];//error
vector不支持push_front(val)和pop_front()操作。
选择容器的提示：
A.如果程序要求随机访问元素，则应使用vector或deque容器。
B.如果程序必须要在中间位置插入或删除元素则应采用list容器。
C.如果不需要在中间插入或删除元素，而是在首或尾部插入或删除元素，则应采用deque容器。
D.如果只需在读取输入时在容器的中间位置插入元素，然后需要随机访问元素，则可考虑在输入时将元素读入到一个list容器中，接着对此容器重新排序，使其适合顺序访问，然后将排序后的list容器复制到vector中。
E.如果程序既需要随机访问又必须在容器的中间位置插入或删除元素，此时选择何种容器取决于下面两种操作的代价：随机访问list的代价，在vector或deque容器中插入/删除元素时复制元素的代价。

string和容器
string类型支持大多数顺序操作，在某些方面可将string类型视为字符容器。与vector容器不同的是，它不支持以栈方式操纵容器：在string类型中不能使用front,back和pop_back操作。

string 不支持的容器操作：
C<T> c(n) 初始化
push_front(e)
back,front
pop_back() pop_front()
关于string的具体介绍请参阅：《关于C++标准库中的 string》一文
容器适配器
除了顺序容器，标准库还提供了三种顺序容器适配器：queue,priority_queue和stack。
适配器支持的通用操作有：
size_type,value_type, container_type, A a; A a(c); 关系运算符
#include<stack>
#include<queue>
初始化：
两种方式：默认构造函数，空对象；带一个容器参数的构造函数将参数容器的副本作为其基础值。
例：假如deq是deque<int>类型的容器，则可用deq初始化一个新stack: stack<int> stk(deq);
覆盖基础容器类型：
默认的stack和queue都基于deque容器上实现，而priority_queue则在vector容器上实现。在创建适配器时，通过将一个顺序容器指定为适配器的第二个类型参数，可覆盖其关联的基础容器类型：
stack< string, vector<string> > str_stk; //implemented on top of vector
stack<string, vector<string> > str_stk(svec);//holds a copy of svec
stack 适配器要要所关联的容器可以是任意一种顺序容器，故可建立在vector,list或deuqe上。
queue适配器要求其关联的基础容器必须提供push_front运算，故只能建立在list容器上，不能建立在vector上。
priority_queue适配器要求提供随机访问的功能，故可建立在vector或deque容器上，不能建立在list容器上。

栈适配器：
s.empty(),s.size(),s.pop(),s.top() ,s.push(item)
队列：FIFO queue
q.empty(),q.size(),q.pop(),q.front(),q.back(),q.push(item)