STL总结与常见面试题( 三 ) _STL

运行结果

文章插图

运行结果
dequedeque容器为一个给定类型的元素进行线性处理，像向量一样，它能够快速地随机访问任一个元素，并且能够高效地插入和删除容器的尾部元素。但它又与vector不同，deque支持高效插入和删除容器的头部元素，因此也叫做双端队列。

文章插图

deque的中控器: deque是由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器结构。

文章插图

deque采用一块所谓的map（不是STL的map容器）作为主控。
map是一小块连续空间，其中每个元素(此处称为一个节点，node)都是指针，指向另一段(较大的)连续线性空间，称为缓冲区。
缓冲区才是deque的储存空间主体。

template<class T, class Alloc = alloc, size_t BufSiz = 0>class deque{public :typedef T value_type ;typedef value_type* pointer ;...protected ://元素的指针的指针(pointer of pointer of T)// 其实就是T**，一个二级指针，维护一个二维数组typedef pointer* map_pointer ;protected :map_pointer map ; //指向map,map是块连续空间，其内的每个元素//都是一个指针(称为节点)，指向一块缓冲区size_type map_size ;//map内可容纳多少指针...};

map其实是一个T**，也就是说它是一个指针，所指之物也是一个指针，指向型别为T的一块空间。
方法说明deque构造函数push_back在当前的最后一个元素之后，在 deque 容器的末尾添加一个新元素push_front在 deque 容器的开始位置插入一个新的元素，位于当前的第一个元素之前pop_back删除 deque 容器中的最后一个元素，有效地将容器大小减少一个pop_front删除 deque 容器中的第一个元素，有效地减小其大小emplace_front在 deque 的开头插入一个新的元素，就在其当前的第一个元素之前emplace_back在 deque 的末尾插入一个新的元素，紧跟在当前的最后一个元素之后
测试代码

#include "stdafx.h"#include<iostream>#include<deque> using namespace std;int main(){	deque<int> d;	d.push_back( 11 );//在 deque 容器的末尾添加一个新元素	d.push_back(20);	d.push_back(35);	cout<<"初始化双端队列d："<<endl;	for(int i = 0; i < d.size(); i++)	{cout<<d.at(i)<<"t";	}	cout<<endl;	d.push_front(10);//容器的开始位置插入一个新的元素，位于当前的第一个元素之前	d.push_front(7);	d.push_front(1);cout<<"队列d向前陆续插入10、7、1:"<<endl;	for(int i = 0;i < d.size();i++)	{cout<<d.at(i)<<"t";	}	cout<<endl;	d.pop_back(); //删除 deque 容器中的最后一个元素，有效地将容器大小减少一个	d.pop_front(); //删除 deque 容器中的第一个元素，有效地减小其大小	cout<<"删除deque最后一个和第一个元素后:"<<endl;	for(int i = 0;i < d.size();i++)	{cout<<d.at(i)<<"t";	}	cout<<endl;	return 0;}

forward_list在头文件<forward_list>中，与list类似，区别就是list时双链表，forward_list是单链表，forward_list（单向链表）是序列容器，允许在序列中的任何地方进行恒定的时间插入和擦除操作。在链表的任何位置进行插入/删除操作都非常快。