STL系列学习参考：STL 数据结构与算法__Zwy@的博客-CSDN博客
https://blog.csdn.net/bite_zwy/category_12852141.html
各位于晏，亦菲们，请点赞关注！
我的个人主页：
_Zwy@-CSDN博客
学习C++ STL的三个境界，会用，明理，能扩展，STL中的所有容器都遵循这个规律，下面我们就按照这三个境界来学习deque
目录
1、前言
2、STL标准库中的deque
2.1、 模板参数（Template Parameters）
2.2、成员类型（Member types）
2.3、成员函数（Member functions）
2.3.1、Constructor 构造函数
Ⅰ、默认构造函数（default）
Ⅱ、填充构造函数（fill）
Ⅲ、迭代器区间构造函数（range）
Ⅳ、拷贝构造函数（copy）
Ⅴ、移动构造函数（move）
Ⅵ、初始化列表构造函数（initializer list）
2.3.2、Iterators 迭代器
Ⅰ、begin（）
Ⅱ、end（）
Ⅲ、rbegin（）
Ⅳ、rend（）
Ⅴ、const_iterators
2.3.3、Capacity 容量操作
Ⅰ、size（）
Ⅱ、max_size（）
Ⅲ、 resize（）
Ⅳ、empty（）
Ⅵ、shrink_to_fit（） 编辑
2.3.4、Element access 元素访问
Ⅰ、operator[ ]
Ⅱ、at（）
Ⅲ、front（）
Ⅳ、back（）
2.3.5、Modifiers 增删查改
Ⅰ、push_back（）
Ⅱ、push_front（）
Ⅲ、pop_back（）
Ⅳ、pop_front（）
Ⅴ、insert（）
Ⅵ、erase（）
Ⅶ、swap（）
Ⅷ、clear
Ⅸ、emplace系列接口
3、deque的结构
3.1、deque容器的结构
3.2 、deque的迭代器结构
3.3、迭代器的遍历
3.3.1、单个缓冲区的遍历
3.3.2、跨越缓冲区的遍历
4、relational operators 关系操作符
5、deque的迭代器失效问题
5.1、插入元素导致的迭代器失效
【C++标准：】
【VS下的检查机制：】
【Linux下g++的检查机制：】
5.2、删除操作导致的迭代器失效问题
【C++标准：】
【VS下的检查机制：】
【Linux下g++的检查机制：】
5.3、迭代器失效问题的解决
5.4、迭代器使用总结
6、deque的应用场景
6.1、队列和栈的实现
6.2、滑动窗口问题
6.3、需要在两端频繁插入和删除元素的场景
7、本文小结
1、前言
上期我们讲到C++ STL标准库中容器适配器stack的queue的默认底层容器都是deque，我们对deque的结构，存储空间，以及迭代器进行了简单的介绍，接下来我们会着重讲解deque的使用和底层结构，以及deque在实践中的应用场景。
温故而知新，可以为师矣！
2、STL标准库中的deque
参考文档：
cplusplus.com/reference/deque/deque/
deque又叫双端队列（Double ended queue），头文件为<deque>，deque是 C++ 标准模板库（STL）中的一个容器类，它允许在两端进行高效的插入和删除操作。
2.1、 模板参数（Template Parameters）
模板参数T
表示元素的类型，别名为成员类型deque::value_type
模板参数Alloc
用于定义存储分配模型的分配器对象的类型。默认情况下，使用allocator类模板，它定义了最简单的内存分配模型，并且与值无关。别名为成员类型deque::allocator_type。
2.2、成员类型（Member types）
| member type | definition | notes |
|---|---|---|
| value_type | The first template parameter (T) | |
| allocator_type | The second template parameter (Alloc) | defaults to: allocator<value_type> |
| reference | allocator_type::reference | for the default allocator: value_type& |
| const_reference | allocator_type::const_reference | for the default allocator: const value_type& |
| pointer | allocator_type::pointer | for the default allocator: value_type* |
| const_pointer | allocator_type::const_pointer | for the default allocator: const value_type* |
| iterator | a random access iterator to value_type | convertible to const_iterator |
| const_iterator | a random access iterator to const value_type | |
| reverse_iterator | reverse_iterator<iterator> | |
| const_reverse_iterator | reverse_iterator<const_iterator> | |
| difference_type | a signed integral type, identical to: iterator_traits<iterator>::difference_type | usually the same as ptrdiff_t |
| size_type | an unsigned integral type that can represent any non-negative value of difference_type | usually the same as size_t |
value_type
定义：第一个模板参数（T）。
说明：这表示由分配器所处理的元素类型。例如，如果allocator用于int类型，那么value_type就是int。
allocator_type
定义：第二个模板参数（Alloc），默认情况下为allocator<value_type>。
说明：它代表分配器自身的类型。如果没有显式指定分配器类型，它会根据所处理的元素类型value_type来确定自身类型。
reference 和 const_reference
reference 定义：对于默认分配器，是value_type&。
const_reference 定义：对于默认分配器，是const value_type&。
说明：这些类型别名用于处理对元素的引用。reference用于可修改的引用，const_reference用于常量引用。
pointer 和 const_pointer
pointer 定义：对于默认分配器，是value_type*。
const_pointer 定义：对于默认分配器，是const value_type*。
说明：它们分别用于指向元素的指针和指向常量元素的指针。
iterator 和 const_iterator
iterator 定义：一个指向value_type的随机访问迭代器，可转换为const_iterator。
const_iterator 定义：一个指向const value_type的随机访问迭代器。
说明：这些迭代器用于遍历由分配器管理的元素序列。const_iterator用于只读操作，而iterator可以用于读写操作。
reverse_iterator 和 const_reverse_iterator
reverse_iterator 定义：reverse_iterator<iterator>。
const_reverse_iterator 定义：reverse_iterator<const_iterator>。
说明：这些是反向迭代器，用于反向遍历元素序列。
difference_type
定义：一个有符号整数类型，等同于iterator_traits<iterator>::difference_type，通常与ptrdiff_t相同。
说明：用于表示迭代器之间的距离，例如在计算两个迭代器之间相差多少个元素时使用。
size_type
定义：一个无符号整数类型，能够表示difference_type的任何非负值，通常与size_t相同。
说明：用于表示容器的大小，例如元素的数量等。
这些成员类型在实现自定义分配器或理解标准库容器如何与分配器协同工作时非常重要。
2.3、成员函数（Member functions）
2.3.1、Constructor 构造函数
Ⅰ、默认构造函数（default）
它接受一个可选的分配器参数alloc，如果没有提供，将使用默认的分配器构造空的deque
void TestConstructor(){//默认构造，构造空的dequedeque<int> deq_int;deque<string> deq2_str;deque<double> deq3_dou;}Ⅱ、填充构造函数（fill）
构造含n个默认初始化元素的deque
void TestConstructor(){//填充构造 构造含n个默认初始化元素的deque//含5个int 的默认值0的deque deque<int> deq_int(5);//含5个stirng 的默认构造 "" 空串的deque deque<string> deq_str(3);//含5个double 的默认值 0.000000的deque deque<double> deq_dou(7);}构造含n个value元素的deque
void TestConstructor(){//5个6deque<int> deq_i(5, 6);//3个hello worlddeque<string> deq_s(3, "hello world");//7个3.14deque<double> deq_d(7, 3.14);}Ⅲ、迭代器区间构造函数（range）
构造一个包含与迭代器区间[first，last)范围相同数量元素的容器，每个元素以相同的顺序从该范围内的相应元素构造
void TestConstructor(){//vector的迭代器去区间构造vector<int> v{ 1,2,3,4,5 };deque<int> deq_v(v.begin(), v.end());//list的迭代器去区间构造list<string> l{ "ab","bc","cd","de"};deque<string> deq_l(l.begin(), l.end());//string的迭代器去区间构造string s("helloworld");deque<char> deq_s(s.begin(), s.end());}n(), s.end());Ⅳ、拷贝构造函数（copy）
用被拷贝的deque对象中每个元素的副本按相同顺序构造一个容器。拷贝构造后两个容器的元素完全相同。
void TestConstructor(){//vector的迭代器去区间构造deq_vvector<int> v{ 1,2,3,4,5 };deque<int> deq_v(v.begin(), v.end());//deq_cp拷贝构造deque<int> deq_cp(deq_v);}Ⅴ、移动构造函数（move）
移动构造会使用来构造的deque对象的资源被move转移，此时该对象会变成空容器。
void TestConstructor(){//vector的迭代器去区间构造deq_vvector<int> v{ 1,2,3,4,5 };deque<int> deq_v(v.begin(), v.end());//deq_mv移动构造deque<int> deq_mv(move(deq_v));}Ⅵ、初始化列表构造函数（initializer list）
deque同样支持C++11提出的initializer list构造
void TestConstructor(){//初始化列表构造函数deque<int> deq_i{ 1,2,3,4,5 };deque<string> deq_s{ "aa","bb","cc","dd" };deque<double> deq_d{ 1.1,2,2,3.14,5.28 };}2.3.2、Iterators 迭代器
deque（双端队列）的迭代器属于随机访问迭代器类型
支持随机访问，可以像指针一样进行算术运算
支持所有迭代器操作，除了随机访问操作外，还支持其他迭代器操作，如++（前缀和后缀）、--（前缀和后缀）、== 、!= 、< 、> 、<= 、>=等比较操作。
随机访问迭代器的操作通常具有常数时间复杂度，这使得在deque这样的容器上进行元素访问和操作非常高效。
Ⅰ、begin（）
begin（）返回指向deque容器中第一个元素的迭代器
Ⅱ、end（）
end（）迭代器返回的是指向deque容器中 “尾后元素”（past - the - end element）的迭代器。这个 “尾后元素” 是一个理论上存在的元素，它并不实际存在于deque容器中，位于容器最后一个元素之后。它不指向任何元素，因此不能被解引用。
如果容器为空，该函数返回与deque::begin相同的结果。
正向迭代器使用示例：
void TestIterator(){//初始化列表构造函数deque<int> deq{ 1,2,3,4,5 };deque<int>::iterator it = deq.begin();while (it != deq.end()){cout << *it << " ";++it;}cout << endl;}输出：
Ⅲ、rbegin（）
返回一个指向容器中最后一个元素的反向迭代器（即容器的反向起始）。rbegin指向end所指向的元素的前一个。
Ⅳ、rend（）
返回一个反向迭代器，指向deque容器中第一个元素之前的理论元素（该元素被认为是其反向端），即指向begin（）的前一个元素，该元素实际上不存在。
反向迭代器使用示例：
void TestIterator(){//初始化列表构造函数deque<int> deq{1,2,3,4,5};deque<int>::reverse_iterator it = deq.rbegin();while (it != deq.rend()){cout << *it << " ";++it;}cout << endl;}输出：
Ⅴ、const_iterators
如下几个迭代器是const_iterator,与普通迭代器用法相同，但是只可读不可写,通常用于遍历容器
2.3.3、Capacity 容量操作
Ⅰ、size（）
返回当前deque容器中有效元素的个数
Ⅱ、max_size（）
返回最大尺寸，返回deque容器可以容纳的最大元素个数
Ⅲ、 resize（）
调整容器的size，使其包含n个元素。
如果n小于当前容器的size，则容器将被减少到前n个元素，删除超出的元素（并销毁它们）。
如果n大于当前容器的size，则通过在末尾插入所需的元素来扩展内容，以达到n的大小。如果指定了val，则将新元素初始化为val的副本，否则将其进行值初始化（默认初始值）。
示例：
void Testresize(){deque<int> mydeque{ 1,2,3,4,5,6 };deque<int>::iterator it;//n小于size的情况mydeque.resize(5);//n大于size且没有value情况mydeque.resize(8, 100);//n大于size且指定value情况mydeque.resize(12);cout << "mydeque contains:" << endl;for (it = mydeque.begin(); it != mydeque.end(); ++it)cout << " " << *it;cout << endl;}输出：
Ⅳ、empty（）
判断容器是否为空，为空返回true，否则返回false
Ⅵ、shrink_to_fit（）
请求容器减少其内存使用以适应其大小。deque容器所分配的内存可能比存储其当前元素所需的内存多：这是因为大多数库将deque实现为动态数组，它可以保留已删除元素的已分配空间，或者提前分配额外的容量以允许更快的插入操作
2.3.4、Element access 元素访问
Ⅰ、operator[ ]
通过下标访问deque容器中的元素，类似vector的operator[ ]，返回下标为n的元素的引用，下标从0开始。operattor[ ]不会强制检查，如果访问的元素的下标超出deuqe对象的范围，则会导致未定义的错误，不同的编译器的处理方式不同！
正常访问：
void Test(){deque<int> deq{ 1,2,3,4,5 };for (size_t i = 0; i < deq.size(); ++i){cout << deq[i] << " ";}cout << endl;}输出：
越界访问：
void Test(){deque<int> deq{ 1,2,3,4,5 };for (size_t i = 0; i < 10; ++i){cout << deq[i] << " ";}cout << endl;}vs下的处理方式：
调试断言失败，程序崩溃，试图访问超出容器范围的下标会导致错误。
Linux下g++的处理方式：
代码编译通过，程序正常运行，但是输出结果错误
输出：
Ⅱ、at（）
访问元素，返回对deque容器对象中下标为n的元素的引用。
该函数自动检查n是否在容器中有效元素的范围内，如果不在，则抛出out_of_range异常（即，如果n大于或等于其大小）。这与成员操作符[]相反，它不检查边界。
正常访问：
void Test(){deque<int> deq{ 1,2,3,4,5 };for (size_t i = 0; i < deq.size(); ++i)cout << deq.at(i) << " ";cout << endl;}输出：
越界访问:会强制检查并且抛出异常
void Test(){deque<int> deq{ 1,2,3,4,5 };//会抛出out_of_range异常，因为已经越界，捕获异常try{cout << deq.at(10) << endl;}catch (const out_of_range& e){//打印异常信息cerr << "Caught out_of_range exception: " << e.what() << endl;}}vs下捕获到的异常信息：
Linux下g++捕获到的异常信息：
在使用at函数访问deque容器中的元素时，如果出现了越界访问，但是没有捕获异常，那么就会导致程序崩溃！
Ⅲ、front（）
返回对deque容器中第一个元素的引用。在空容器上调用此函数会导致未定义行为。与operator[]相同，vs下程序崩溃，Linux下g++编译通过，程序输出结果错误！
Ⅳ、back（）
访问最后一个元素，返回对容器中最后一个元素的引用。在空容器上调用此函数会导致未定义行为。同front（）
示例：
void Test(){deque<int> deq{ 1,2,3,4,5 };cout << "front()：" << deq.front() << endl;cout << "back()：" << deq.back() << endl;}输出：
2.3.5、Modifiers 增删查改
Ⅰ、push_back（）
在末尾添加元素，在deque容器的最后一个当前元素之后，在其末尾添加一个新元素
Ⅱ、push_front（）
在开头插入元素，在deque容器的开头，即当前第一个元素的正前方插入一个新元素
示例：
void Test(){deque<int> deq;deq.push_back(100);deq.push_front(1);//对空容器插入后访问cout << "front()：" << deq.front() << endl;cout << "back()：" << deq.back() << endl;}输出：
Ⅲ、pop_back（）
删除deque容器中的最后一个元素，有效地将容器大小减少一个。
Ⅳ、pop_front（）
删除deque容器中的第一个元素，有效地将其大小减少一个。
示例：
void Test(){deque<int> deq{ 1,2,3,4,5 };cout << "初始front()：" << deq.front() << " "<<"初始back():"<< deq.back() << endl;deq.pop_back();deq.pop_front();cout << endl;cout << "当前front()：" << deq.front() <<" " << "当前back()：" << deq.back() << endl;}输出：
Ⅴ、insert（）
插入元素，通过在指定位置的元素前面插入新元素来扩展deque容器。插入的位置是一个元素的迭代器
形参决定插入多少个元素以及将元素初始化为哪些值。
返回值，指向第一个新插入元素的迭代器。
示例：
void Test(){vector<int> v{ 6,6,6 };deque<int> deq{ 1,2,3,4,5 };//在position位置插入valuedeq.insert(deq.begin(), -100);//在position位置插入n个valuedeq.insert(deq.begin() + 2, 3, 100);//在position位置插入一段迭代器区间deq.insert(deq.end(), v.begin(), v.end());for (size_t i = 0; i < deq.size(); ++i)cout << deq[i] << " ";cout << endl;}输出：
Ⅵ、erase（）
删除元素，从deque容器中移除单个元素或一系列元素。
参数，单个元素的迭代器或者一系列元素的迭代器区间【first,last】
返回值，指向被函数调用删除的最后一个元素后面元素的迭代器，如果删除了容器中的最后一个元素，则返回end迭代器。
示例：
void Test(){deque<int> deq{ 1,2,3,4,5,6,7,8,9,10 };//移除单个元素deq.erase(deq.begin() + 4);deq.erase(deq.end() - 2);//移除一段迭代器区间deq.erase(deq.begin() + 3, deq.end() - 2);for (size_t i = 0; i < deq.size(); ++i)cout << deq[i] << " ";cout << endl;}输出：
Ⅶ、swap（）
交换两个deque容器的内容
示例：
void Test(){deque<int> deq1{ 1,2,3,4,5 };deque<int> deq2{ 6,7,8,9,10 };deq1.swap(deq2);cout << "deq1:" << " ";for (size_t i = 0; i < deq1.size(); ++i)cout << deq1[i] << " ";cout << endl;cout << "deq2:" << " ";for (size_t i = 0; i < deq1.size(); ++i)cout << deq2[i] << " ";}输出：
Ⅷ、clear
从deque中移除所有元素，使容器的大小为0。
示例：
void Test(){deque<int> deq{1,2,3,4,5 };deq.clear();cout << "size():" << deq.size() << endl;if (deq.empty())cout << "deq容器已被清空" << endl;}输出：
Ⅸ、emplace系列接口
emplace系列接口涉及C++11的可变参数模板，以及右值引用的移动语义，这里我只进行简单的使用示例。具体原理请移步下面这篇博文：
深入探索C++11 第三弹：C++11完结，迈进高效编程的新纪元-CSDN博客
示例：
void Test(){deque<pair<string,string>> deq;deq.emplace(deq.begin(), "apple", "苹果"); //deq.emplace_front("apple", "苹果");deq.emplace(deq.end(), "banana", "香蕉"); //deq.emplace_back("apple", "苹果");cout << deq.front().first <<" :"<<deq.front().second << endl;cout << deq.back().first <<" :"<< deq.back().second << endl;}输出：
3、deque的结构
deque作为STL标准库中stack和queue的底层容器，是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。它的元素在内存中不是连续存储的，而是由多个固定大小的数组块组成，这些块在逻辑上是连续的。
3.1、deque容器的结构
deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个
动态的二维数组 ，其底层结构如下图所示：
多个缓冲区的组合：deque内部维护了一个指向这些缓冲区的指针数组（通常称为映射，map）。每个缓冲区是一段连续的内存空间，用于存储deque中的元素。当需要存储的元素数量增加时，deque会动态分配新的缓冲区，并将这些缓冲区通过指针数组组织起来
元素存储方式：元素在这些缓冲区中按照顺序存储，就像它们在一个连续的内存空间中一样。例如，如果一个deque中有 10 个元素，可能会存储在两个缓冲区中，第一个缓冲区存储前几个元素，第二个缓冲区存储剩下的元素，而从用户的角度来看，这些元素是连续排列的。
3.2 、deque的迭代器结构
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其 “ 整体连续 ” 以及随机访问的假象，落在了 deque 的迭代器身上， 因此deque 的迭代器设计就比较复杂，如下图所示：
那deque是如何借助其迭代器维护其假想连续的结构呢？ 通过对迭代器的特殊封装：
deque的迭代器是一个相对复杂的结构。它不仅要能够指向当前元素，还需要知道所在的缓冲区以及在该缓冲区中的位置。
deque的迭代器包含多个成员，用于记录其在deque底层结构中的位置信息。它主要包含一个指向当前元素的指针（cur）、一个指向所在缓冲区起始位置的指针（first）和一个指向所在缓冲区结束位置的指针（last），以及一个指向deque中缓冲区数组（map）的指针（node）。
当迭代器被初始化时，这些指针会根据deque的初始状态进行设置。例如，当迭代器指向deque的第一个元素时，cur指向第一个缓冲区（如果只有一个缓冲区）的第一个元素，first也指向这个缓冲区的第一个元素，last指向这个缓冲区的最后一个元素，node指向包含这个缓冲区的map中的相应位置。
3.3、迭代器的遍历
3.3.1、单个缓冲区的遍历
在单个缓冲区内的遍历
当迭代器在单个缓冲区内移动时，只要cur指针没有超出last指针的范围，就可以正常地通过递增cur指针来遍历元素。
例如，假设一个deque的某个缓冲区存储了 5 个元素，迭代器从缓冲区的第一个元素开始，每次递增cur指针，就可以访问到这个缓冲区内的后续元素，就像在普通的连续内存数组中遍历一样。其时间复杂度接近O(1)，因为在单个连续的内存块内访问元素主要是通过简单的指针算术运算。
3.3.2、跨越缓冲区的遍历
跨越缓冲区的遍历
当迭代器的cur指针到达当前缓冲区的last指针位置时，就需要跨越到下一个缓冲区。此时，迭代器会通过node指针找到下一个缓冲区在map中的位置。
具体操作包括更新first、last和cur指针。first和last指针会被重新设置为指向新缓冲区的起始和结束位置，cur指针会被设置为新缓冲区的起始位置。然后，继续在新缓冲区中进行遍历。
跨越缓冲区的操作相对复杂一些，会带来一定的额外开销。不过，这种情况在整个deque的遍历过程中不是频繁发生的，除非deque中的元素分布在多个缓冲区中，且遍历过程需要频繁地在缓冲区之间切换。其时间复杂度与缓冲区的数量和元素在缓冲区之间的分布有关，但总体来说，在遍历整个deque时，由于缓冲区之间的切换操作，其随机访问性能比vector（基于单一连续内存块）要差一些。
4、relational operators 关系操作符
首先比较两个deque的第一个元素。如果第一个deque的第一个元素小于第二个deque的第一个元素，那么第一个deque小于第二个deque；如果第一个元素大于第二个元素，那么第一个deque大于第二个deque。
如果两个deque的第一个元素相等，那么继续比较第二个元素，以此类推。
如果在比较过程中，一个deque的元素已经全部比较完，而另一个deque还有剩余元素，那么元素先比较完的deque小于另一个deque。
示例：
void Test(){deque<int> foo(3, 100); // three ints with a value of 100deque<int> bar(2, 200); // two ints with a value of 200if (foo == bar) std::cout << "foo and bar are equal\n";if (foo != bar) std::cout << "foo and bar are not equal\n";if (foo < bar) std::cout << "foo is less than bar\n";if (foo > bar) std::cout << "foo is greater than bar\n";if (foo <= bar) std::cout << "foo is less than or equal to bar\n";if (foo >= bar) std::cout << "foo is greater than or equal to bar\n";}输出：
5、deque的迭代器失效问题
5.1、插入元素导致的迭代器失效
【C++标准：】
在deque中间插入元素当在deque中间插入元素时，会导致插入点及其之后的迭代器失效。因为插入操作可能会引起元素在缓冲区之间的重新分配，或者改变现有缓冲区中的元素排列。
在deque头部插入元素使用push_front在deque头部插入元素可能会导致所有迭代器失效。因为在头部插入元素可能会引起内部缓冲区的重新分配或者调整，改变了元素的存储布局。
在deque尾部插入元素通常情况下，使用push_back在deque尾部插入元素不会导致已有迭代器失效。但如果deque需要重新分配内存（例如达到容量上限时），所有迭代器会失效。
不同的编译器对于迭代器失效的检查不同：
【VS下的检查机制：】
Visual Studio（VS）对于代码规范性和潜在错误有着比较严格的检查机制，基于一种保守的策略来防止潜在的错误使用迭代器情况，所以VS认为只要在deque中插入元素，都会导致原来的迭代器失效。
deque中间插入元素：
void Test(){deque<int> dq = { 1, 2, 3, 4, 5 };auto it = dq.begin();auto position= dq.begin() + 2;dq.insert(position, 10); // 在3之前插入10// 此时，vs认为原来所有的迭代器都失效//cout << *it << endl; it已经失效，继续访问就会报错}deque头部插入元素：
void Test(){deque<int> dq = { 1, 2, 3, 4, 5 };auto it = dq.begin()+3;//指向4dq.push_front(10); // 在1之前插入10// 此时，vs认为原来所有的迭代器都失效//cout << *it << endl; //it已经失效，继续访问就会报错}在deque尾部插入元素：
void Test(){deque<int> dq = { 1, 2, 3, 4, 5 };auto it = dq.begin()+1;//指向2dq.push_back(10); // 在5之后插入10，尾插10// 此时，vs认为原来所有的迭代器都失效//cout << *it << endl; //it已经失效，继续访问就会报错}访问失效的迭代器导致程序崩溃
综上所述，由于deque底层缓冲区的复杂结构和迭代器的特殊封装，以及VS的严格检查机制，只要在deque的任意位置插入元素，都会导致原来所有的迭代器失效。
【Linux下g++的检查机制：】
在 Linux 下的 g++ 编译器对于迭代器失效后的访问，可能不会像某些其他编译器（如 Visual Studio）那样严格报错。当使用已经失效的deque迭代器访问元素时，这是一种未定义行为。g++ 编译器在这种情况下可能没有立即给出错误提示，而是继续执行代码，可能会出现看似 “正确” 的结果。但这并不意味着迭代器没有失效，只是 g++ 编译器没有对这种错误进行严格检查
deque的底层结构由多个缓冲区组成。在某些情况下，即使迭代器已经失效，但由于内存布局的特点和元素存储的连续性（在每个缓冲区内部），g++ 编译器可能会按照失效迭代器原来指向的内存位置继续访问，而这个位置恰好还保存着看似正确的数据。但这种情况是不可靠的，因为任何微小的改变（如重新分配缓冲区、插入更多元素等）都可能导致访问错误或程序崩溃。
deque中间插入元素：
插入位置之前的迭代器不会失效，仍然可以正常使用
void Test() { deque<int> dq = { 1, 2, 3, 4, 5 }; auto it = dq.begin() + 1; auto position = dq.begin() + 3; dq.insert(position, 10); // 在4之前插入10 // 插入位置之前的迭代器不会失效，仍然可以正常使用 // 输出2cout << *it << endl; }输出:
deque头部插入元素：
此时所有的迭代器都失效了，不能正常使用，但是输出结果看起来似乎正确，实际上迭代器已经失
效，这种情况下，不要继续访问已经失效的迭代器。
void Test(){deque<int> dq = { 1, 2, 3, 4, 5 };auto it = dq.begin() + 3;//指向4dq.push_front(10); // 在1之前插入10，头插10// 此时，原来所有的迭代器都失效cout << *it << endl; //it已经失效，不要继续访问}输出：
在deque的尾部插入元素：
一般不会导致已有的迭代器失效，但是如果deque需要重新分配内存的话，所有的迭代器都会失效。
void Test(){deque<int> dq = { 1, 2, 3, 4, 5 };auto it1= dq.begin();//指向1auto it2= dq.begin()+1;//指向2auto it3 = dq.begin()+2;//指向3auto it4 = dq.begin()+3;//指向4auto it5 = dq.begin() + 4;//指向5dq.push_back(10); // 在5之后插入10，尾插10// 此时，已有的迭代器一般不会失效cout << *it1 << " " << *it2 << " " << *it3 << " " <<*it4 << " " << *it5 << endl;}输出：
综上所述，Linux 下的 g++ 编译器同样存在deque迭代器失效的问题，只是在处理迭代器失效后的访问时，可能没有像其他一些编译器那样严格的报错机制，但这并不代表可以忽视迭代器失效问题。正确的做法是始终遵循 C++ 标准，在可能导致迭代器失效的操作后，正确地更新和使用迭代器。
5.2、删除操作导致的迭代器失效问题
【C++标准：】
在deque中间删除元素当从deque中间删除一个元素时，所有指向被删除元素及其之后位置的迭代器都会失效。这是因为删除元素后，deque内部的元素布局发生了变化，后续元素可能会在缓冲区之间移动或者在同一缓冲区内重新排列。
在deque头部删除元素使用pop_front删除deque头部元素会导致所有迭代器失效。因为头部元素的删除会引起内部存储结构的改变，例如缓冲区的调整等。
在deque尾部删除元素一般情况下，使用pop_back删除deque尾部元素不会导致已有迭代器失效。但如果deque在删除元素后需要重新分配内存，所有迭代器会失效。
【VS下的检查机制：】
对于删除元素来说，VS的检查机制也不严格，有些迭代器失效的场景也无法检测。
删除deque中间的元素，此时所有的迭代器失效，访问就会导致错误
void Test(){deque<int> dq = { 1, 2, 3, 4, 5 };auto it = dq.begin() + 1;//指向2auto position = dq.begin() + 3;//指向4dq.erase(position); //删除deque中间的元素，迭代器失效cout << *it << endl;//继续访问it就会报错} 
删除deque的头部元素，根据C++标准，此时所有已有的迭代器失效，无法访问。但是VS并没有检测出迭代器失效的问题。因为这个是一个概率性的情况 当调用 dq.pop_front() 删除 deque 的头部元素时，deque 的容器可能会重新分配内存 但是这里是可能 如果说底层没有重新进行内存分配那么是检查不到失效的 并且 编译器其实并没有那么智能，编译器也只能在特定情况下检查到越界使用或者迭代器失效
void Test(){deque<int> dq{ 1,2,3,4,5 };auto it = dq.begin() + 2; //3dq.pop_front(); //删除头部元素cout << *it << endl; //理论上it已经失效无法访问,但是编译器没有检查出来}输出：
删除尾部元素：
一般不会导致已有的迭代器失效，已有的迭代器仍然可以正常访问
void Test(){deque<int> dq{ 1,2,3,4,5 };auto it1 = dq.begin();//指向1auto it2 = dq.begin() + 1;//指向2auto it3 = dq.begin() + 2;//指向3auto it4 = dq.begin() + 3;//指向4dq.pop_back(); //删除尾部元素// 此时，已有的迭代器一般不会失效cout << *it1 << " " << *it2 << " " << *it3 << " " <<*it4 << " " << endl;}输出：
【Linux下g++的检查机制：】
与插入元素相同，迭代器失效的检查不严格，也不采取措施终止程序，而是继续执行代码，可能会出现看似 “正确” 的结果。但这并不意味着迭代器没有失效，只是 g++ 编译器没有对这种错误进行严格检查。
删除中间元素：
void Test(){deque<int> dq = { 1, 2, 3, 4, 5 };auto it = dq.begin() + 1;//指向2auto position = dq.begin() + 2;//指向3dq.erase(position); //删除deque中间的元素，删除位置之后的迭代器失效,之前的正常使用cout << *it << endl;//it可以正常访问}输出：
删除头部元素：
void Test(){deque<int> dq{ 1,2,3,4,5 };auto it = dq.begin() + 2; //3dq.pop_front(); //删除头部元素cout << *it << endl; //理论上it已经失效无法访问}理论上所有迭代器全都失效，但是仍然可以继续访问并且输出，但这并不意味着迭代器没有失效，只是 g++ 编译器没有对这种错误进行严格检查。
输出：
删除尾部元素：
一般不会导致已有的迭代器失效，已有的迭代器仍然可以正常访问
void Test(){deque<int> dq{ 1,2,3,4,5 };auto it1 = dq.begin();//指向1auto it2 = dq.begin() + 1;//指向2auto it3 = dq.begin() + 2;//指向3auto it4 = dq.begin() + 3;//指向4dq.pop_back(); //删除尾部元素// 此时，已有的迭代器一般不会失效cout << *it1 << " " << *it2 << " " << *it3 << " " <<*it4 << " " << endl;}输出：
5.3、迭代器失效问题的解决
【及时更新迭代器】
插入操作后的更新，当在deque中进行插入操作时，利用insert函数的返回值来更新迭代器。insert函数会返回一个指向新插入元素的迭代器。
void Test(){ std::deque<int> dq = { 1, 2, 3, 4, 5 }; auto it = dq.begin() + 2; //3 auto new_it = dq.insert(it, 6); // 此时new_it指向新插入的元素6 // 如果想访问新插入元素之后的元素，比如原来it指向的元素（现在是新插入元素之后一个） if (new_it + 1 != dq.end()) { cout << *(new_it + 1) << endl; }}输出：
删除操作后的更新，对于deque的删除操作，erase函数会返回一个迭代器，它指向被删除元素之后的元素。可以利用这个返回值来更新迭代器，以确保在删除操作后能够正确地继续访问deque中的元素。
void Test(){ deque<int> dq = { 1, 2, 3, 4, 5 }; auto it = dq.begin() + 2; //3 auto new_it = dq.erase(it); // 此时new_it指向原来元素4，即被删除元素3之后的元素 cout << *new_it << endl;}输出：
【减少循环内的插入 / 删除操作】
尽量避免在循环中频繁地对deque进行插入或删除操作。因为这样很容易导致迭代器失效，并且难以跟踪和更新迭代器。
如果必须在循环中进行插入或删除操作，可以考虑先记录需要插入或删除的位置信息，等循环结束后再统一进行操作。
【谨慎使用迭代器范围】
当使用迭代器范围进行操作时（如在一个范围内插入或删除元素），要特别注意迭代器失效的情况。例如，在deque中，如果要删除一个范围内的元素，要考虑到删除操作后迭代器的变化以及如何正确地更新迭代器来继续后续的操作。
5.4、迭代器使用总结
如上分析迭代器失效问题，不同的编译器检查机制以及处理方式都不同，编译器也没有我们想象中那么智能，只能在特定情况下检查到越界使用或者迭代器失效这种 就是我们有时候看不到现象是很正常的，对于我们来说，我们要掌握迭代器失效的原理，以及如何避免迭代器失效的问题，严格的按照C++标准来规范的使用迭代器。
6、deque的应用场景
6.1、队列和栈的实现
队列：
deque 非常适合用于实现队列（Queue）数据结构。在队列中，元素是按照先进先出（FIFO）的原则进行操作的。push_back操作可以将元素添加到队列的尾部，而pop_front操作则可以从队列的头部移除元素。
例如，在一个任务调度系统中，任务可以被添加到队列的末尾，然后按照顺序从队列头部取出任务进行处理
void Test(){ deque<int> taskQueue; // 将任务添加到队列（模拟） taskQueue.push_back(1); taskQueue.push_back(2); taskQueue.push_back(3); // 从队列头部取出任务并处理（模拟） while (!taskQueue.empty()) { int currentTask = taskQueue.front(); std::cout << "Processing task: " << currentTask << std::endl; taskQueue.pop_front(); }}栈：
对于栈（Stack）数据结构，deque 也能很好地支持。栈遵循后进先出（LIFO）原则，push_back和pop_back操作可以分别用于将元素压入栈和从栈顶弹出元素。
比如在一个表达式求值的程序中，操作数和运算符可以被压入栈中，然后根据运算规则从栈顶弹出元素进行计算。
void Test(){ deque<int> stack; // 将元素压入栈 stack.push_back(1); stack.push_back(2); stack.push_back(3); // 从栈顶弹出元素 while (!stack.empty()) { int topElement = stack.back(); std::cout << "Popping element: " << topElement << std::endl; stack.pop_back(); }}6.2、滑动窗口问题
在一些算法问题中，如滑动窗口算法，deque 可以用于高效地维护窗口内的元素。
例如，在一个给定的数组中，需要找到长度为k的滑动窗口内的最大值。可以使用 deque 来存储窗口内元素的索引，并且保证 deque 的头部始终是窗口内的最大值索引。
vector<int> maxSlidingWindow(const std::vector<int>& nums, int k){ vector<int> result; deque<int> window; for (size_t i = 0; i < nums.size(); ++i) { // 当窗口头部元素不在当前窗口范围内时，弹出头部元素 while (!window.empty() && window.front() <= i - k) { window.pop_front(); } // 保证deque的头部始终是窗口内的最大值索引 while (!window.empty() && nums[window.back()] <= nums[i]) { window.pop_back(); } window.push_back(i); if (i >= k - 1) { result.push_back(nums[window.front()]); } } return result;}int main() { vector<int> nums = { 1, 3, -1, -3, 5, 3, 6, 7 }; int k = 3; vector<int> maxValues = maxSlidingWindow(nums, k); for (int value : maxValues) { cout << value << " "; } cout << std::endl; return 0;}6.3、需要在两端频繁插入和删除元素的场景
在网络编程中，对于接收和发送网络数据包的缓冲区，deque 可以用于存储等待处理的数据包。
新收到的数据包可以使用push_back添加到缓冲区的末尾，而已经处理完的数据包可以使用pop_front从缓冲区的头部移除。这样可以方便地管理数据包的流入和流出，并且在处理过程中，如果需要在缓冲区头部或尾部插入一些控制信息或者元数据，deque 也能够很好地支持。
例如，在一个简单的网络服务器程序中，接收客户端请求并存储在 deque 中，然后从 deque 头部取出请求进行处理，处理后的响应可以添加到另一个 deque 中等待发送回客户端。
7、本文小结
deque同样是STL中十分重要的容器之一，实际应用中很多场景都能看到它的身影，深入理解其特性、操作方法、迭代器机制、内部实现以及应用场景，能够使我们在 C++ 编程中更加得心应手地应对各种数据处理和算法实现的挑战，根据实际需求灵活选择并高效运用 deque，为开发高质量、高性能的程序奠定坚实的基础。
以上关于 deque 的讲解只是我在学习与探索过程中的一些心得分享，自知难免存在局限与浅薄之处。诚如管中窥豹，仅见一斑，若有未详尽或不准确之处，还望各位大佬不吝在评论区赐教点拨，予以斧正，让我得以不断完善知识体系，在编程学习之路上更进一步，感激不尽！
在 C++ 学习的浩瀚星空中，我们都是执着的追光者，每一次成功解析一个晦涩的错误，每一回透彻理解一个精妙的算法，都是我们穿越星际迷雾的胜利。每一行精心编写的代码，都是在这片星空中留下的属于自己的光芒，这段话与诸君共勉，在C++追梦路上共同前行！
创作不易，还请多多互三支持！！！关注博主，为你带来更多优质内容！
