1、顺序容器类型

---- C++标准库定义了6种顺序容器（Sequential Container）类型：

      vector，deque，list，forward_list，array，string

---- 顺序容器为程序员提供了控制元素存储和访问顺序的能力，这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

      对顺序容器内的元素按其位置存储和访问。

---- 标准库中的所有容器都提供了快速顺序访问元素的能力，在以下方面有不同的性能折中：

--1）向容器添加或从容器删除元素的代价。

--2）非顺序访问容器中元素的代价。

vector	可变大小数组，支持快速随机访问。 在尾部之外的位置插入或删除元素可能较慢。
deque	双端队列，支持快速随机访问，在头尾位置插入/删除速度很快。
list	双向链表，只支持双向顺序访问。 在list中的任何位置进行插入/删除操作速度快。
forward_list	单向链表，支持单向顺序访问。插入/删除速度快。
array	固定大小数组
string	与vector相似的容器。

2、deque介绍

---- deque：双端队列，double-ended queue的简写，发音为“deck”。其实现类似于vector容器，支持随机访问。

主要区别在于：从deque对象的起始位置插入和删除元素的时间是固定的，而不像vector中那样是线性时间的。

所以如果多数操作发生在序列的起始和结尾处，则应考虑使用deque数据结构。  

-- 为实现在deque两端执行插入和删除操作的时间为固定的这一目的，deque对象的设计比vector对象更为复杂。

因此，尽管两者都提供对元素的随机访问和在序列中部执行线性时间的插入和删除操作，但vector容器执行这些操作时速度要快些。

核心特性

• ‌双端高效操作‌：与 std::vector 仅能在尾部高效操作不同，deque 在头部和尾部的插入（push_front/push_back）和删除（pop_front/pop_back操作的时间复杂度均为 O(1)O(1)。
• ‌随机访问‌：支持使用下标运算符 [] 或 at()方法以 O(1)的时间复杂度访问任意位置的元素。
• ‌动态扩容‌：不需要像 vector 那样在扩容时移动所有现有元素，也不需要像 list 那样为每个节点存储额外的指针开销。
• ‌非连续内存‌：虽然逻辑上是连续的序列，但物理内存上是由多段连续的缓冲区（buffers）拼接而成的。

底层实现原理

deque 的底层结构通常被描述为‌分段连续数组‌或‌中控数组+数据块‌的结构：

1. ‌中控数组（Map）‌：这是一个指针数组，每个指针指向一个固定大小的连续内存块（Buffer）。
2. ‌数据块（Buffers）‌实际存储元素的地方。当需要扩容时，deque 只需分配新的数据块，并在中控数组中添加指向新块的指针，而无需移动已有数据。
3. ‌迭代器复杂性‌：由于内存不连续，deque 的迭代器比 vector 复杂得多。它通常封装了多个指针（如指向当前缓冲区的起始、结束、当前位置以及中控数组的位置），以便在跨越缓冲区边界时自动跳转。

推荐使用 deque 的场景：‌

1. ‌作为 std::stack 或 std::queue 的底层容器‌：这是 deque 最典型的应用。STL 中的 stack 和 queue 默认使用 deque 作为底层容器，因为它们只需要在两端进行操作，且不需要遍历整个容器。
2. ‌需要在两端频繁插入/删除数据‌：如果业务逻辑涉及“生产者-消费者”模型，或者需要维护一个滑动窗口，deque 比 vector 更高效。
3. ‌需要随机访问但数据量较大且频繁扩容‌：相比 vector，deque 扩容时不需要复制大量旧数据，减少了内存分配的峰值压力。

‌不建议使用 deque 的场景：‌

1. ‌频繁遍历‌：由于内存不连续，deque 的缓存命中率低于 vector，遍历性能稍差。
2. ‌频繁的中间位置插入/删除‌：deque 在中间操作的时间复杂度为 O(n)O(n)，且实现复杂，此时 std::list 或 std::forward_list 可能更合适。
3. ‌对内存连续性有严格要求‌：如果需要将数据直接传递给要求连续内存的 C API（如 memcpy 或某些图形 API），vector 是更好的选择，因为 deque 的地址不连续。

总结来说，std::deque 是一个在随机访问效率和双端操作灵活性之间取得平衡的容器。如果你需要一个既支持快速下标访问，又需要在头部和尾部高效增删元素的序列容器，deque 是最佳选择。

#include <iostream>
#include <deque>
#include <string>

int main() {
    // 1. 声明与初始化
    std::deque<int> d1; // 空 deque
    std::deque<int> d2 = {10, 20, 30}; // 列表初始化

    // 2. 两端插入
    d1.push_back(100);  // 尾部插入: 
    d1.push_front(50);  // 头部插入: [50, 100]
    d1.push_back(200);  // 尾部插入: [50, 100, 200]

    // 3. 访问元素
    std::cout << "Front: " << d1.front() << std::endl; // 输出: 50
    std::cout << "Back: " << d1.back() << std::endl;   // 输出: 200
    std::cout << "Index 1: " << d1 << std::endl;    // 输出: 100 (随机访问)

    // 4. 两端删除
    d1.pop_front(); // 删除头部: [100, 200]
    d1.pop_back();  // 删除尾部: 

    // 5. 遍历
    for (const auto& val : d1) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // 6. 其他常用操作
    std::cout << "Size: " << d1.size() << std::endl;
    std::cout << "Empty? " << std::boolalpha << d1.empty() << std::endl;

    return 0;
}

3、顺序容器适配器

---- 标准库还提供了三种顺序容器适配器（adaptors）：stack，queue，priority_queue

---- stack：后进先出（LIFO）堆栈。

---- queue：先进先出（FIFO）队列。

---- priority_queue：有优先级管理的队列。

适配器是根据原始的容器类型所提供的操作，通过定义新的操作接口，来适应基础的容器类型。

4、向容器中添加元素

4.1  push_back()

---- 所有顺序容器都支持push_back()操作，提供在容器尾部插入一个元素的功能。

---- 调用push_back函数会在容器尾部创建一个新元素，并使容器的长度加1.

4.2  push_front()

---- 除了push_back之外，list（双向链表）和deque（双端队列）容器类型还提供了push_front()实现在容器首部插入新元素的功能。

4.3  insert()

指定的迭代器所指的元素前面插入新元素

4.4 在顺序容器中添加元素的操作

c.push_back(t)	在容器c的尾部添加值为t的元素。返回void类型
c.push_front(t)	在容器c的首部添加值为t的元素。返回void类型 只适用于list和deque容器类型
c.insert(p,t)	在迭代器p所指向的元素前面插入1个值为t的新元素。 返回指向新添加元素的迭代器。
c.insert(p,n,t)	在迭代器p所指向的元素前面插入n个值为t的新元素。 返回void类型
c.insert(p,b,e)	在迭代器p所指向的元素前面插入由迭代器b和e标记的 范围内的元素。返回void类型

举例说明：

#include <iostream>
#include <vector>
#include <list>
#include <string>
using namespace std;
int main()
{
	vector<int> ivec;
	ivec.push_back(10);
	vector<int>::iterator itor = ivec.end();
	ivec.insert(itor,5,20);//尾部插入5个20
	for(itor=ivec.begin();itor!=ivec.end();itor++)
	{
		cout<<*itor<<" ";
	}
	cout<<endl<<"ivec.size() = "<<ivec.size()<<endl;
	
	vector<string> svec;
	svec.insert(svec.begin(),"china");
	svec.insert(svec.begin(),3,"yan");
	string sarray[4]={"dog","cat","pig","bird"};
	svec.insert(svec.end(),sarray,sarray+4);
	vector<string>::iterator stor;
	for(stor=svec.begin();stor!=svec.end();++stor)
	{
		cout<<*stor<<" ";
	}
	cout<<endl<<"svec.size() = "<<svec.size()<<endl;
	
	list<int> ilist;
	ilist.push_back(15);
	ilist.push_front(20);//list and deque can use
	ilist.insert(ilist.begin(),3,8);
	list<int>::iterator iltor;
	for(iltor=ilist.begin();iltor!=ilist.end();++iltor)
	{
		cout<<*iltor<<" ";
	}
	cout<<endl<<"ilist.size() = "<<ilist.size()<<endl;
	system("pause");
	return 0;
}

输出：

 

5、容器的比较

---- 相比较的容器必须具有相同的容器类型，而且其元素类型也必须相同。

例如：vector<int>的容器只能与vector<int>的容器比较，而不能与list<int>或vector<double>类型的容器比较。

---- 容器的比较是基于容器内元素的比较。

--1）如果两个容器具有相同的长度而且所有元素都相等，那么这两个容器就相等；否则，它们就不相等。

--2）如果两个容器的长度不相等，但较短的容器中的所有元素都等于较长容器中对应的元素，则称较短的容器小于另一个容器。

--3）如果两个容器都不是对文的初始子序列，则它们的比较结果取决于所比较的第一个不相等的元素。

例如：

        ivec1: 1 3 5 7 9 12

        ivec2: 0 2 4 6 8 10

        ivec3: 1 3 9

        ivec4: 1 3 5 7

        ivec5: 1 3 5 7 9 12

----   ivec1>ivec2  //true 1>0

----   ivec1<ivec3  //true 5<9

----   ivec1==ivec5 //true

----   ivec1>ivec4 && ivec1!=ivec4