【C++】顺序容器

　　一个容器就是一些特定类型对象的集合。顺序容器为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

顺序容器的概述

下表列出了标准库中的顺序容器，所有顺序容器都提供了快速顺序访问元素的能力。但是不同容器在一下方面都有不同程度的性能折中。

1. 向容器添加或删除元素的代价
2. 非顺序访问容器元素的代价

顺序容器类型
vector　－－－－－－ 可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢
deque　－－－－－－双端队列。支持快速随机访问。在头尾位置插入删除速度很快
list －－－－－－－－双向链表。只支持双向顺序访问。在list中任何位置进行插入删除操作速度都很快
forward_list －－－－单向链表。只支持单向顺序访问。在链表任何位置进行插入删除速度都很快
array－－－－－－－－固定大小数组。支持快速随机访问。不能添加或删除元素
string－－－－－－－－与vector相似的容器，但专门用来保存字符。随机访问速度快。在尾部插入删除速度快

　　　
容器保存元素的策略对容器操作的效率有着固有的，有时是重大的影响。

string和vector将元素保存在连续的内存空间中，由于元素是连续存储的，所以通过下标来计算其地址是很快速的。但是在插入删除某元素时，其之后的元素都需要移动，非常耗时。

list和forward_list两个容器的设计目的是令容器任何位置的添加和删除操作都很快速。作为代价，这两个容器不支持随机访问，如果想访问某个元素只能遍历整个容器。这两个容器的额外内存开销很大。

deque更为复杂。支持快速随机访问，在中间位置插入和删除元素的代价很高，但是在两端添加或删除元素是很快的。

forward_list和array是新C++标准增加的类型。array与内置数组相比，更加安全更易使用，array对象的大小是固定的。forward_list的设计目标是达到与手写单向链表结构相当的性能，所以为了节省开销，无size操作。

确定使用哪种容器

通常，使用vector是最好的选择，除非你有很好的理由选择其他容器。

基本原则：

如果程序有很多小元素，且空间的额外开销很重要，则不要使用list或者forward_list。

如果程序要求在中间位置插入或删除元素，应使用list或forward_list。

如果程序需要在头尾位置插入或删除元素，但不会在中间位置插入或删除操作，则用deque。

如果程序在输入时需要在容器中间位置插入元素，随后需要随机访问元素，则：
－－首先，确定是否　真的需要在中间位置插入元素。当处理输入数据时，很容易地向vector尾部追加元素，然后在调用sort来重排容器中的元素，从而避免在中间位置插入元素。
－－如果必须在中间位置插入元素，考虑在输入阶段用list，一旦输入完成后，将list中的内容拷贝到一个vector中。

例子：判断下列情况应该用哪种容器　
　
a.读取固定数量的单词，按字典序的方式插入容器中。

需要频繁地在容器内部插入数据，vector在尾部之外插入元素很慢，deque在头尾之外很慢，所以最好用list。

b.从文件中读取未知数量的整数，并将这些数排序，然后将它们打印出来。

整数占用空间不大，而且快速的**排序算法需频繁的随机访问元素**，将list排除，无需在头部进行插入删除操作，所以不需用deque，故选择vector。

容器库概览

　　一般来说，每个容器都定义在一个头文件中，文件名与类型名相同。即，deque定义在头文件deque中，以此类推。容器均定义为模板类，当我们定义对象时，必须提供额外的信息来生成特定的容器类型。
比如定义一个list对象，其元素类型是int的deque：list<deque<int>> em;
　　顺序容器几乎可以保存任意类型的元素，但某些容器操作对元素类型有其自己的特殊要求。

迭代器

迭代器介绍

　　迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器不仅仅是指针，因此你不能认为他们一定具有地址值。例如，一个数组索引，也可以认为是一种迭代器。用的最多的还是容器迭代器。

使用迭代器

　　和指针不一样的是，获取迭代器不是使用取地址符，有迭代器的类型同时拥有返回迭代器的成员。比如这些成员都有名为begin()和end()的成员，其中begin成员负责返回第一个元素的迭代器；end成员负责返回最后一个元素的下一个位置的迭代器，通常称为尾后迭代器。
ps：如果容器为空，则begin和end返回的迭代器相同，且都是尾后迭代器。

迭代器运算符

标准容器迭代器的运算符	作用
*iter	返回迭代器iter所指元素的引用
iter->mem	解引用iter并获取该元素的名为mem的成员，等价于(*iter).mem
++iter	令iter指向容器的下一个元素
–iter	令iter指向元素的上一个元素
iter1 == iter2	判断两个迭代器是否相等，如果两个迭代器指的是同一个元素或者他们是同一个容器的尾后迭代器，则相等。
iter1 != iter2	判断两个迭代器是否不想等。判断条件同上

和指针类似，通过解引用来获取迭代器所指的的元素。举个例子

/*将 s 中的字母变成大写的*/
string s = "abcdef";
for(auto it = s.begin(); it != s.end(); ++it)
    *it = toupper(*it);

迭代器类型

　　一般来说我们并不知道迭代器的类型(我们也无需知道)，而实际上，那些拥有迭代器的标准库类型使用iterator和const_iterator来表示迭代器的类型：
vector<int>::iterator it; 　//it 能读写vector<int>的元素
string::iterator it2; 　　 //it2能读写string对象中的字符
vector<int>::const_iterator it3; 　//it3 只能读　不能写vector<int>的元素
string::const_iterator it4; 　　 //it4只能读　不能写　string对象中的字符

　　const_iterator和常量指针差不多，能读取但不能修改它所指向的元素值如果vector或string对象是常量，那么只能使用const_iterator。

迭代器和迭代器类型

　　我们认定某个类型是迭代器当且仅当它支持一套操作，这套操作使得我们能访问容器的元素或者从某个元素移动到另外一个元素。
　　每个容器定义了一个名为iterator的类型，该类型支持迭代器类型所规定的一系列操作。

迭代器范围

　　一个迭代器范围由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者尾元素之后的位置，即begin和end。这种元素范围被称为左闭合区间，其标准数学描述为[begin,end)。
　　
标准库之所以使用左闭合范围，是因为这种范围有三种方便的性质：
1. 如果begin和end相等，则范围为空。
2. 如果begin和end不想等，则范围至少包含一个元素，且begin指向该范围中的第一个元素。
3. 我们可以对begin递增若干次，使begin==end。

　　begin和end有多个版本：带r的版本返回反向迭代器；以c开头的返回const迭代器。不以c开头的函数都是被重载过的，也就是说实际上有两个名为begin的成员，一个是const成员，返回容器的const_iterator类型；一个是非常量成员，返回容器的iterator类型。可以将一个普通的iterator转换为对应的const_iterator，但反之不行。以c开头的是C++新标准引入的，可以只读的访问容器，但不能写。
　　

结合解引用和成员访问操作

　　解引用迭代器可获得迭代器的对象，如果该对象的类型恰好是类，就有可能希望进一步访问它的成员。
　　例如：对于一个由字符串组成的vector对象来说，要想检查其元素是否为空，令it是该vector的迭代器，只需检查it所指的字符串是否为空就可以了。代码如下：

(*it).empty() 　//先解引用it，调用结果对象的empty成员
*it.empty() 　 //error:试图访问it的名为empty成员，但it是迭代器，没有empty成员　　　
为了简化上式，C++语言定义了箭头运算符(->)。箭头运算符把解引用和成员访问两个操作结合在一起。。即it->empty()和(*it).empty()意思相同。

某些对vector对象的操作会使迭代器失效

不能在范围for循环中向vector对象添加元素。
任何一种改变vector对象容量的操作，都会使迭代器失效，比如push_back。原因后面再讲。

谨记：但凡是使用了迭代器的循环体，都不要向迭代器所属的容器添加元素。

例子：编写一个程序创建一个包含10个整数的vector对象，然后使用迭代器将对象元素的值变为原来的两倍，输出vector对象的内容。

  vector<int> arr;
    for(decltype(arr.size()) ix=0; ix!=10; ix++)
        arr.push_back(ix);  //向对象中添加元素

    vector<int>::iterator it;
    for(it = arr.begin();it!=arr.end();++it)
        (*it) *= 2;         //将元素的值变为原来的二倍

    for(it = arr.begin();it!=arr.end();++it)
        cout << *it << " "; //输出
    cout << endl;

容器类型成员

　　每个容器都定义了多个类型，如size_type、iterator和const_iterator等。除了上面用过的迭代器类型，大多数容器还提供反向迭代器。反向迭代器就是一种反向遍历的迭代器，与正向迭代器相比，各种操作都发生了颠覆，比如对反向迭代器执行++操作，会的到上一个元素。

容器定义和初始化

将一个容器初始化为另一个容器的拷贝

两种方式：

1.  直接拷贝整个容器，要求容器类型及其元素类型必须匹配。
2.  拷贝由一个迭代器对指定的元素范围，容器类型及其元素类型都可不同，只要能将要拷贝的元素转换为初始化的容器的元素类型即可。

看下面例子：

list<string> authors = {"Milton","Shakespare","Austen"};
vector<const char*> articles = {"a","an","the"};

list<string> list1(authors);      //正确：类型匹配
deque<string> authlist(authors);  //错误：容器类型不匹配
vector<string> words(articles);   //错误：元素类型不匹配

//正确：可将const char*转换为string
forward_list<string> words(articles.begin(),articles.end());

列表初始化

list<string> authors = {"Milton","Shakespare","Austen"};
这样做时，我们就显式地指定了容器中的每个元素的值，除了array的容器，初始化列表还隐含地指定了容器的大小，即容器将包含和初始值一样多的元素。

与容器大小相关的构造函数

　　顺序容器(array除外)提供了另一个构造函数，它接受一个容器大小和一个(可选的)元素初始值。如果我们不提供初始值，那么标准库会创建一个值初始化器。(顺序容器特有，关联容器并不支持)。
　　如果元素是内置类型或提供了默认构造函数的类类型，那么可以只为构造函数提供一个容器大小参数，如果元素类型没有默认构造函数，则必须指定一个显式的元素初始值。

vector<int> arr(10,-1); //10个int元素，每个都初始化为-1
vector<int> arr1(10);   //10个int元素，每个都初始化为0--int默认

标准库array具有固定大小

　　与内置数组类似，标准库array的大小也是类型的一部分，定义array对象时，除了指定元素类型，还要指定容器大小：

array<int,10>      //类型为：保存10个int的数组
array<string,10>   //类型为：保存10个string的数组

　　与其他容器不同，一个默认的array是非空的：它包含了与其大小一样多的元素。如果我们对array进行列表初始化，那么初始值的数目必须等于或小于array的大小。如果小于，那么它们用来初始化array中靠前的元素，所有剩下的元素进行值初始化。注意的是，如果元素的类型是类类型，那么该类必须有一个默认构造函数。
　　与内置数组一个不同的地方是，内置数组不能进行拷贝或对象赋值操作，但array无此限制。

array<int,10> digits = {0,1,2,3,4,5,6,7,8,9};
array<int,10>  digits1 = digits;  //正确

　　array要求初始值的类型必须和要创建的容器类型一致，同时还要求元素的类型和大小也都一样。

举个例子来复习一下本小节的初始化方法

对6种创建和初始化vector对象的方法，每一种都给出实例。解释每个vector包含什么值。

vector<int> a1;                  //默认初始化，容器为空
vector<int> a2(copy);            //a2初始化为copy的拷贝
vector<int> a3(copy.begin(),copy.end());//a3迭代器参数初始化和a2相同
vector<int> a4 = {1,2,3,4,5,6};  //列表初始化 6个元素，分别为123456
vector<int> a5(a4.begin()+1,a4.end()-1); //两个迭代器指定范围的拷贝 值为2345
vector<int> a6(10,22);           //10个元素，每个值为22

赋值和swap

使用赋值运算符

　　赋值运算符可用于所有容器，要求左边和右边的运算对象具有相同的类型。赋值运算符将其左边容器中的全部元素替换为右边容器中元素的拷贝。如果两个容器原来大小不同，那么赋值后两者的大小都与右边容器的原大小相同。标准库array类型也允许赋值，但是不能将一个花括号列表赋予它。

使用assign

　　此外，顺序容器中除了array以外的其他容器还可以使用assign赋值，允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值。

list<string> names;
vector<const char*> oldstyle;
names = oldstyles;   //error:容器类型不相同
name.assign(oldstyle.cbegin(),oldstyle.cend()); //right

assign第二个版本接受一个整型值和一个元素值。它用指定数目且具有相同给定值的元素替换容器中原有的元素：

list<string> slist(1);     //1个元素，为空string
slist.assign(10,"Hiya!");  //10个元素，每个都是"Hiya!"

使用swap

　　swap操作交换两个相同类型容器的内容。调用swap之后，两个容器的元素将会交换，除array之外，swap不对任何元素进行拷贝、插入删除操作，可以保证在常数时间内完成，交换两个容器内容的操作保证会很快，因为元素本身并未改变，swap只是交换了两个容器的内部数据结构。
　　除string之外，指向容器的指针、引用和迭代器不会在swap操作后不会失效，他们仍指向swap之前所指向的那些元素。

int main()
{
    vector<int> v1 = {1,2,3,4};
    vector<int> v2 = {5,6,7};
    vector<int>::iterator it1 = v1.begin();
    vector<int>::iterator it2 = v2.begin();

    cout << "交换之前 *it1 = " << *it1 << endl;
    cout << "交换之前 *it2 = " << *it2 << endl;
    v1.swap(v2);
    cout << "交换之后 *it1 = " << *it1 << endl;
    cout << "交换之后 *it2 = " << *it2 << endl;

    //注意交换后it1为v2的迭代器
    while(it1 != v2.end())
    {
        cout << *it1++ << " ";
    }

    return 0;
}

　　
　　swap交换之前，两个v1，v2代表的是容器，it1，it2代表的是迭代器；交换后，我们看到it1和it2所指的元素并未改变，it1本来指的是v1[2]中的元素，交换后it1指向v2[2]。
　　对于array容器来说，交换两个容器，会真正交换它们的元素，因此交换两个array所需的时间与array中的数目成正比。

容器大小操作

1. 成员函数 size 返回容器中当前所有元素的数目；
2. 成员函数 empty 当size为0时返回true，否则返回false；
3. 成员函数 max_size 返回一个大于或等于该类型容器所能容纳的最大元素数的值。

ps：forward_list 不支持 size。

关系运算符

　　每个容器都支持相等运算符(== && !=)；除了无序关联容器外的所有容器都支持关系运算符(> < <+ >=)。关系运算符左右两边的运算对象必须是相同类型的容器，且元素类型也要相同。
　　容器的关系运算符使用元素的关系运算符来完成比较。比较两个容器实际上是进行元素的逐对比较。

1.  如果两个容器具有相同大小且所有元素都两两对应相等，则这两个容器相等，否则不等。
2.  如果两个容器大小不同，但较小的容器中每个元素都等于较大容器中的对应元素，则较小容器小于较大容器。
3.  如果两个容器都不是另一个容器的前缀子序列，则它们的比较结果取决于第一个不想等的元素的比较结果。

顺序容器操作

向顺序容器添加元素

　　除array外，所有标准库容器都提供了灵活的内存管理。在运行时可以动态添加或删除元素来改变容器大小。当我们在使用这些操作时，不同的容器采用不同的策略来分配元素空间，而这些策略直接影响性能。向一个vector、string或deque插入元素会使所有指向容器的迭代器、引用和指针失效。

向顺序容器添加元素的操作	array不支持这些操作
forward_list	有自己专门的insert和emplace,不支持push_back 和 emplace_back
vector 和 string	不支持push_front和emplace_front
c.push_back(t)	在c的尾部添加一个值为t的元素
c.push_front(t)	在c的头部添加一个值为t的元素
c.insert(it,t)	在迭代器it指向的元素之前创建一个值为t的元素。返回指向新添加的元素的迭代器
c.insert(it,n,t)	在迭代器it指向的元素之前创建n个值为t的元素。返回指向新添加的第一个元素的迭代器；若n为0，则返回it
c.insert(it,b,e)	将迭代器b和e指定的范围内的元素插入到迭代器it指向的元素之前。b和e不能指向c中的元素。返回指向新添加的第一个元素的迭代器；若范围为空，则返回it
c.insert(it,il)	il是一个花括号包围的元素值列表。将这些给定值插入到迭代器it指向的元素之前。返回指向新添加的第一个元素的迭代器；若列表为空，则返回it

　　　　
　　向一个vector、string或deque插入元素会使所有指向容器的迭代器、指针和引用失效。
　　当我们用一个对象来初始化容器时，或是采用上述方法将一个对象插入到容器中时，实际上放入到容器中的是对象值的一个拷贝，而不是对象本身。就像我们将一个对象传递非非引用参数一样，容器中的元素与提供值的对象之间没有任何关联。随后对容器中元素的任何改变都不会影响到原始对象，反之亦然。

使用emplace操作

　　新标准引进了三个新成员－－emplace_front、emplace、emplace_back，这些操作构造而不是拷贝元素。这些操作分别对应push_front、insert、push_back，允许我们将元素防止在容器头部、一个指定的位置之前或容器尾部。
区别：
　　当我们调用push或insert时，我们将元素类型的对象传递给它们，这些对象被拷贝到容器中。而当我们调用一个emplace成员函数时，则是将参数传递给元素类型的构造函数，emplace成员使用这些参数在容器管理的内存空间中直接构造元素。

/*在c的末尾构造一个Sales_data对象*/
//使用三个参数的Sales_data构造函数
c.emplace_back("97801-2-2-2-",25,19.22);
//error
c.push_back("97801-2-2-2-",25,19.22);
//right创建一个临时对象传递给push_back
c.push_back(Sales_data("97801-2-2-2-",25,19.22));

emplace函数的参数根据元素类型而变化，参数必须与元素类型的构造函数相匹配。

访问元素

在容器中访问元素的操作
c.back()	返回c中尾元素的引用。若c为空，函数行为未定义
c.front()	返回c中首元素的引用。若c为空，函数行为未定义
c[n]	返回c中下标为n的元素的引用，n是一个无符号整数。若n>c.size()，函数行为未定义
c.at(n)	返回下标为n的元素的引用。如果下标越界则抛出一out_of_range异常

　　　
　　访问成员函数返回的是引用，如果我们希望使用此变量来改变元素的值，必须将变量定义为引用类型。

int main()
{
    vector<int> v = {1,2,4,5,6,7};

    //空vector会出现段错误
    vector<int> v1;
    cout << v.front() << " ";
    cout << v.back() << " ";
    cout << v[0] << " ";
    cout << v.at(0) << " ";

    return 0;
}

输出：1 7 1 1

删除元素

顺序容器的删除操作	array不支持这些会改变大小的操作
forward_list	有自己特殊版本的erase,不支持pop_back
vector 和 string	不支持pop_front
c.push_back()	删除c中尾元素。若c为空，则函数行为未定义。函数返回void
c.push_front()	删除c中首元素。若c为空，则函数行为未定义。函数返回void
c.erase(p)	删除迭代器p所指定的元素，返回一个指向被删元素之后元素的迭代器，若p指向尾元素，则返回尾后迭代器。若p是尾后迭代器，则函数行为未定义
c.erase(b,e)	删除迭代器b和e之间的元素，e指向我们要删除的最后一个元素之后的元素。返回一个指向最后一个被删元素之后元素的迭代器，若e本身就是尾后迭代器，则函数也返回尾后迭代器
c.clear()	删除c中所有元素。返回void

改变容器大小

我们可以使用resize来增大或缩小容器。

c.resize(n,t);  //调整c的大小为n个元素。任何新添加的元素都初始化为值t
c.resize(n);  //调整c的大小为n个元素。若当前大小大于所要求的大小，则多出的后部元素被删除；若必须添加元素，则对新元素进行值初始化。

ps：resize操作接受一个可选的元素值参数，用来初始化添加到容器中的元素。如果调用者未提供此参数，新元素进行值初始化。如果是类类型，则我们必须提供初始值，或者元素类型必须提供一个默认构造函数。

容器操作可能使迭代器失效

　　向容器中添加或删除元素的操作可能会使指向容器元素的指针、引用或迭代器失效，使用失效后的指针、引用或迭代器是一种严重的程序设计错误，很可能会引起与为初始化指针一样的错误。
　　

1. 在向容器添加元素后：

    vector和string：
    存储空间被重新分配，则指向容器元素的指针、引用或迭代器都会失效。
    存储空间未被重新分配，则指向容器插入元素之前的指针、引用或迭代器扔有效，但指向容器插入位置之后的指针、引用或迭代器将会失效。
    deque：
    插入到除首尾位置之外的任何位置，都会使指向容器元素的指针、引用或迭代器失效。如果在首尾位置添加元素，迭代器会失效，但指向存在元素的指针或引用不会失效。
    list和forward_list：
    指向容器元素的指针、引用或迭代器(包括尾后迭代器和首前迭代器)仍有效。

2. 从容器删除元素后

vector和string：
指向被删元素之前的指针、引用或迭代器仍有效。
deque：
如果在首尾位置之外的任何位置删除元素，那么指向被删除元素之外的任何元素的指针、引用或迭代器也会失效。如果是删除deque的尾元素，则尾后迭代器也会失效，但其他迭代器、引用或指针不受影响；如果是删除首元素，其他元素都不受影响。
list和forward_list：
指向容器其他位置的迭代器(包括尾后迭代器和首前迭代器)、引用或指针都不会失效。

ps：
　　添加/删除vector、string或deque元素的循环程序必须考虑迭代器、引用和指针可能失效的问题。程序必须保证每个循环步中都更新迭代器、引用或指针。
　　当我们添加/删除vector或string的元素后，或在deque中首元素之外的任何位置添加/删除元素之后，原来end返回的迭代器总是失效。因此，添加删除元素的循环程序必须反复调用end，而不能在循环之前保存end返回的迭代器。。。通常C++标准库的实现中end()操作都很快，部分就是因为这个原因。

额外的string操作

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

string s("hello world");
string s2 = s.substr(0,5);  //s2 = hello
string s3 = s.substr(6);    //s3 = world
string s4 = s.substr(6,11); //s4 = world
string s5 = s.substr(12);   //抛出一个out_of_range异常

s.append(args) 将args追加到s.返回一个指向s的引用
s.replace(range,args) 删除s中范围range内的字符，替换为args指定的字符。range或者是一个下标和一个长度，或者是一对指向s德尔迭代器。返回一个指向s的引用
string s = "C++ primer";
string s2 = s.append(" 5th Ed."); //s2 = "C++ Primer 5th Ed."
s2.replace(11,3,"Fifth"); //s2 = "C++ Primer Fifth Ed."

string搜索操作
s.find(args) 查找s中args第一次出现的位置，若找到返回第一个匹配位置的下标，否则返回npos
s.rfind(args) 查找s中args最后一次出现的位置(逆向搜索　从右向左)
s.find_first_of(args) 在s中查找args中任何一个字符　第一次　出现的位置
s.find_last_of(args) 在s中查找args中任何一个字符　最后一次　出现的位置
s.find_first_not_of(args) 在s中查找第一个不在args中的字符
s.find_last_not_of(args) 在s中查找最后一个不在args中的字符
每个操作都接受一个可选的第二参数，可用来指定从什么位置开始搜索
s.find(args,pos)  //pos为 s 的下标

vector对象是如何增长的？

策略：

　　为了支持快速随机访问，vector将元素连续存储－－每个元素紧挨着前一个元素存储。假定容器是连续存储的，且容器的大小是可变的，考虑向vector或string中添加元素会发生什么：如果没有空间容纳元素，容器不可能简单地将它添加到内存中其他位置－－因为元素必须连续存储。*容器必须分配新的内存空间来保存已有元素和新元素，将已有元素从旧位置移动到新空间中，然后添加新元素，释放旧存储空间。*如果没添加一个元素，vector就执行这样一次内存分配，性能会慢到无法接受。
　　标准库实现者采用了可以减少容器空间重新分配次数的策略。当不得不获取新的内存空间时，vector和string的实现通常会分配比新空间需求更大的内存空间。容器预留这些空间作为备用，可用来保存更多的新元素。
　　这种分配策略性能上要高效的多。

管理容量的成员函数

vector和string类型提供了一些成员函数，允许我们与它的实现的内存分配部分互动。

容器大小管理操作
:shrink_to_fit()适用于vector string deque	capacity() reserve(n) 适用于vector和string
c.shrink_to_fit()	请将capacity()减少为与size()相同大小
c.capacity()	不重新分配内存空间的话，c可以保存多少元素
c.reserve(n)	分配至少能容纳n个元素的内存空间(尽影响预先分配多大的内存空间)

具体分配时的相互调用规律

　　只有当需要的内存孔家超过当前容量时，reserve调用才会改变vector的容量。如果需求大小大于当前容量，reserve至少分配与需求一样大小的内存空间(可能更大)。
　　如果需求大小小于或等于当前容量，reserve什么都不做。特别是，当需求大小小于当前容量时，容器不会退回内存空间。因此，在调用reserve后，capacity将会大于或等于传递给reserve的参数。
　　这样，调用reserve永远也不会减少容器占用的内存空间。类似的，resize成员只改变容器中元素的数目，而不是容器的容量。

capacity和size的区别

容器的size是指它已经保存的元素的数目；

capacity是在不分配新的内存空间的前提下它最多可以保存多少个元素。

/*************************************************************************
    > File Name: 9.4.cpp
    > Author: Tanswer
    > Mail: 98duxm@gmail.com
    > Created Time: 2016年11月08日 星期二 22时53分14秒
 ************************************************************************/

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> ivec;
    //size应为0;capacity的值依赖于具体实现
    cout << "ivec:size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;

    //向ivec添加24个元素
    for(int i=0; i!=24; i++)
        ivec.push_back(i);

    //size应为24;capacity的值依赖于具体实现
    cout << "ivec:size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;

    //现在预分配一些空间
    ivec.reserve(50);  //将capacity至少设定为50,可能会更大
    //size应为24;capacity的值依赖于具体实现,应该大于等于50
    cout << "ivec:size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;

    //添加元素用光这些空间
    while(ivec.size() != ivec.capacity())
        ivec.push_back(0);

    //capacity应该未改变，size和capacity不相等
    cout << "ivec:size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;

    //由于我们只使用了预留空间，所以内存空间不会重新分配
    ivec.push_back(42);
    cout << "ivec:size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;


    return 0;
}

输出结果：