1、模板类vector

1.1 基本定义及操作

vector是一种动态数组，可在运行阶段设置vector对象的长度，可在末尾附加数据也可在中间插入数据，它使用new和delete来管理内存。

  • 首先，要使用vector对象，必须包含头文件vector。
  • 其次，vector包含在名称空间std中，可使用using编译指令、using声明或std::vector
  • 第三，模板使用不同的语法来指出它存储的数据类型
  • 第四，vector使用不同的语法来指定元素数。
一般而言，声明如下：
vector<typeName> vt(n_elem);   //它可存储n_elem个类型为typeName的元素，其中参数n_elem可以为整形常量，也可以为整形变量。

示例： 
#include<vector>
...
using namespace std;
vector<int>vi;     //初始长度为0的int数组
int n;
cin>>n;
vector<double>vd(n);   //长度为n的double数组

基本操作：
(1)头文件#include<vector>.

(2)创建vector对象，vector<int> vec;

(3)尾部插入数字：vec.push_back(a);

(4)使用下标访问元素，cout<<vec[0]<<endl;记住下标是从0开始的。

(5)使用迭代器访问元素. 

vector<int>::iterator it;
for(it=vec.begin();it!=vec.end();it++)
cout<<*it<<endl;


(6)插入元素： vec.insert(vec.begin()+i,a);在第i+1个元素前面插入a;

(7)删除元素： vec.erase(vec.begin()+2);删除第3个元素

vec.erase(vec.begin()+i,vec.end()+j);删除区间[i,j-1];区间从0开始

(8)向量大小:vec.size();

(9)清空:vec.clear();

vector<Elem> c 创建一个空的vector。
vector <Elem> c1(c2)  复制一个vector。
vector <Elem> c(n) 创建一个vector，含有n个数据，数据均已缺省构造产生。
vector <Elem> c(n, elem) 创建一个含有n个elem拷贝的vector。
vector <Elem> c(beg,end) 创建一个以[beg;end)区间的vector。
c.~ vector <Elem>() 销毁所有数据，释放内存。

注意：vector的元素不仅仅可以使int,double,string,还可以是结构体，但是结构体要定义为全局的，否则会出错。

vector算法，需要头文件#include<algorithm>

(1) 使用reverse将元素翻转：reverse(vec.begin(),vec.end());将元素翻转(在vector中，如果一个函数中需要两个迭代器，一般后一个都不包含.)

(2)使用sort排序：sort(vec.begin(),vec.end());(默认是按升序排列,即从小到大).可以通过重写排序比较函数按照降序比较，如下：

定义排序比较函数：

bool Comp(const int &a,const int &b)
{
return a>b;
}
调用时:sort(vec.begin(),vec.end(),Comp)，这样就降序排序。

1.2 vector的内存管理

1. vector容器的内存自增长 

vector的内存容量只会增加不会减少，先来看看"C++ Primer"中怎么说：为了支持快速的随机访问，vector容器的元素以连续方式存放，每一个元素都紧挨着前一个元素存储。设想一下，当vector添加一个元素时，为了满足连续存放这个特性，都需要重新分配空间、拷贝元素、撤销旧空间，这样性能难以接受。因此STL实现者在对vector进行内存分配时，其实际分配的容量要比当前所需的空间多一些。就是说，vector容器预留了一些额外的存储区，用于存放新添加的元素，这样就不必为每个新元素重新分配整个容器的内存空间。

关于vector的内存空间，有两个函数需要注意：size()成员指当前拥有的元素个数；capacity()成员指当前(容器必须分配新存储空间之前)可以存储的元素个数。reserve()成员可以用来控制容器的预留空间。vector另外一个特性在于它的内存空间会自增长，每当vector容器不得不分配新的存储空间时，会以加倍当前容量的分配策略实现重新分配。例如，当前capacity为50，当添加第51个元素时，预留空间不够用了，vector容器会重新分配大小为100的内存空间，作为新连续存储的位置。

2. vector内存释放

由于vector的内存占用空间只增不减，比如你首先分配了10,000个字节，然后erase掉后面9,999个，留下一个有效元素，但是内存占用仍为10,000个。所有内存空间是在vector析构时候才能被系统回收。empty()用来检测容器是否为空的，clear()可以清空所有元素。但是即使clear()，vector所占用的内存空间依然如故，无法保证内存的回收。

如果需要空间动态缩小，可以考虑使用deque。如果非vector不可，可以用swap()来帮助你释放内存。具体方法如下：

vector<int> nums; 
nums.push_back(1);
nums.push_back(2);
nums.push_back(3);
nums.push_back(4); 
vector<int>().swap(nums); //或者nums.swap(vector<int> ())

或者如下所示，使用一对大括号，意思一样的：

//加一对大括号是可以让tmp退出{}的时候自动析构
{ 
    std::vector<int> tmp =   nums;  
    nums.swap(tmp); 
}

 swap()是交换函数，使vector离开其自身的作用域，从而强制释放vector所占的内存空间，总而言之，释放vector内存最简单的方法是vector<int>.swap(nums)。当时如果nums是一个类的成员，不能把vector<int>.swap(nums)写进类的析构函数中，否则会导致double free or corruption (fasttop)的错误，原因可能是重复释放内存。标准解决方法如下：

template < class T >
void ClearVector( vector< T >& vt ) 
{
    vector< T > vtTemp; 
    veTemp.swap( vt );
}

 其实意思就是把现在用不完的vector内存空间换到一个临时空间中去，这个临时空间是拷贝构造函数创建的只有那么多空间的内存并没有多余的内存，所以交换后不会产生浪费，而这个临时变量则持有了曾经在vt中的没用到的过剩容量。之后，临时vector被销毁，因此释放了以前ivec使用的内存，收缩到合适。

3. 利用vector释放指针

如果vector中存放的是指针，那么当vector销毁时，这些指针指向的对象不会被销毁，那么内存就不会被释放。如下面这种情况，vector中的元素时由new操作动态申请出来的对象指针：

#include <vector> 
using namespace std; 

vector<void *> v;

每次new之后调用v.push_back()该指针，在程序退出或者根据需要，用以下代码进行内存的释放： 

for (vector<void *>::iterator it = v.begin(); it != v.end(); it ++) 
    if (NULL != *it) 
    {
        delete *it; 
        *it = NULL;
    }
v.clear();

2、模板类array（C++11）
vector功能强大但效率较低，如果需要长度固定的数组则array是更好的选择，array使用栈（静态内存分配），而不是自由存储区，因此其更效率安全。
声明： array<typeName,n_elem>arr;   //与vector不同的是，n_elem不能是变量。 
#include<array>
...
using namespace std;
array<int,5>ai;
array<double,4>ad={1.2,2.1,3.43,4.3};

成员类型

 
成员类型 定义
value_type T[编辑]
size_type size_t[编辑]
difference_type ptrdiff_t[编辑]
reference value_type&[编辑]
const_reference const value_type&[编辑]
pointer T*[编辑]
const_pointer const T*[编辑]
iterator 随机访问迭代器（RandomAccessIterator）及字面类型（LiteralType） (C++17 起)[编辑]
const_iterator 随机访问常迭代器[编辑]
reverse_iterator std::reverse_iterator<iterator>[编辑]
const_reverse_iterator std::reverse_iterator<const_iterator>

成员函数

元素访问
at
访问指定的元素，同时进行越界检查 
(公开成员函数)[编辑]
访问指定的元素 
(公开成员函数)[编辑]
访问第一个元素 
(公开成员函数)[编辑]
访问最后一个元素 
(公开成员函数)[编辑]
返回指向内存中数组第一个元素的指针 
(公开成员函数)[编辑]
迭代器

返回指向容器第一个元素的迭代器 
(公开成员函数)[编辑]

返回指向容器尾端的迭代器 
(公开成员函数)[编辑]

返回一个指向容器最后一个元素的反向迭代器 
(公开成员函数)[编辑]

返回一个指向容器前端的反向迭代器 
(公开成员函数)[编辑]
容量控制
检查容器是否为空 
(公开成员函数)[编辑]
返回容纳的元素数 
(公开成员函数)[编辑]
返回可容纳的最大元素数 
(公开成员函数)[编辑]
操作
使用指定的值填充容器 

 
(公开成员函数)[编辑]
交换array的内容 
(公开成员函数)[编辑]

构造函数 说明
arrary<T, N> c 默认构造函数，N个元素全部使用“默认初始化行为”来构造。
arrary<T, N> c(other) 拷贝构造函数，拷贝所有other的元素到c来构造。
arrary<T, N> c = other 拷贝构造函数，拷贝所有other的元素到c来构造。
arrary<T, N> c(rValue) 移动构造，使用右值rValue里的元素来初始化c。
arrary<T, N> c = rValue 移动构造，使用右值rValue里的元素来初始化c。
arrary<T, N> c = initlist 使用初始化列表初始化元素

注意： 由于默认构造函数是对每一个元素使用“默认构造”行为来初始化，这意味着对于基本类型的数据其初始值是未定义的。

array 被要求是一个“aggregate”: 没有用户自定义的构造函数、没有非静态的private和protected类型的成员、没有基类、没有虚函数.

因此不支持这样的构造方法：array<int, 3> a({1, 2, 4});

初始化array最常用的方法是使用赋值运算符和初始化列表：

array<int, 3> a = {1, 2, 3};

array<int, 100> b = {1, 2, 3};  // a[0] ~ a[2] = 1, 2, 3; a[3] ~ a[99] = 0, 0, 0 ... 0;

array<int, 3> c;                // c[0] ~ c[2] 未初始化，是垃圾值.

例子： 
#include <string>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <array>
 
int main()
{
    // 使用聚合初始化来构造
    std::array<int, 3> a1{ {1,2,3} };    // C++11中需要使用双重花括号（而14中不需要）
    std::array<int, 3> a2 = {1, 2, 3}; 
    std::array<std::string, 2> a3 = { {std::string("a"), "b"} };
 
    // 支持基本的容器操作
    std::sort(a1.begin(), a1.end());
    std::reverse_copy(a2.begin(), a2.end(), std::ostream_iterator<int>(std::cout, " "));
 
    // 支持范围for
    for(auto& s: a3)
        std::cout << s << ' ';
}

输出：

3 2 1 
a b
参考资料：http://www.cnblogs.com/summerRQ/articles/2407974.html
http://zh.cppreference.com/w/cpp/container/array