今天学习目标是STL的deque和vector，这两者是各有好处，vector内存小，deque则是结构优雅，能处理更复杂的数据。
STL中有两种数据类型，一种是vector，一种是deque，在使用方法上，两者类似，都是重载赋值，头插法，尾插法的写法都是一致的，非常标准。
但是两种的根本区别在两者的数据结构。
vector是一种单序列的数组，每一个数据紧紧的连着上一个数据，就像是锁链一样。
但是deque就不一样，尽管从内存地址上来看，deque数据容器也是在一片连续的地址上开辟的，但是事实上，deque会创建一片缓冲区，在缓冲区的中间创建数据，并且使用中继器来记录地址并管理，因此他在处理大量数据的时候，不需要那么麻烦，仅需要在缓冲区创建地址即可，但是vecto人在处理大量数据的插入时，就需要把所有数据地址进行更改。
下面请见详解。
目录
vector容器
vector基本概念
vector构造函数
vector赋值操作
vector容量和大小
vector插入和删除
vector数据存取
vector互换容器
vector预留空间
deque容器
deque容器基本概念
deque构造函数
deque赋值操作
deque大小操作
deque大小操作
deque 插入和删除
deque 数据存取
deque 排序
vector容器
vector基本概念
功能：
-
vector数据结构和数组非常相似，也称为单端数组
vector与普通数组区别：
-
不同之处在于数组是静态空间，而vector可以动态扩展
动态扩展：
-
并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间
-
静态空间是固定内存空间存储，不可更改的，就是创建五个数据存储后，就放在这里，不能扩展也不能缩小
-
但动态就可以随时调整，实现原理就是一个封装好的 “拷贝加拼接” 代码，为什么拷贝的新空间，不是在原地址扩展，因为他不知道要拼接的地方后边有没有数据，造成覆盖和溢出
vector容器的迭代器是支持随机访问的迭代器
因此在迭代器的帮助下，可以进行更多功能的操作
vector构造函数
函数原型：
-
vector
v; //采用模板实现类实现，默认构造函数（无参构造）
-
vector(v.begin(), v.end()); //将v[begin(), end())区间中的元素拷贝给本身。（将一段区间的元素拷贝进来，前闭后开）
vector(n, elem); //构造函数将n个elem拷贝给本身。（n个elem数据拷贝）
vector(const vector &vec); //拷贝构造函数。（就是拷贝）
代码
#include#include #include using namespace std; void print_vector(vector &v) { for(vector ::iterator it=v.begin();it!=v.end();it++) { cout << *it << " "; } cout << endl; } //无参构造 void test01() { vector v1;//默认构造 无参构造 for (int i = 0; i < 10; i++) { v1.push_back(i); } print_vector(v1); //通过区间方式进行构造 vector v2(v1.begin(), v1.end());// v1.begin就是头开始，到尾部结束 print_vector(v2); //n个elem方式构造 vector v3(10, 100); print_vector(v3); //拷贝构造函数 vector v4(v3); print_vector(v4); } int main() { test01(); system("pause"); return 0; }
vector的多种构造方式没有可比性，根据需求操作
vector赋值操作
功能描述：
-
给vector容器进行赋值
函数原型：
-
vector& operator=(const vector &vec);//重载等号操作符
-
assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
-
assign(n, elem); //将n个elem拷贝赋值给本身。
这一节学习要注意两点
一是打印函数的书写
void print_vector(vector&v) { for (vector ::iterator it =v.begin();it!=v.end();it++) { cout << *it << " "; } cout << endl; }
二是各种赋值操作，简单粗暴
void test01() //赋值操作
{
vectorv1;
for(int i = 0; i < 10; i++)
{
v1.push_back(i);
}
print_vector(v1);
//赋值 使用operator=的方式赋值
vectorv2;
v2 = v1; //直接将v1的值给v2
print_vector(v2);
//assign
vectorv3;
v3.assign(v1.begin(), v1.end());//采用的区间取值的方法诶，，，v1的开始处，到v2的关闭处
print_vector(v3);
//n个elem方式赋值
vectorv4;
v4.assign(10, 100);
print_vector(v4);
}
其中第二种我比较在意，老师说用operator的方式，但是我并没有书写operator的代码。这是自动完成的？
vector容量和大小
功能描述：
-
对vector容器的容量和大小操作
函数原型：
-
empty(); //判断容器是否为空
-
capacity(); //容器的容量
-
size(); //返回容器中元素的个数
-
resize(int num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除。
-
resize(int num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。//如果容器变短，则末尾超出容器长度的元素被删除
#include#include #include using namespace std; void print_vector(vector & v) { for (vector ::iterator it = v.begin(); it != v.end(); it++) { cout << *it << " "; } cout << endl; } void test01() //赋值操作 { vector v1; for (int i = 0; i < 10; i++) { v1.push_back(i); } if (v1.empty()) { cout << "v1为空" << endl; } else { cout << "v1不为空，其数据为： " << endl; print_vector(v1); cout << "v1的容量 = " << v1.capacity() << endl; cout << "v1的大小 = " << v1.size() << endl; } //resize 重新指定大小 ，若指定的更大，默认用0填充新位置，可以利用重载版本替换默认填充 v1.resize(15, 10); print_vector(v1); //resize 重新指定大小 ，若指定的更小，超出部分元素被删除 v1.resize(5); print_vector(v1); } int main() { test01(); system("pause"); return 0; }
总结：
-
判断是否为空 --- empty
-
返回元素个数 --- size
-
返回容器容量 --- capacity
-
重新指定大小 --- resize
vector插入和删除
判断是否为空 --- empty
返回元素个数 --- size
返回容器容量 --- capacity
重新指定大小 --- resize
功能描述：
-
对vector容器进行插入、删除操作
函数原型：
-
push_back(ele); //尾部插入元素ele
-
pop_back(); //删除最后一个元素
-
insert(const_iterator pos, ele); //迭代器指向位置pos插入元素ele
-
insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele
-
erase(const_iterator pos); //删除迭代器指向的元素
-
erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
-
clear(); //删除容器中所有元素
#include#include #include using namespace std; void print_vector(vector &v) { for (vector ::iterator it = v.begin(); it != v.end(); it++) { cout << *it << " "; } cout << endl; } void test01() //赋值操作 { vector v1; //尾插法 v1.push_back(10); v1.push_back(11); v1.push_back(12); v1.push_back(13); v1.push_back(14); v1.push_back(15); //遍历; print_vector(v1); //尾删法 v1.pop_back(); //遍历; print_vector(v1); //插入； v1.insert(v1.begin(), 100);//在头部插入数值100， print_vector(v1); //头部多次插入 v1.insert(v1.begin(), 2, 222); print_vector(v1); //删除 v1.erase(v1.begin()); print_vector(v1); //清空 v1.clear(); print_vector(v1); } int main() { test01(); system("pause"); return 0; }
总结：重点掌握单词和用法，合理使用
-
尾插 --- push_back
-
尾删 --- pop_back
-
插入 --- insert (位置迭代器)
-
删除 --- erase （位置迭代器）
-
清空 --- clear
vector数据存取
功能描述：
-
对vector中的数据的存取操作
void test01() //赋值操作
{
vectorv1;
for (int i = 0; i < 10; i++)
{
v1.push_back(i);
}
//利用中括号的方式来访问元素
for (int i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}
cout << endl;
//利用at的方式来访问元素
for (int i = 0; i < v1.size(); i++)
{
cout << v1.at(i) << " ";
}
cout << endl;
//获取第一个袁术
cout << "第一个元素: " << v1.front() << endl;
//获取最后一个袁术
cout << "最后一个元素: " << v1.back() << endl;
}
int main()
{
test01();
system("pause");
return 0;
}
总结：
-
除了用迭代器获取vector容器中元素，[ ]和at也可以
-
front返回容器第一个元素
-
back返回容器最后一个元素
vector互换容器
功能描述：
-
实现两个容器内元素进行互换
函数原型：
-
veb.swap(vec); // 将vec与本身veb的元素互换
作用是缩减内存占用，就是在运行程序的时候才会调用。
理解一下，在常规操作中，swap要先创建一个temp先接受，接收临时的值。然后再重新赋值，但是该方法并不用创建空间来接收临时的，直接从底层交换？
void print_vector(vector&v) { for (vector ::iterator it = v.begin(); it != v.end(); it++) { cout << *it << " "; } cout << endl; } void test01() //赋值操作 { vector v1; for (int i = 0; i < 10; i++) { v1.push_back(i); } cout << "打印v1数组" << endl; print_vector(v1); vector v2; for (int i = 10; i > 0; i--) { v2.push_back(i); } cout << "打印v2数组" << endl; print_vector(v2); v1.swap(v2); cout << "打印交换后数组" << endl; cout << "打印v1数组" << endl; print_vector(v1); cout << "打印v2数组" << endl; print_vector(v2); } int main() { test01(); system("pause"); return 0; }
swap可以使两个容器互换，可以达到实用的收缩内存效果
vector预留空间
功能描述：
-
减少vector在动态扩展容量时的扩展次数，就是个小工具，用来提高稳定
函数原型：
-
reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。
#include
void test01() { vector v; //预留空间 v.reserve(100000); int num = 0; int* p = NULL; for (int i = 0; i < 100000; i++) { v.push_back(i); if (p != &v[0]) { p = &v[0]; num++; } } cout << "num:" << num << endl; } int main() { test01(); system("pause"); return 0; } 如果数据量较大，可以一开始利用reserve预留空间，防止对此开辟空间的很多问题，如内存覆盖溢出，丢失
deque容器
deque容器基本概念
功能：
-
双端数组，可以对头端进行插入删除操作
deque与vector区别：
-
vector对于头部的插入删除效率低，数据量越大，效率越低
-
deque相对而言，对头部的插入删除速度回比vector快
-
vector访问元素时的速度会比deque快,这和两者内部实现有关
deque内部工作原理:
deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据
中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间
当0x01满了，从中控器在创建一个新的标注0x02，虽然看起来像是一片连续的
但其实分开的，因此他需要从尾部插入的时候，找到对应的编号插入数据即可，对应的，头插的时候，在数据前面的缓冲区创建存储地址，并更新节点即可，并不需要吧所有数据变动位置
eque容器的迭代器也是支持随机访问的
deque构造函数
功能描述：
-
deque容器构造（绰号双端数组）
函数原型：
-
deque
deqT; //默认构造形式 -
deque(beg, end); //构造函数将[beg, end)区间中的元素拷贝给本身。
-
deque(n, elem); //构造函数将n个elem拷贝给本身。
-
deque(const deque &deq); //拷贝构造函数
#include#include #include using namespace std; void print_deque(deque &d) { for (deque ::iterator it = d.begin(); it != d.end(); it++) { cout << *it << " "; } cout << endl; } void print_deque_const(const deque & d) { for (deque ::const_iterator it = d.begin(); it != d.end(); it++) { //测试是否可以修改 //*it = 100; cout << *it << " "; } cout << endl; } void test01() //赋值操作 { deque d1; for (int i = 0; i < 10; i++) { d1.push_back(i); } print_deque(d1); //区间赋值 deque d2(d1.begin(), d1.end()); //吧d1的之全部赋值给d2 print_deque(d2); //n个elem的方法 deque d3(10, 100); print_deque(d3); //拷贝构造 deque d4(d3); print_deque (d4); } int main() { test01(); system("pause"); return 0; }
总结，和vector一致
重点，如果想要限制数组改变，使用const，但是迭代器也要随之改变
deque赋值操作
功能描述：
-
给deque容器进行赋值
函数原型：
-
deque& operator=(const deque &deq); //重载等号操作符
-
assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
-
assign(n, elem); //将n个elem拷贝赋值给本身。
dequed1; for (int i = 0; i < 10; i++) { d1.push_back(i); } print_deque(d1); //区间赋值 deque d2(d1.begin(), d1.end()); //吧d1的之全部赋值给d2 print_deque(d2); //n个elem的方法 deque d3(10, 100); print_deque(d3); //拷贝构造 deque d4(d3); print_deque (d4);
deque大小操作
功能描述：
-
对deque容器的大小进行操作（和vector一致，规则也差不多）
函数原型：
-
deque.empty(); //判断容器是否为空
-
deque.size(); //返回容器中元素的个数
-
deque.resize(num); //重新指定容器的长度为num,若容器变长，则以默认值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除。
-
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置。//如果容器变短，则末尾超出容器长度的元素被删除。
功能描述：
-
对deque容器的大小进行操作
函数原型：
-
deque.empty(); //判断容器是否为空
-
deque.size(); //返回容器中元素的个数
-
deque.resize(num); //重新指定容器的长度为num,若容器变长，则以默认值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除。（deque这里是容量的限制，但是vector没有，可以无限去扩展）
-
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置。//如果容器变短，则末尾超出容器长度的元素被删除。
哦。我的错，指定了就是1，没指定就是0 d1.resize（15,0）
void test01() //赋值操作
{
dequed1;
for (int i = 0; i < 10; i++)
{
d1.push_back(i);
}
print_deque(d1);
if (d1.empty())
{
cout << "d1为空!" << endl;
}
else
{
cout << "d1不为空!" << endl;
}
//重新指定大小
d1.resize(15, 1);
print_deque(d1);
d1.resize(5);
print_deque(d1);
}
总结：deque有容量的概念，但是vector没有，这就内部结构的问题
-
deque没有容量的概念
-
判断是否为空 --- empty
-
返回元素个数 --- size
-
重新指定个数 --- resize
deque 插入和删除
功能描述：
-
向deque容器中插入和删除数据
函数原型：
两端插入操作：
-
push_back(elem); //在容器尾部添加一个数据
-
push_front(elem); //在容器头部插入一个数据
-
pop_back(); //删除容器最后一个数据
-
pop_front(); //删除容器第一个数据
指定位置操作：
-
insert(pos,elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置。
-
insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。
-
insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值。
-
clear(); //清空容器的所有数据
-
erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。
-
erase(pos); //删除pos位置的数据，返回下一个数据的位置。
#include#include #include using namespace std; void print_deuqe(deque & d) { for (deque ::iterator it = d.begin(); it != d.end(); it++) { cout << *it << " "; } cout << endl; } void test01() //赋值操作 { deque d1; d1.push_back(10); d1.push_back(20); d1.push_back(30); print_deuqe (d1); //尾插法 d1.push_back(40); d1.push_back(50); print_deuqe(d1); //头插法 d1.push_front(01); d1.push_front(02); print_deuqe(d1); //删除尾部最后一个数据 d1.pop_back(); print_deuqe(d1); //删除头部最后一个数据 d1.pop_front(); print_deuqe(d1); //insert插入法 d1.insert(d1.begin(), 1000); print_deuqe(d1); d1.insert(d1.begin(), 2, 2222); print_deuqe(d1); //按照区间插入 deque d2; d2.push_back(1); d2.push_back(2); d2.push_back(3); d1.insert(d1.begin(), d2.begin(), d2.end()); print_deuqe(d1); } void test02() { deque d1; d1.push_back(10); d1.push_back(20); d1.push_back(30); d1.push_back(40); d1.push_back(50); d1.push_back(60); print_deuqe(d1); cout << " 原始数据从10——60 " << endl; //删除 /删除[beg,end)区间的数据，返回下一个数据的位置。 d1.erase(d1.begin()); print_deuqe(d1); //如何跳跃删除，使数据偏移位置即可 deque ::iterator it = d1.begin(); it++; d1.erase(it); //这样就删除了第二个数据，同理可以使用for循环 print_deuqe(d1); //按区间删除 d1.erase(d1.begin(), d1.end()); print_deuqe(d1); d1.clear(); print_deuqe(d1); } int main() { test02(); system("pause"); return 0; }
总结：
-
插入和删除提供的位置是迭代器！
-
尾插 --- push_back
-
尾删 --- pop_back
-
头插 --- push_front
-
头删 --- pop_front
deque 数据存取
功能描述：
-
对deque 中的数据的存取操作
函数原型：
-
at(int idx); //返回索引idx所指的数据
-
operator[]; //返回索引idx所指的数据
-
front(); //返回容器中第一个数据元素
-
back(); //返回容器中最后一个数据元素
void test01() //赋值操作
{
dequed;
d.push_back(10);
d.push_back(20);
d.push_back(30);
d.push_front(100);
d.push_front(200);
d.push_front(300);
//`operator[]; ` //返回索引idx所指的数据
for (int i = 0; i < d.size(); i++)
{
cout << d[i] << " ";
}
cout << endl;
//通过at方式
for (int i = 0; i < d.size(); i++)
{
cout << d.at(i) << " ";
}
cout << endl;
//`front(); ` //返回容器中第一个数据元素
cout << "第一个数据元素:" << d.front() <
总结：
-
除了用迭代器获取deque容器中元素，[ ]和at也可以
-
front返回容器第一个元素
-
back返回容器最后一个元素
deque 排序
功能描述：
-
利用算法实现对deque容器进行排序
-
sort算法非常实用，使用时包含头文件 algorithm即可
算法：
-
sort(iterator beg, iterator end) //对beg和end区间内元素进行排序
#include
#include
#include
#include
using namespace std;
void printDeque(const deque& d)
{
for (deque::const_iterator it = d.begin(); it != d.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test01()
{
//创建数组
deque d;
d.push_back(10);
d.push_back(20);
d.push_back(20);
d.push_back(30);
d.push_front(100);
d.push_front(200);
//排序算法
printDeque(d);
sort(d.begin(), d.end());
printDeque(d);
}
int main() {
test01();
system("pause");
return 0;
}
总结：sort算法非常实用，使用时包含头文件 algorithm即可
