参考文章：https://www.bilibili.com/video/BV1et411b73Z?p=204
deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据
中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间
C++中的vector和deque都是STL（标准模板库）中的容器，它们都可以用来存储一系列的元素。但是它们的内部工作原理有所不同。
vector是一个动态数组，它在内存中是连续存储的。当vector的大小超过了它的容量时，vector会重新分配一块更大的内存，并将原来的元素复制到新的内存中。这个过程可能会导致内存的重新分配和元素的复制，因此在插入或删除元素时，vector的效率可能会受到影响。
deque是一个双端队列，它在内存中不是连续存储的。deque通常是由多个固定大小的缓冲区组成的，每个缓冲区都是一个独立的数组。当deque的大小超过了当前缓冲区的容量时，deque会分配一个新的缓冲区，并将元素插入到新的缓冲区中。这个过程不需要重新分配内存或复制元素，因此deque在插入或删除元素时，效率比vector更高。
总的来说，vector适用于需要随机访问元素的场景，而deque适用于需要在两端插入或删除元素的场景。
deque<T> deqT; //默认构造形式deque(beg, end); //构造函数将[beg, end)区间中的元素拷贝给本身。deque(n, elem); //构造函数将n个elem拷贝给本身。deque(const deque &deq); //拷贝构造函数#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
using namespace std;
void printDeque(const deque<int> &d)
{
// for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
// {
// cout << *it << " ";
// }
for (auto i : d)
{
cout << i << " ";
}
cout << endl;
}
// deque构造
void test01()
{
deque<int> d1; // 无参构造函数
for (int i = 0; i < 10; i++)
{
d1.push_back(i);
}
printDeque(d1);
cout << "-------------------------" << endl;
deque<int> d2(d1.begin(), d1.end());
printDeque(d2);
cout << "-------------------------" << endl;
deque<int> d3(10, 100); // 10个值为100的元素
printDeque(d3);
cout << "-------------------------" << endl;
deque<int> d4 = d3;
printDeque(d4);
cout << "-------------------------" << endl;
}
int main()
{
test01();
std::cout << "Press ENTER to continue...";
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 读取内容直到用户输入enter键
return EXIT_SUCCESS;
}
总结：deque容器和vector容器的构造方式几乎一致，灵活使用即可
deque& operator=(const deque &deq); //重载等号操作符
assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem); //将n个elem拷贝赋值给本身。
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
using namespace std;
// cout << "------------------" << endl;
void printDeque(const deque<int> &d)
{
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
// 赋值操作
void test01()
{
deque<int> d1;
for (int i = 0; i < 10; i++)
{
d1.push_back(i);
}
printDeque(d1);
cout << "------------------" << endl;
deque<int> d2;
d2 = d1;
printDeque(d2);
cout << "------------------" << endl;
deque<int> d3;
d3.assign(d1.begin(), d1.end());
printDeque(d3);
cout << "------------------" << endl;
deque<int> d4;
d4.assign(10, 100);
printDeque(d4);
cout << "------------------" << endl;
}
int main()
{
test01();
std::cout << "Press ENTER to continue...";
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 读取内容直到用户输入enter键
return EXIT_SUCCESS;
}
总结：deque赋值操作也与vector相同，需熟练掌握
deque.empty(); //判断容器是否为空
deque.size(); //返回容器中元素的个数
deque.resize(num); //重新指定容器的长度为num,若容器变长，则以默认值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置。
//如果容器变短，则末尾超出容器长度的元素被删除。
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
using namespace std;
// cout << "------------------" << endl;
void printDeque(const deque<int> &d)
{
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
// 大小操作
void test01()
{
deque<int> d1;
for (int i = 0; i < 10; i++)
{
d1.push_back(i);
}
printDeque(d1);
cout << "------------------" << endl;
// 判断容器是否为空
if (d1.empty())
{
cout << "d1为空!" << endl;
}
else
{
cout << "d1不为空!" << endl;
// 统计大小
cout << "d1的大小为：" << d1.size() << endl;
}
cout << "------------------" << endl;
// 重新指定大小
d1.resize(15, 1); // 重新指定大小为15，以数值1补空
printDeque(d1);
cout << "------------------" << endl;
d1.resize(5);
printDeque(d1);
cout << "------------------" << endl;
}
int main()
{
test01();
std::cout << "Press ENTER to continue...";
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 读取内容直到用户输入enter键
return EXIT_SUCCESS;
}
总结：
两端插入操作：
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 <vector>
#include <algorithm>
#include <iostream>
#include <deque>
using namespace std;
// cout << "------------------" << endl;
void printDeque(const deque<int> &d)
{
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
// 两端操作
void test01()
{
deque<int> d;
// 尾插
d.push_back(10);
d.push_back(20);
// 头插
d.push_front(100);
d.push_front(200);
printDeque(d); // 200 100 10 20
// 尾删
d.pop_back();
// 头删
d.pop_front();
printDeque(d); // 100 10
}
// 插入
void test02()
{
deque<int> d;
d.push_back(10);
d.push_back(20);
d.push_front(100);
d.push_front(200);
printDeque(d); // 200 100 10 20
d.insert(d.begin(), 1000);
printDeque(d); // 1000 200 100 10 20
d.insert(d.begin(), 2, 10000);
printDeque(d); // 10000 10000 1000 200 100 10 20
deque<int> d2;
d2.push_back(1);
d2.push_back(2);
d2.push_back(3);
d.insert(d.begin(), d2.begin(), d2.end());
printDeque(d); // 1 2 3 10000 10000 1000 200 100 10 20s
}
// 删除
void test03()
{
deque<int> d;
d.push_back(10);
d.push_back(20);
d.push_front(100);
d.push_front(200);
printDeque(d); // 200 100 10 20
d.erase(d.begin());
printDeque(d); // 100 10 20
d.erase(d.begin(), d.end());
d.clear();
printDeque(d); // 空
}
int main()
{
test01();
cout << "------------------" << endl;
test02();
cout << "------------------" << endl;
test03();
cout << "------------------" << endl;
std::cout << "Press ENTER to continue...";
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 读取内容直到用户输入enter键
return EXIT_SUCCESS;
}
总结：
at(int idx); //返回索引idx所指的数据operator[]; //返回索引idx所指的数据front(); //返回容器中第一个数据元素back(); //返回容器中最后一个数据元素#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
using namespace std;
// cout << "------------------" << endl;
void printDeque(const deque<int> &d)
{
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
// 数据存取
void test01()
{
deque<int> d;
d.push_back(10);
d.push_back(20);
d.push_front(100);
d.push_front(200);
for (int i = 0; i < d.size(); i++)
{
cout << d[i] << " ";
}
// 200 100 10 20
cout << endl;
for (int i = 0; i < d.size(); i++)
{
cout << d.at(i) << " ";
}
// 200 100 10 20
cout << endl;
cout << "front:" << d.front() << endl; // front:200
cout << "back:" << d.back() << endl; // back:20
}
int main()
{
test01();
std::cout << "Press ENTER to continue...";
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 读取内容直到用户输入enter键
return EXIT_SUCCESS;
}
总结：
sort(iterator beg, iterator end) //对beg和end区间内元素进行排序#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
using namespace std;
// cout << "------------------" << endl;
void printDeque(const deque<int> &d)
{
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test01()
{
deque<int> d;
d.push_back(10);
d.push_back(20);
d.push_front(100);
d.push_front(200);
printDeque(d); // 200 100 10 20
sort(d.begin(), d.end());
printDeque(d); // 10 20 100 200
}
int main()
{
test01();
std::cout << "Press ENTER to continue...";
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 读取内容直到用户输入enter键
return EXIT_SUCCESS;
}
总结：sort算法非常实用，使用时包含头文件 algorithm即可
有5名选手：选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分。
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
using namespace std;
// cout << "------------------" << endl;
// 选手类
class Person
{
public:
Person(string name, int score)
{
this->m_Name = name;
this->m_Score = score;
}
string m_Name; // 姓名
int m_Score; // 平均分
};
void createPerson(vector<Person> &v)
{
string nameSeed = "ABCDE";
for (int i = 0; i < 5; i++)
{
string name = "选手";
name += nameSeed[i];
int score = 0;
Person p(name, score);
// 将创建的person对象 放入到容器中
v.push_back(p);
}
}
// 打分
void setScore(vector<Person> &v)
{
for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
{
// 将评委的分数 放入到deque容器中
deque<int> d;
for (int i = 0; i < 10; i++)
{
int score = rand() % 41 + 60; // 60 ~ 100
d.push_back(score);
}
cout << "选手： " << it->m_Name << " 打分： " << endl;
for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
{
cout << *dit << " ";
}
cout << endl;
// 排序
sort(d.begin(), d.end());
// 去除最高和最低分
d.pop_back();
d.pop_front();
// 取平均分
int sum = 0;
for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++)
{
sum += *dit; // 累加每个评委的分数
}
int avg = sum / d.size();
// 将平均分 赋值给选手身上
it->m_Score = avg;
}
}
void showScore(vector<Person> &v)
{
for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
{
cout << "姓名： " << it->m_Name << " 平均分： " << it->m_Score << endl;
}
}
int main()
{
// 随机数种子
srand((unsigned int)time(NULL));
// 1、创建5名选手
vector<Person> v; // 存放选手容器
createPerson(v);
// 测试
for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
{
// cout << "姓名： " << (*it).m_Name << " 分数： " << (*it).m_Score << endl;
cout << "姓名： " << it->m_Name << " 分数： " << it->m_Score << endl;
}
cout << "------------------" << endl;
// 2、给5名选手打分
setScore(v);
cout << "------------------" << endl;
// 3、显示最后得分
showScore(v);
cout << "------------------" << endl;
std::cout << "Press ENTER to continue...";
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 读取内容直到用户输入enter键
return EXIT_SUCCESS;
}
总结： 选取不同的容器操作数据，可以提升代码的效率