Deuqe概念

容器deque和vector非常相似，属于序列式容器。都是采用动态数组来管理元素，提供随机存取，并且有着和vector一样的接口。不同的是deque具有首尾两端进行快速插入、删除的能力。

Deque结构

是一种优化了的、对序列两端元素进行添加和删除操作的基本序列容器。它允许较为快速地随机访问，但它不像vector 把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪。向deque 两端添加或删除元素的开销很小。它不需要重新分配空间，所以向末端增加元素比vector 更有效。

deque在实现上主要有以下两点：

1.由一段一段的定量连续空间构成，第一个区块朝某个方向扩展，最后一个区块朝相反方向扩展；

2.管理这些分段的定量连续空间，维护其整体连续的假象，并提供随机存取的接口；

1.Constructors 创建一个新双向队列

语法:

deque();//创建一个空双向队列；

deque( size_type size );// 创建一个大小为size的双向队列

deque( size_type num, const TYPE &val ); //放置num个val的拷贝到队列中

deque( const deque &from );// 从from创建一个内容一样的双向队列

deque(input_iteratorstart,input_iterator end );// start 和 end - 创建一个队列，保存从start到end的元素。

2.Operators 比较和赋值双向队列

//可以使用[]操作符访问双向队列中单个的元素

3.assign() 设置双向队列的值

语法:

void assign( input_iterator start, input_iterator end); //start和end指示的范围为双向队列赋值

void assign( Size num, const TYPE &val );//设置成num个val。

4.at() 返回指定的元素

语法:

reference at( size_type pos ); 返回一个引用，指向双向队列中位置pos上的元素

5.back() 返回最后一个元素

语法:

reference back();//返回一个引用，指向双向队列中最后一个元素

6.begin() 返回指向第一个元素的迭代器

语法:

iterator begin();//返回一个迭代器，指向双向队列的第一个元素

7.clear() 删除所有元素

8.empty() 返回真如果双向队列为空

9.end() 返回指向尾部的迭代器

10.erase() 删除一个元素

语法:

iterator erase( iterator pos ); //删除pos位置上的元素

iterator erase( iterator start, iterator end ); //删除start和end之间的所有元素

//返回指向被删除元素的后一个元素

11.front() 返回第一个元素的引用

12.get_allocator() 返回双向队列的配置器

13.insert() 插入一个元素到双向队列中

语法:

iterator insert( iteratorpos,size_type num, const TYPE &val ); //pos前插入num个val值

void insert( iterator pos, input_iterator start, input_iterator end ); //插入从start到end范围内的元素到pos前面

14.max_size() 返回双向队列能容纳的最大元素个数

15.pop_back() 删除尾部的元素

16.pop_front() 删除头部的元素

17.push_back() 在尾部加入一个元素

18.push_front() 在头部加入一个元素

19.rbegin() 返回指向尾部的逆向迭代器

20.rend() 返回指向头部的逆向迭代器

21.resize() 改变双向队列的大小

22.size() 返回双向队列中元素的个数

23.swap() 和另一个双向队列交换元素

语法：

void swap( deque &target );// 交换target和现双向队列中元素

1.deque::deque

构造一个deque容器对象，根据所使用的构造函数版本初始化它的内容：

Example

#include <iostream>#include <deque>int main (){  unsigned int i;  // constructors used in the same order as described above:  std::deque<int> first;                                // empty deque of ints  std::deque<int> second (4,100);                       // four ints with value 100  std::deque<int> third (second.begin(),second.end());  // iterating through second  std::deque<int> fourth (third);                       // a copy of third  // the iterator constructor can be used to copy arrays:  int myints[] = {16,2,77,29};  std::deque<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );  std::cout << "The contents of fifth are:";  for (std::deque<int>::iterator it = fifth.begin(); it!=fifth.end(); ++it)    std::cout << ' ' << *it;  std::cout << '\n';  return 0;}

Output：

he contents of fifth are: 16 2 77 29 

2. deque::push_back

在当前的最后一个元素之后 ，在deque容器的末尾添加一个新元素。val的内容被复制（或移动）到新的元素。

这有效地增加了一个容器的大小。

void push_back (const value_type& val);void push_back (value_type&& val);

Example

#include <iostream>#include <deque>int main (){  std::deque<int> mydeque;  int myint;  std::cout << "Please enter some integers (enter 0 to end):\n";  do {    std::cin >> myint;    mydeque.push_back (myint);  } while (myint);  std::cout << "mydeque stores " << (int) mydeque.size() << " numbers.\n";  return 0;}

output:

Please enter some integers (enter 0 to end):1 2 3 4 5 0mydeque stores 6 numbers.

3. deque::push_front

在deque容器的开始位置插入一个新的元素，位于当前的第一个元素之前。val的内容被复制（或移动）到插入的元素。

这有效地增加了一个容器的大小。

void push_front (const value_type& val);void push_front (value_type&& val);

Example:

#include <iostream>#include <deque>int main (){  std::deque<int> mydeque (2,100);     // two ints with a value of 100  mydeque.push_front (200);  mydeque.push_front (300);  std::cout << "mydeque contains:";  for (std::deque<int>::iterator it = mydeque.begin(); it != mydeque.end(); ++it)    std::cout << ' ' << *it;  std::cout << '\n';  return 0;}

Output

300 200 100 1001

删除deque容器中的最后一个元素，有效地将容器大小减少一个。

这破坏了被删除的元素。

void pop_back();

Example

#include <iostream>#include <deque>int main (){  std::deque<int> mydeque;  int sum (0);  mydeque.push_back (10);  mydeque.push_back (20);  mydeque.push_back (30);  while (!mydeque.empty())  {    sum+=mydeque.back();    mydeque.pop_back();  }  std::cout << "The elements of mydeque add up to " << sum << '\n';  return 0;}

Output

The elements of mydeque add up to 601

5. deque::pop_front

删除deque容器中的第一个元素，有效地减小其大小。

这破坏了被删除的元素。

void pop_front();

Example

#include <iostream>#include <deque>int main (){  std::deque<int> mydeque;  mydeque.push_back (100);  mydeque.push_back (200);  mydeque.push_back (300);  std::cout << "Popping out the elements in mydeque:";  while (!mydeque.empty())  {    std::cout << ' ' << mydeque.front();    mydeque.pop_front();  }  std::cout << "\nThe final size of mydeque is " << int(mydeque.size()) << '\n';  return 0;}

Output

Popping out the elements in my deque: 100 200 300The final size of mydeque is 0

6. deque::emplace_front

在deque的开头插入一个新的元素，就在其当前的第一个元素之前。这个新的元素是用args作为构建的参数来构建的。

这有效地增加了一个容器的大小。

该元素是通过调用allocator_traits::construct来转换args来创建的。

存在一个类似的成员函数push_front，它可以将现有对象复制或移动到容器中。

template <class... Args>  void emplace_front (Args&&... args);

Example

#include <iostream>#include <deque>int main (){  std::deque<int> mydeque = {10,20,30};  mydeque.emplace_front (111);  mydeque.emplace_front (222);  std::cout << "mydeque contains:";  for (auto& x: mydeque)    std::cout << ' ' << x;  std::cout << '\n';  return 0;}

Output

mydeque contains: 222 111 10 20 30

7. deque::emplace_back

在deque的末尾插入一个新的元素，紧跟在当前的最后一个元素之后。这个新的元素是用args作为构建的参数来构建的。

这有效地增加了一个容器的大小。

该元素是通过调用allocator_traits::construct来转换args来创建的。

存在一个类似的成员函数push_back，它可以将现有对象复制或移动到容器中

template <class... Args>void emplace_back (Args&&... args);

Example

#include <iostream>#include <deque>int main (){  std::deque<int> mydeque = {10,20,30};  mydeque.emplace_back (100);  mydeque.emplace_back (200);  std::cout << "mydeque contains:";  for (auto& x: mydeque)    std::cout << ' ' << x;  std::cout << '\n';  return 0;}

Output

mydeque contains: 10 20 30 100 200