C++ 顺序容器

容器：一些特定类型对象的集合。
通俗来讲，容器就类似于数组的升级版，长度可变，以函数的形式对容器内的数据进行操作。
每个容器都有自己的头文件，使用的时候，必须引用相应的头文件！
比如 使用vector容器时，#include < vector >。

一、顺序容器的选择

顺序容器有：

• vector，可变数组，支持随机访问，尾部插入/删除速度快
• deque，双端队列，支持随机访问，头尾插入/删除速度快
• list，双向链表，只支持双向顺序访问，任何位置插入/删除速度都快
• forward_list，单向链表，只支持单向顺序访问，任何位置插入/删除速度都快
• array，固定大小数组，支持随机访问，不能插入/删除元素
• string，与vector类似，用于保存字符，支持随机访问，尾部插入/删除速度快

对于顺序容器的说明都列出来了，根据程序需要进行的操作选择即可。
C++ Primer书中特别强调：
“通常，使用vector是最好的选择，除非你有很好的理由选择其他容器。”

二、迭代器

迭代器是容器中很重要的概念，可以和指针类比，指针指着数组里面元素，迭代器指着容器里面的元素。
容器类型不同，迭代器的数据类型也不同：
vector< int >::iterator iter;
（vector< int >在下面例子中会看到，是容器定义的类型）
迭代器iter的类型就是前面的“vector::iterator”。
其中最重要的迭代器就是begin和end两个。
begin迭代器指着容器中第一个元素，而end指着容器中最后一个元素之后的位置，这么做是为了更方便地使用begin和end两个迭代器遍历访问容器。

//定义了一个int型的vector容器
vector<int> v;
//v1是v的begin迭代器，v2是end迭代器
vector<int>::iterator v1 = v.begin(), v2 = v.end();
while(v1 != v2){
	*v1 = val;
	++v1;
}

这里通过不断递增begin迭代器，顺序访问容器中的内容，end迭代器指着容器中最后一个元素之后的位置，当begin = end -1 的时候，说明begin此时已经指向容器中最后一个元素了，当begin和end相等的时候，说明容器中所有内容都已经访问完了，循环结束。
一般使用上面的方法访问容器，而不要使用下面这样的：

while( v1 < v2){}

因为有些容器不支持"<"、">“等这样的运算符，但全部都支持”==“和”!=“运算符，vector是支持”<"的，但list不支持，保险起见，统一用等号和不等号。
在C++11中提供auto类型说明符，简化操作。
上文代码中第4行可以简化如下：

auto v1 = v.begin(), v2 = v.end();

关于begin和end的类型，还需要再介绍一下：

auto v1 = v.begin();//auto为vector<int>::iterator
auto v2 = v.rbegin();//auto为vector<int>::reverse_iterator
auto v3 = v.cbegin();//auto为vector<int>::const_iterator
auto v4 = v.crbegin();//auto为vector<int>::const_reverse_iterator

不同的版本，迭代器的类型也不同。
如果不进行写的操作，选择c开头的版本，保护容器中的数据。（ cbegin(); ，cend(); ）

三、顺序容器的定义和初始化

容器的定义和初始化有如下几种：

1. 默认
2. 拷贝初始化
3. 含大小参数初始化（只有顺序容器才可以，不包括array）
   以vector为例，示例如下：

	//默认 
	vector<int> v1;
	
	//拷贝其他容器
	vector<int> v2(v1);//将v1拷给v2
	vector<int> v3 = v1;//将v1拷给v3
	vector<int> v4(b,e);
	//拷贝初始化列表 
	vector<int> v5{0, 1, 2};//初始v5包含元素012
	vector<int> v6 = {0, 1, 2};//同上
	
	//含大小参数
	vector<int> v7(3);//初始v7大小为3 
	vector<int> v8(3,0);//初始v8为3个0 

其中定义初始化v4的时候，b、e是两个迭代器，将二者之间范围（从b开始到e前一个）的元素拷贝给v4。
需要注意的是，在vector< int > v2(v1);中，v1和v2容器类型必须相同，必须都是vector< int >，而在vector< int > v4(b,e);中则不作要求，只要元素类型能进行转化即可，比如b,e可以是list< double >中的迭代器，double可以转化为int。
以上方法是除array外通用的，list等都适用。
下面说一下array：
array<类型，数量>
比如：

//初始化int型的array容器
array<int,10> a1;
array<int,3> a2 = {0, 1, 2};
a1 = {0,1,2,3,4,5,6,7,8,9};//错误，同内置数组一样，只能在定义的时候使用列表初始化。

你可能会想，这和内置数组 int a1[10]有什么区别呢？
区别就是，array可以进行拷贝或赋值，而内置数组不可以：

	array<int,3> a3 = {0, 1, 2};
	array<int,3> a4 = a3;//正确
	
	int a5[3] =  {0, 1, 2};
	int a6[3] = a5;//错误 

四、顺序容器的操作

顺序容器的操作分为三种：添加、访问和删除。

1. 添加元素。

添加元素分为：

• 尾部添加，除array和forward_list外，每个顺序容器都支持
• 头部添加，list、forward_list和deque支持
• 指定位置添加， 除array外，均支持

尾部添加：

 c.push_back(t); 

头部添加：

c.push_front(t); 

指定位置添加：

//在迭代器p指的位置前添加元素t，返回新添加元素的迭代器
c.insert(p,t);

//在p前添加n个元素t，返回新添加的第一个元素的迭代器
c.insert(p,n,t);

//在p前添加迭代器b和e之间的元素，返回新添加的第一个元素的迭代器
c.insert(p,b,e);

//在p前添加花括号包围的元素值列表，返回新添加的第一个元素的迭代器
c.insert(p, {元素值列表});

2. 访问元素
对于string, vector, deque和array这些支持随机访问的容器来说，可以用at和下标操作（c.at(0)或是c[0]）访问。
更通用的，是下面两个函数：

• c.back(); //容器的首个元素
• c.front();//容器的最后一个元素

back()和begin()是一样的，而front()和end()不一样，front()指向的是最后一个元素，end()指的是最后一个元素之后的位置。

3. 删除元素
删除元素也有三种：

• 尾部删除
• 头部删除
• 指定删除

尾部删除：

c.pop_back();

头部删除：

c.pop_front();

指定删除：

//删除迭代器p指向的元素，返回被删元素之后的元素的迭代器
c.erase(p);
//删除迭代器b和e范围的元素，返回最后一个被删元素之后的元素的迭代器
c.erase(b,e);
//全删，返回void
c.clear();

4. 注意事项
往容器里添加或者删除元素之后，迭代器可能会失效，所以在写程序时，每次对容器操作之后，都要考虑迭代器是否已经失效。
可以利用添加或者删除元素返回的迭代器，避免迭代器失效。
无须保存end()的内容，每次操作后end()可能会改变，需要用时直接调用end()即可，通常c++标准库中实现end()的操作都很快。

五、vector容器的内存

size和capacity是两个关键的概念。
size是容器的大小(元素总个数)，可以用函数c.size()获得。
capacity是容器所占空间的大小，可以用函数c.capacity()获得。
vector支持随机访问，所以它将元素连续存储，一般分给它的内存(capacity)都会大于它的当前的容量(size)，不断往里添加元素，一旦size大于capacity，就要把vector所有的元素换一个更大的空间存储。
对容器大小进行操作的函数：

//获取容器的大小
c.size();

//调整容器的大小为n个元素
c.resize(n);

//调整容器的大小为n个元素，新添加的元素都初始化为t
c.resize(n,t);

对内存进行操作的函数：
其中，shrink_to_fit 只适用于vector, string 和 deque
capacity和reserve只适用于vector 和string

//获取容器的capacity
c.capacity();

//分配至少为n个元素的内存空间
c.reserve(n);

//将内存空间（capacity）缩小至容器大小（size），不过不一定成功
c.shrink_to_fit();