关键字： vector容器 deque容器
3.2 vector容器
3.2.1基本概念
功能：vector数据结构和数组非常相似，也称为单端数组，在尾端可以进行插入删除操作；
vector与普通数组区别：数组为静态空间，vector可以动态扩展
注：vector容器的迭代器是支持随机访问的迭代器
动态扩展
并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间；
vector容器的迭代器是支持随机访问的迭代器
3.2.2 vector构造函数
函数原型：
1 vector<T> v;//采用模板实现类实现，默认构造函数
2 vector(v.begin(),v.end());//将v[begin(),end()）区间中的元素拷贝给本身
3 vector(n,elem);//构造函数将n个elem拷贝给本身
4 vector(const vector &vec);//拷贝构造函数
示例：
void test01()
{
vector<int> v1;
vector<int> v2(v1.begin(), v1.end());
vector<int> v3(10, 100);
vector<int> v4(v3);
}
3.2.3 vector赋值操作
函数原型：
1 vector &operator=(const vector &vec);
2 assign(beg,end);//左开右闭
3 assign(n,elem);
示例：
void test01()
{
vector<int> v1;
for (int i = 0; i < 10; ++i)
{
v1.push_back(i);
}
vector<int> v2 = v1;
vector<int> v3;
v3.assign(v1.begin(), v1.end());
vector<int> v4;
v4.assign(10, 100);
}
3.2.4 vector容量和大小
函数原型：
1 empty();//判空
2 capacity();//容量
3 size();//返回容器中元素个数
4 resize(int num);//重新指定容器长度，若容器变长，以默认值填充；若变短，则末尾元素被删除；
5 resize(int num, elem);//重新指定容器长度，若容器变长，以elem值填充；
3.2.5 vector插入和删除
函数原型：
1 push_back(ele);//尾插
2 pop_back()；//删除最后一个元素
3 insert(const_iterator pos, ele);//迭代器指向位置pos插入元素ele)
4 insert(const_iterator pos, int count, ele);//迭代器指向位置pos插入count个元素ele)
5 erase(const_iterator pos);//删除迭代器指向元素
6 erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
7 clear();//删除容器中所有元素
3.2.6 vector数据存取
函数原型：
1 at(int idx);//返回索引idx所指的数据
2 operator[];//返回索引idx所指的数据
3 front();//返回容器中第一个数据元素
4 back();//返回容器中最后一个数据元素
3.2.7 vector互换容器
功能：实现两个容器内元素进行互换
函数原型：swap(vec);
用途：收缩内存
示例：
void test02()
{
vector<int> v;
for (int i = 0; i < 1000; ++i)
{
v.push_back(i);
}
cout << "capacity: " << v.capacity()<< endl;
cout << "size: " << v.size() << endl;
v.resize(3);//重新指定大小 容量不变
cout << "capacity: " << v.capacity() << endl;
cout << "size: " << v.size() << endl;
//巧用swap收缩内存
vector<int>(v).swap(v);
//vector<int>(v)//匿名对象 调用拷贝构造函数
//按照v目前所用元素个数初始化该匿名对象
//匿名对象当前行结束系统自动回收
cout << "capacity: " << v.capacity() << endl;
cout << "size: " << v.size() << endl;
}
3.2.8 vector预留空间
功能：减少vector动态扩展容量时的扩展次数
函数原型：reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问
示例：
void test01()
{
//统计扩展（开辟空间）次数
int num = 0;
int *p = NULL;
vector<int> v1;
//利用reserve预留空间
v1.reserve(100000);
for (int i = 0; i < 100000; ++i)
{
v1.push_back(i);
if (p != &v1[0])
{
p = &v1[0];
++num;
}
}
cout << "num = " << num << endl;
}
3.3 deque容器
3.3.1 deque容器基本概念
功能：双端数组，可以对头端进行插入删除操作
deque和vector区别：
1 vector对于头部的插入删除效率低，数据量越大，效率越低
2 deque相对而言，对头部的插入删除速度比vector快
3 vector访问元素的速度会比deque快，这和两者内部实现有关
deque内部工作原理：
deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据
中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间
注：deque容器迭代器也是支持随机访问的
3.3.2 deque构造函数
函数原型：
1 deque<T> deqT;//默认构造
2 deque(beg,end);//构造函数将[begin,end)区间中的元素拷贝给本身
3 deque(n,elem);//构造函数将n个elem拷贝给本身
4 deque(const deque &deq);//拷贝构造函数
3.3.3 deque赋值操作
函数原型
1 deque &operator=(const deque &deq);
2 assign(beg,end);
3 assign(n,ele);
3.3.4 deque大小操作
函数原型
1 deque.empty();
2 deque.size();
3 deque.resize(num);//以默认值0填充
4 deque.resize(num,elem);//以elem填充
注：deque容器不存在容量的概念，因为容量不受限制，
可以无限开辟新空间，中控器只需增加地址；
3.3.5 deque插入和删除
函数原型：
两端操作：
1 push_back(elem);
2 push_front(elem);
3 pop_back();
4 pop_front();
指定位置操作：
1 insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据位置
2 insert(pos,n,elem);//在pos位置插入n个elem，无返回值
3 insert(pos,beg,end);//插入一个区间数据。无返回值
4 clear();
5 erase(beg,end);//删除区间数据，返回下一个数据位置
6 erase(pos);//删除pos位置数据，返回下一数据的位置
3.3.6 deque数据存取
函数原型
1 at(int idx);
2 operator[];
3 front();
4 back();
3.3.7 deque排序
函数原型
sort(iterator beg,iterator end);//对区间内的元素进行排序
注：头文件 <algorithm>
