STL-deque双端队列

STL-deque双端队列

• STL-deque双端队列
  • 创建初始化
  • 插入元素
  • 删除元素
  • 遍历容器
  • 函数总览
  • deque和vector
  • 参考资料

deque 是 double-ended queue 的缩写，又称双端队列容器，可以对其两段的数据进行操作，因为它没有capacity属性，因此不会像vector那样”旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”，因此，deque没有必须要提供所谓的空间保留(reserve)功能。

vector是单向开口的连续线性空间，但deque一种双向开口的连续线性空间

deque 容器也擅长在序列头部  和  尾部添加或删除元素

创建初始化

deque()						//创建一个空deque。
deque(int nSize)			//创建一个deque，元素个数为nSize。
deque(int nSize，const T& t) //创建一个deque,元素个数为nSize，且值均为t。
deque (const deque &.)		 //复制构造函数。

#include <deque>
using namespace std;

std::deque<int> d;   		//空 deque 容器
std::deque<int> d(10, 5)   // 创建了一个包含 10 个元素（值都为 5）
    
//拷贝普通数组，创建deque容器
int a[] = { 1,2,3,4,5 };
std::deque<int>d(a, a + 5);
//适用于所有类型的容器
std::array<int, 5>arr{ 11,12,13,14,15 };
std::deque<int>d(arr.begin()+2, arr.end());  //拷贝arr容器中的{13,14,15}

插入元素

void push_front(const T& x):双端队列头部增加一个元素x。
void push_back(const T&. x):双端队列尾部增加一个元素x。

#include <iostream>
#include <deque>
using namespace std;
int main()
{
   // 初始化一个空deque容量
   deque<int> d;
   // 向d容器中的尾部依次添加 1，2,3
   d.push_back(1); //{1}
   d.push_back(2); //{1,2}
   d.push_back(3); //{1,2,3}
   // 向d容器的头部添加 0
   d.push_front(0); //{0,1,2,3}
   // 调用 size() 成员函数输出该容器存储的字符个数。
   cout << "deque size:" << d.size() << endl;

   // 使用迭代器遍历容器
   for (auto i = d.begin(); i < d.end(); i++)
   {
      cout << *i << " ";
   }
   cout << endl;
   return 0;
}

//deque size:4
//0 1 2 3

删除元素

void pop_front() //删除双端队列中最前一个元素。
void pop_back()	//删除双端队列中最后一个元素。
void clear()	//删除双端队列中所有元素。

遍历容器

#include <iostream>
#include <deque>

using namespace std;

int main()
{
   deque<int> d(3); //{0,0,0}
   d.push_back(10);
   d.push_back(20);
   d.push_back(30);
   cout << "original deque: ";
   for (int i = 0; i < d.size(); i++)
   {
      cout << d[i] << ",";
   }
   cout << endl;

   d.push_back(5);
   d.push_back(3);
   d.push_back(1);
   cout << "after push_front(5,3,1): ";
   for (int i = 0; i < d.size(); i++)
   {
      cout << d.at(i) << ",";
   }
   cout << endl;
   d.pop_front();
   d.pop_front();
   d.pop_back();
   cout << "after  pop_front and pop_back ";
   for (int i = 0; i < d.size(); i++)
   {
      cout << d.at(i) << ",";
   }
   cout << endl;
}

// original deque: 0,0,0,10,20,30,
// after push_front(5,3,1): 0,0,0,10,20,30,5,3,1,
// after  pop_front and pop_back 0,10,20,30,5,3,

函数总览

和 vector 相比，额外增加了实现在容器头部添加和删除元素的成员函数，同时删除了 capacity()、reserve() 和 data() 成员函数。

deque和vector

1、deque能够在常数时间在头端插入和删除元素；
2、deque没有容量的观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。

参考资料

https://zhuanlan.zhihu.com/p/583038985