• 进阶C++__STL__stack和queue | deque与priority queue

    目录

    stack容器

     stack 基本概念

    stack 常用接口

    模拟实现stack类

    queue 容器

    queue 基本概念

    queue 常用接口

    模拟实现queue类

    优先级队列 - priority queue

     priority_queue 的概念

    优先级队列的使用

    模拟实现priority_queue类

    双端队列 - double ended queue

    deque容器基本概念

    deque构造函数

    deque赋值操作

    deque大小操作

    deque 插入和删除

    deque 数据存取

    deque 排序

             deque，stack 和 queue 的底层默认容器

    deque 的缺陷

    stack容器

     stack 基本概念

    1. 栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作。
    2. 进行数据插入的删除和操作的一端，称为 栈顶 。另一端则称为 栈底 。
    3. stack是一种先进后出(First In Last Out,FILO)的数据结构，它只有一个出口栈中只有顶端的元素才可以被外界使用，因此栈不允许有遍历行为
    • 栈中进入数据称为 — 入栈 push
    • 栈中弹出数据称为 — 出栈 pop

    文档介绍：stack - C++ Reference 

    • stack 是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行 元素的插入与提取操作。
    • stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定 的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
    • 标准容器 vector、deque、list 均符合这些需求，默认情况下，如果没有为 stack 指定特定的底层容器， 默认情况下使用 deque。
       

    stack 常用接口

    功能描述：栈容器常用的对外接口

    构造函数：

    • stack stk; //stack采用模板类实现， stack对象的默认构造形式
    • stack(const stack &stk); //拷贝构造函数

    赋值操作：

    • stack& operator=(const stack &stk); //重载等号操作符

    数据存取：

    • push(elem); //向栈顶添加元素
    • pop(); //从栈顶移除第一个元素
    • top(); //返回栈顶元素

    大小操作：

    • empty(); //判断堆栈是否为空
    • size(); //返回栈的大小

     示例：

    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. //栈容器常用接口
    7. void test01()
    8. {
    9. 	//创建栈容器 栈容器必须符合先进后出
    10. 	stack<int> s;
    11.  
    12. 	//向栈中添加元素，叫做 压栈 入栈
    13. 	s.push(10);
    14. 	s.push(20);
    15. 	s.push(30);
    16.  
    17. 	while (!s.empty()) {
    18. 		//输出栈顶元素
    19. 		cout << "栈顶元素为： " << s.top() << endl;
    20. 		//弹出栈顶元素
    21. 		s.pop();
    22. 	}
    23. 	cout << "栈的大小为：" << s.size() << endl;
    24.  
    25. }
    26.  
    27. int main() {
    28.  
    29. 	test01();
    30.  
    31. 	system("pause");
    32.  
    33. 	return 0;
    34. }

    输出：

    栈顶元素为： 30
    栈顶元素为： 20
    栈顶元素为： 10
    栈的大小为：0

    模拟实现stack类

    函数接口

    1.   #include
    2.  
    3.   template<class T, class Con = deque>
    4.  
    5.   class stack
    6.  
    7.   {
    8.  
    9.   public:
    10.  
    11.     stack();
    12.  
    13.     void push(const T& x);
    14.  
    15.     void pop();
    16.  
    17.     T& top();
    18.  
    19.     const T& top()const;
    20.  
    21.     size_t size()const;
    22.  
    23.     bool empty()const;
    24.  
    25.   private:
    26.  
    27.     Con _c;
    28.  
    29.   };

    模拟实现

    1. /*
    3. *思路：
    5. * 1. stack和queue的模拟实现思路一样，都是通过容器适配而成
    7. * 2. 容器的模板参数Con给出容器deque作为底层的默认容器(使用的过程中也可以自己指定容器)
    9. * 3. stack和queue的方式实现在底层都是转为调用适配容器，只要容器能够满足所有的转调用操作，都可以充当适配   容器
    11. * 4. 由于stack和queue是通过其他容器适配而成，所以stack和queue称为容器适配器
    13. */
    14. #include
    15.  
    16.   template<class T, class Con = deque>
    17.  
    18.   class stack
    19.   {
    20.   public:
    21.  
    22.     stack()
    23.     {}
    24.     void push(const T& x)
    25.     {
    26.       _c.push_back(x);
    27.     }
    28.  
    29.     void pop()
    30.     {
    31.       _c.pop_back();
    32.     }
    33.  
    34.     T& top()
    35.     {
    36.       return _c.back();
    37.     }
    38.  
    39.     const T& top()const
    40.     {
    41.       return _c.back();
    42.     }
    43.  
    44.     size_t size()const
    45.     {
    46.       return _c.size();
    47.     }
    48.  
    49.     bool empty()const
    50.  
    51.     {
    52.       return _c.empty();
    53.     }
    54.  
    55.   private:
    56.     Con _c;
    57.  
    58.   };

    queue 容器

    queue 基本概念

    概念：Queue是一种先进先出(First In First Out,FIFO)的数据结构，它有两个出口

    队列容器允许从一端新增元素，从另一端移除元素

    队列中只有队头和队尾才可以被外界使用，因此队列不允许有遍历行为

    队列中进数据称为 — 入队 push

    队列中出数据称为 — 出队 pop

    文档介绍：queue - C++ Reference

    • 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端 提取元素。
    • 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的 成员函数来访问其元素。元素从队尾入队列，从队头出队列。
    • 标准容器类 deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标 准容器 deque。


     

    queue 常用接口

    功能描述：栈容器常用的对外接口

    构造函数：

    • queue que; //queue采用模板类实现，queue对象的默认构造形式
    • queue(const queue &que); //拷贝构造函数

    赋值操作：

    • queue& operator=(const queue &que); //重载等号操作符

    数据存取：

    • push(elem); //往队尾添加元素
    • pop(); //从队头移除第一个元素
    • back(); //返回最后一个元素
    • front(); //返回第一个元素

    大小操作：

    • empty(); //判断堆栈是否为空
    • size(); //返回栈的大小
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5. #include 
    6.  
    7. class Person
    8. {
    9. public:
    10. 	Person(string name, int age)
    11. 	{
    12. 		this->m_Name = name;
    13. 		this->m_Age = age;
    14. 	}
    15.  
    16. 	string m_Name;
    17. 	int m_Age;
    18. };
    19.  
    20. void test01() {
    21.  
    22. 	//创建队列
    23. 	queue q;
    24.  
    25. 	//准备数据
    26. 	Person p1("唐僧", 30);
    27. 	Person p2("孙悟空", 1000);
    28. 	Person p3("猪八戒", 900);
    29. 	Person p4("沙僧", 800);
    30.  
    31. 	//向队列中添加元素  入队操作
    32. 	q.push(p1);
    33. 	q.push(p2);
    34. 	q.push(p3);
    35. 	q.push(p4);
    36.  
    37. 	//队列不提供迭代器，更不支持随机访问	
    38. 	while (!q.empty()) {
    39. 		//输出队头元素
    40. 		cout << "队头元素-- 姓名： " << q.front().m_Name 
    41.               << " 年龄： "<< q.front().m_Age << endl;
    42.         
    43. 		cout << "队尾元素-- 姓名： " << q.back().m_Name  
    44.               << " 年龄： " << q.back().m_Age << endl;
    45.         
    46. 		cout << endl;
    47. 		//弹出队头元素
    48. 		q.pop();
    49. 	}
    50.  
    51. 	cout << "队列大小为：" << q.size() << endl;
    52. }
    53.  
    54. int main() {
    55.  
    56. 	test01();
    57.  
    58. 	system("pause");
    59.  
    60. 	return 0;
    61. }

    输出：

    队头元素-- 姓名： 唐僧 年龄： 30
    队尾元素-- 姓名： 沙僧 年龄： 800

    队头元素-- 姓名： 孙悟空 年龄： 1000
    队尾元素-- 姓名： 沙僧 年龄： 800

    队头元素-- 姓名： 猪八戒 年龄： 900
    队尾元素-- 姓名： 沙僧 年龄： 800

    队头元素-- 姓名： 沙僧 年龄： 800
    队尾元素-- 姓名： 沙僧 年龄： 800

    队列大小为：0

    模拟实现queue类

    函数接口

    1.   template<class T, class Con = deque>
    2.  
    3.   class queue
    4.  
    5.   {
    6.  
    7.   public:
    8.  
    9.     queue();
    10.  
    11.     void push(const T& x);
    12.  
    13.     void pop();
    14.  
    15.     T& back();
    16.  
    17.     const T& back()const;
    18.  
    19.     T& front();
    20.  
    21.     const T& front()const;
    22.  
    23.     size_t size()const;
    24.  
    25.     bool empty()const;
    26.  
    27.   private:
    28.  
    29.     Con _c;
    30.  
    31.   };

    模拟实现

    1. /*
    3. *思路：
    5. * 1. stack和queue的模拟实现思路一样，都是通过容器适配而成
    7. * 2. 容器的模板参数Con给出容器deque作为底层的默认容器(使用的过程中也可以自己指定容器)
    9. * 3. stack和queue的方式实现在底层都是转为调用适配容器，只要容器能够满足所有的转调用操作，都可以充当适配   容器
    11. * 4. 由于stack和queue是通过其他容器适配而成，所以stack和queue称为容器适配器
    13. */
    14. #include
    15. template<class T, class Con = deque>
    16.  
    17.   class queue
    18.  
    19.   {
    20.  
    21.   public:
    22.  
    23.     queue()
    24.     {}
    25.  
    26.     void push(const T& x)
    27.     {
    28.       _c.push_back(x);
    29.     }
    30.  
    31.     void pop()
    32.     {
    33.       _c.pop_front();
    34.     }
    35.  
    36.     T& back()
    37.     {
    38.       return _c.back();
    39.     }
    40.  
    41.     const T& back()const
    42.     {
    43.       return _c.back();
    44.     }
    45.  
    46.     T& front()
    47.     {
    48.       return _c.front();
    49.     }
    50.  
    51.     const T& front()const
    52.     {
    53.       return _c.front();
    54.     }
    55.  
    56.     size_t size()const
    57.     {
    58.       return _c.size();
    59.     }
    60.  
    61.     bool empty()const
    62.     {
    63.       return _c.empty();
    64.     }
    65.  
    66.   private:
    67.  
    68.     Con _c;
    69.  
    70.   };

    优先级队列 - priority queue

     priority_queue 的概念

    优先级队列（priority_queue）其实，不满足先进先出的条件，更像是数据类型中的“堆”。优先级队列每次出队的元素是队列中优先级最高的那个元素，而不是队首的元素。这个优先级可以通过元素的大小等进行定义。比如定义元素越大优先级越高，那么每次出队，都是将当前队列中最大的那个元素出队

    文档介绍：priority_queue - C++ Reference

    • 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
    • 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素（优先队列中位于顶部的元素）。
    • 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特 定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
    • 标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue 类实例化指 定容器类，则使用 vector。
    • 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 来自动完成此操作。


     

    优先级队列的使用

    优先级队列默认使用 vector 作为其底层存储数据的容器，

    在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因为 priority_queue 就是堆。

    所有需要用到堆的地方，都可以考虑使用 priority_queue。

    值得注意的是，priority_queue 默认为大根堆。

    优先级队列默认大的优先级高，传的是 less 仿函数，底层是一个大堆；

    如果想控制小的优先级高，需手动传 greater 仿函数，其底层是一个小堆。
     

    • empty()：检测容器是否为空
    • size()：返回容器中有效元素个数
    • front()：返回容器中第一个元素的引用
    • push_back()：在容器尾部插入元素
    • pop_back()：删除容器尾部元素

    1. #include 
    2. #include 
    3. #include   // greater算法的头文件
    4. using namespace std;
    5.  
    6. void test_priority_queue() 
    7. {
    8.     priority_queue<int, vector<int>, greater<int> > pQ;
    9.   
    10.     pQ.push(2);
    11.     pQ.push(5);
    12.     pQ.push(1);
    13.     pQ.push(6);
    14.     pQ.push(8);
    15.     while (!pQ.empty()) {
    16.         cout << pQ.top() << " ";
    17.         pQ.pop();
    18.     }
    19.     cout << endl;
    20.  
    21.  
    22.     priority_queue<int> pQ2;
    23.  //默认是用 vector 存储的，注意这里没有明确指定 less 还是 greater，所以默认为 less。
    24.     pQ2.push(2);
    25.     pQ2.push(5);
    26.     pQ2.push(1);
    27.     pQ2.push(6);
    28.     pQ2.push(8);
    29.     while (!pQ2.empty()) {
    30.         cout << pQ2.top() << " ";
    31.         pQ2.pop();
    32.     }
    33.     cout << endl;
    34. }
    35.  
    36.  
    37.  
    38. int main() {
    39.     test_priority_queue();
    40.     return 0;
    41. }

    输出：

    1 2 5 6 8
    8 6 5 2 1

    默认是用 vector 存储的，注意这里没有明确指定 less 还是 greater，所以默认为 less。

    我们在定义优先级队列时主动去传 greater 即可令该优先级队列以小的优先级高。

    模拟实现priority_queue类

    函数接口

    1. namespace bit
    2.  
    3. {
    4.  
    5.   #include
    6.  
    7.   #include
    8.  
    9.   template <class T, class Container = vector, class Compare = less >
    10.  
    11.   class priority_queue
    12.  
    13.   {
    14.  
    15.   public:
    16.  
    17.     priority_queue();
    18.  
    19.     template <class InputIterator>
    20.  
    21.     priority_queue(InputIterator first, InputIterator last);
    22.  
    23.     bool empty() const;
    24.  
    25.     size_t size() const;
    26.  
    27.     T& top() const;
    28.  
    29.     void push(const T& x);
    30.  
    31.     void pop();
    32.  
    33.   private:
    34.  
    35.     Container c;
    36.  
    37.     Compare comp;
    38.  
    39.   };
    40.  
    41. };

    模拟实现

    1. namespace bit
    2.  
    3. {
    4.  
    5.   //函数对象 less
    6.   template<class T>
    7.  
    8.   struct less
    9.   {
    10.     bool operator()(const T& left, const T& right)
    11.     { 
    12.       return left < right; 
    13.     }
    14.   };
    15.  
    16.   //函数对象 greater
    17.   template<class T>
    18.  
    19.   struct greater
    20.   {
    21.     bool operator()(const T& left, const T& right)
    22.     { 
    23.       return left > right; 
    24.     }
    25.   };
    26.    
    27.  
    28. namespace bit
    29. {
    30.  
    31.   //函数对象 less
    32.   template<class T>
    33.   struct less
    34.   {
    35.     bool operator()(const T& left, const T& right)
    36.     { 
    37.       return left < right; 
    38.     }
    39.   };
    40.  
    41.  
    42.   //函数对象 greater
    43.   template<class T>
    44.   struct greater
    45.   {
    46.     bool operator()(const T& left, const T& right)
    47.     { 
    48.       return left > right; 
    49.     }
    50.   };
    51.  
    52.    
    53.  
    54.   template <class T, class Container = std::vector, class Compare = less >
    55.   class priority_queue
    56.   {
    57.   public:
    58.  
    59.     //创建空的优先级队列
    60.     priority_queue():c()
    61.     {}
    62.  
    63.     template <class InputIterator>
    64.     priority_queue(InputIterator first, InputIterator last)
    65.       :c(first, last)
    66.     {
    67.       //将c中的元素调整为堆的结构，默认为大堆
    68.       int count = c.size();
    69.       int root = ((count - 2) >> 1);
    70.       for (; root >= 0; root--)
    71.        AdjustDown(root);
    72.     }
    73.  
    74.     bool empty() const
    75.     {
    76.       return c.empty();
    77.     }
    78.  
    79.     size_t size() const
    80.     {
    81.       return c.size();
    82.     }
    83.  
    84.     // 堆顶元素不允许修改，因为：堆顶元素修改可以会破坏堆的特性
    85.  
    86.     const T& top() const
    87.     {
    88.       return c.front();
    89.     }
    90.  
    91.     void push(const T& x)
    92.     {
    93.       c.push_back(x);
    94.       //push_heap(c.begin(), c.end(), comp);
    95.       AdjustUp(c.size() - 1);
    96.     }
    97.  
    98.     void pop()
    99.     {
    100.       if (empty())
    101.        return;
    102.       std:swap(c.front(), c.back());
    103.       c.pop_back();
    104.       AdjustDown(0);
    105.     }
    106.  
    107.   private:
    108.  
    109.     //向上调整
    110.  
    111.     void AdjustUp(int child)
    112.     {
    113.  
    114.       int parent = ((child - 1) >> 1);
    115.       while (child)
    116.       {
    117.         if (Com(c[parent], c[child]))
    118.         {
    119.           std::swap(c[child], c[parent]);
    120.           child = parent;
    121.           parent = ((child - 1) >> 1);
    122.        }
    123.         else  return;
    124.  
    125.       }
    126.  
    127.     }
    128.  
    129.      
    130.  
    131.     //向下调整
    132.     void AdjustDown(int parent)
    133.     {
    134.       int child = parent * 2 + 1;
    135.       while (child < c.size())
    136.       {
    137.  
    138.         // 找以parent为根的较大的孩子
    139.         if (child + 1 < c.size() && Com(c[child], c[child+1]))
    140.         child += 1;
    141.  
    142.         // 检测双亲是否满足情况
    143.         if (Com(c[parent], c[child]))
    144.         {
    145.           std::swap(c[child], c[parent]);
    146.           parent = child;
    147.           child = parent * 2 + 1;
    148.        }
    149.        else  return;
    150.  
    151.       }
    152.  
    153.     }
    154.  
    155.   private:
    156.  
    157.     Container c;
    158.  
    159. Compare Com;
    160.   };
    161.  
    162. };

    双端队列 - double ended queue

    deque容器基本概念

    功能：

    • 双端数组，可以对头端进行插入删除操作

    deque与vector区别：

    • deque 可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)，比vector快,

    • vector访问元素时的速度会比deque快,这和两者内部实现有关

    deque内部工作原理:

    deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据

    中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间

    • deque容器的迭代器也是支持随机访问的

    deque构造函数

    • deque deqT; //默认构造形式
    • deque(beg, end); //构造函数将[beg, end)区间中的元素拷贝给本身。
    • deque(n, elem); //构造函数将n个elem拷贝给本身。
    • deque(const deque &deq); //拷贝构造函数

    注意：

    1. void printDeque(deque<int>& d) 
    2. {
    3. 	for (deque<int>::iterator it = d.begin(); it != d.end(); it++) {
    4. 		cout << *it << " ";
    5.  
    6. 	}
    7. 	cout << endl;
    8. }
    9. 无const，迭代器用iterator
    10.  
    11. void printDeque(const deque<int>& d) 
    12. {
    13. 	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
    14. 		cout << *it << " ";
    15.  
    16. 	}
    17. 	cout << endl;
    18. }
    19. 有const限定用cosnt_iterator

    示例：

    1. #include 
    2.  
    3. using namespace std;
    4. #include 
    5.  
    6. void printDeque(const deque<int>& d) 
    7. {
    8. 	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
    9. 		cout << *it << " ";
    10.  
    11. 	}
    12. 	cout << endl;
    13. }
    14. //deque构造
    15. void test01() {
    16.  
    17. 	deque<int> d1; //无参构造函数
    18. 	for (int i = 0; i < 10; i++)
    19. 	{
    20. 		d1.push_back(i);
    21. 	}
    22. 	printDeque(d1);
    23. 	deque<int> d2(d1.begin(),d1.end());
    24. 	printDeque(d2);
    25.  
    26. 	deque<int>d3(10,100);
    27. 	printDeque(d3);
    28.  
    29. 	deque<int>d4 = d3;
    30. 	printDeque(d4);
    31. }
    32.  
    33. int main() {
    34.  
    35. 	test01();
    36.  
    37. 	system("pause");
    38.  
    39. 	return 0;
    40. }

    输出：

    0 1 2 3 4 5 6 7 8 9
    0 1 2 3 4 5 6 7 8 9
    100 100 100 100 100 100 100 100 100 100
    100 100 100 100 100 100 100 100 100 100

    deque容器和vector容器的构造方式几乎一致，灵活使用即可

    deque赋值操作

    • deque& operator=(const deque &deq); //重载等号操作符

    • assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。

    • assign(n, elem); //将n个elem拷贝赋值给本身。

    1. #include 
    2.  
    3. using namespace std;
    4. #include 
    5.  
    6. void printDeque(const deque<int>& d) 
    7. {
    8. 	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
    9. 		cout << *it << " ";
    10.  
    11. 	}
    12. 	cout << endl;
    13. }
    14. //赋值操作
    15. void test01()
    16. {
    17. 	deque<int> d1;
    18. 	for (int i = 0; i < 10; i++)
    19. 	{
    20. 		d1.push_back(i);
    21. 	}
    22. 	printDeque(d1);
    23.  
    24. 	deque<int>d2;
    25. 	d2 = d1;
    26. 	printDeque(d2);
    27.  
    28. 	deque<int>d3;
    29. 	d3.assign(d1.begin(), d1.end());
    30. 	printDeque(d3);
    31.  
    32. 	deque<int>d4;
    33. 	d4.assign(10, 100);
    34. 	printDeque(d4);
    35.  
    36. }
    37.  
    38. int main() {
    39.  
    40. 	test01();
    41.  
    42. 	system("pause");
    43.  
    44. 	return 0;
    45. }

    输出：

    0 1 2 3 4 5 6 7 8 9
    0 1 2 3 4 5 6 7 8 9
    0 1 2 3 4 5 6 7 8 9
    100 100 100 100 100 100 100 100 100 100

    deque大小操作

    • deque.empty(); //判断容器是否为空

    • deque.size(); //返回容器中元素的个数

    • deque.resize(num); //重新指定容器的长度为num,若容器变长，则以默认值填充新位置。

      ​ //如果容器变短，则末尾超出容器长度的元素被删除。

    • deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置。

      ​ //如果容器变短，则末尾超出容器长度的元素被删除。

      ​

    • deque没有容量的概念

    示例：

    1. #include 
    2.  
    3. using namespace std;
    4. #include 
    5.  
    6. void printDeque(const deque<int>& d) 
    7. {
    8. 	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
    9. 		cout << *it << " ";
    10.  
    11. 	}
    12. 	cout << endl;
    13. }
    14.  
    15. //大小操作
    16. void test01()
    17. {
    18. 	deque<int> d1;
    19. 	for (int i = 0; i < 10; i++)
    20. 	{
    21. 		d1.push_back(i);
    22. 	}
    23. 	printDeque(d1);
    24.  
    25. 	//判断容器是否为空
    26. 	if (d1.empty()) {
    27. 		cout << "d1为空!" << endl;
    28. 	}
    29. 	else {
    30. 		cout << "d1不为空!" << endl;
    31. 		//统计大小
    32. 		cout << "d1的大小为：" << d1.size() << endl;
    33. 	}
    34.  
    35. 	//重新指定大小
    36. 	d1.resize(15, 1);
    37. 	printDeque(d1);
    38.  
    39. 	d1.resize(5);
    40. 	printDeque(d1);
    41. }
    42.  
    43. int main() {
    44.  
    45. 	test01();
    46.  
    47. 	system("pause");
    48.  
    49. 	return 0;
    50. }

    输出：

    0 1 2 3 4 5 6 7 8 9
    d1不为空!
    d1的大小为：10
    0 1 2 3 4 5 6 7 8 9 1 1 1 1 1
    0 1 2 3 4

    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位置的数据，返回下一个数据的位置。

      ​

      ​

    示例：

    1. #include 
    2.  
    3. using namespace std;
    4. #include 
    5.  
    6. void printDeque(const deque<int>& d) 
    7. {
    8. 	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
    9. 		cout << *it << " ";
    10.  
    11. 	}
    12. 	cout << endl;
    13. }
    14. //两端操作
    15. void test01()
    16. {
    17. 	deque<int> d;
    18. 	//尾插
    19. 	d.push_back(10);
    20. 	d.push_back(20);
    21. 	//头插
    22. 	d.push_front(100);
    23. 	d.push_front(200);
    24.  
    25. 	printDeque(d);
    26.  
    27. 	//尾删
    28. 	d.pop_back();
    29. 	//头删
    30. 	d.pop_front();
    31. 	printDeque(d);
    32. 	cout<
    33. }
    34.  
    35. //插入
    36. void test02()
    37. {
    38. 	deque<int> d;
    39. 	d.push_back(10);
    40. 	d.push_back(20);
    41. 	d.push_front(100);
    42. 	d.push_front(200);
    43. 	printDeque(d);
    44.  
    45. 	d.insert(d.begin(), 1000);
    46. 	printDeque(d);
    47.  
    48. 	d.insert(d.begin(), 2,10000);
    49. 	printDeque(d);
    50.  
    51. 	deque<int>d2;
    52. 	d2.push_back(1);
    53. 	d2.push_back(2);
    54. 	d2.push_back(3);
    55.  
    56. 	d.insert(d.begin(), d2.begin(), d2.end());
    57. 	printDeque(d);
    58. 	cout<
    59.  
    60. }
    61.  
    62. //删除
    63. void test03()
    64. {
    65. 	deque<int> d;
    66. 	d.push_back(10);
    67. 	d.push_back(20);
    68. 	d.push_front(100);
    69. 	d.push_front(200);
    70. 	printDeque(d);
    71.  
    72. 	d.erase(d.begin());
    73. 	printDeque(d);
    74.  
    75. 	//d.erase(d.begin(), d.end());
    76. 	d.clear();
    77. 	printDeque(d);
    78.  
    79. }
    80.  
    81. int main() {
    82.  
    83. 	test01();
    84.  
    85. 	test02();
    86.  
    87.     test03();
    88.     
    89. 	system("pause");
    90.  
    91. 	return 0;
    92. }
    93.

    输出：

    200 100 10 20
    100 10

    200 100 10 20
    1000 200 100 10 20
    10000 10000 1000 200 100 10 20
    1 2 3 10000 10000 1000 200 100 10 20

    200 100 10 20
    100 10 20

    （空字符串）
     

    deque 数据存取

    • at(int idx); //返回索引idx所指的数据
    • operator[]; //返回索引idx所指的数据
    • front(); //返回容器中第一个数据元素
    • back(); //返回容器中最后一个数据元素

    除了用迭代器获取deque容器中元素，[ ]和at也可以

    示例：

    1. #include 
    2.  
    3. using namespace std;
    4. #include 
    5.  
    6. void printDeque(const deque<int>& d) 
    7. {
    8. 	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
    9. 		cout << *it << " ";
    10.  
    11. 	}
    12. 	cout << endl;
    13. }
    14.  
    15. //数据存取
    16. void test01()
    17. {
    18.  
    19. 	deque<int> d;
    20. 	d.push_back(10);
    21. 	d.push_back(20);
    22. 	d.push_front(100);
    23. 	d.push_front(200);
    24.  
    25. 	for (int i = 0; i < d.size(); i++) {
    26. 		cout << d[i] << " ";
    27. 	}
    28. 	cout << endl;
    29.  
    30.  
    31. 	for (int i = 0; i < d.size(); i++) {
    32. 		cout << d.at(i) << " ";
    33. 	}
    34. 	cout << endl;
    35.  
    36. 	cout << "front:" << d.front() << endl;
    37.  
    38. 	cout << "back:" << d.back() << endl;
    39.  
    40. }
    41.  
    42. int main() {
    43.  
    44. 	test01();
    45.  
    46. 	system("pause");
    47.  
    48. 	return 0;
    49. }
    50.

    输出：

    200 100 10 20
    200 100 10 20
    front:200
    back:20

    deque 排序

    • sort(iterator beg, iterator end) //对beg和end区间内元素进行排序

    示例：

    1. #include 
    2.  
    3. using namespace std;
    4. #include 
    5. #include 
    6.  
    7. void printDeque(const deque<int>& d) 
    8. {
    9. 	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
    10. 		cout << *it << " ";
    11.  
    12. 	}
    13. 	cout << endl;
    14. }
    15.  
    16. void test01()
    17. {
    18.  
    19. 	deque<int> d;
    20. 	d.push_back(10);
    21. 	d.push_back(20);
    22. 	d.push_front(100);
    23. 	d.push_front(200);
    24. 	printDeque(d);
    25. 	
    26. 	sort(d.begin(), d.end());
    27. 	printDeque(d);
    28. 	
    29. 	sort(d.begin(), d.end(),greater<int>());
    30. 	printDeque(d);
    31. }
    32.  
    33. int main() {
    34.  
    35. 	test01();
    36.  
    37. 	system("pause");
    38.  
    39. 	return 0;
    40. }

    输出：

    200 100 10 20
    10 20 100 200
    200 100 20 10

    deque，stack 和 queue 的底层默认容器

     在 stack 和 queue 的实现上，是选择 deque 作为底层默认容器的。

    stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为stack 的底层容器，比如 vector 和 list 都可以； queue是先进先出的特殊线性数据结构，只要具有 push_back和pop_front 操作的线性结构，都可以作为 queue 的底层容器，比如 list 。但是 STL 中对 stack 和 queue默认选择 deque 作为其底层容器，主要是因为：
    1. stack 和 queue 不需要遍历（因此 stack 和 queue 没有迭代器），只需要在固定的一端或者两端进行操作。
    2. 在 stack 中元素增长时，deque 比 vector 的效率高（扩容时不需要搬移大量数据）；queue  中的元素增长时，deque 不仅效率高，而且内存使用率高。 结合了 deque 的优点，而完美的避开了其缺陷。
       

    deque 的缺陷

    deque 有一个致命缺陷：不适合遍历，因为在遍历时， deque 的迭代器要频繁的去检测其是否移动到 某段小空间的边界，导致效率低下 ，而序列式场景中，可能需要经常遍历，因此 在实际中，需要线性结构 时，大多数情况下优先考虑 vector 和 list ， deque 的应用并不多，而 目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构

  • 相关阅读:
    【大型电商项目开发】性能压测-优化-中间件对性能的影响-40
    C# 与 C/C++ 的交互
    【分享】在集简云搭建流程，日期格式需要调整怎么办？
    NX上配置TLD的环境---对opencv的版本没有要求
    Vue rules校验规则详解
    【CI/CD】Rancher CD过程--20230906
    GCC
    互联网快讯：天猫好房正式入驻六安；搜狗又一业务关停
    k8s 基础
    bootz启动 Linux内核过程中涉及的 do_bootm_states 函数
  • 原文地址：https://blog.csdn.net/qq_61386381/article/details/125937428