deque
deque容器为一个给定类型的元素进行线性处理,像向量一样,它能够快速地随机访问任一个元素,并且能够高效地插入和删除容器的尾部元素。但它又与vector不同,deque支持高效插入和删除容器的头部元素,因此也叫做双端队列。
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5SM4gzM1ITO2QzNyMWM3cTYhVTY0MjNkNGN1EmZ5IDO28CX5d2bs92Yl1iclB3bsVmdlR2LcNWaw9CXt92Yu4GZjlGbh5yYjV3Lc9CX6MHc0RHaiojIsJye.png)
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
在头文件中,与list类似,区别就是list时双链表,forward_list是单链表,forward_list(单向链表)是序列容器,允许在序列中的任何地方进行恒定的时间插入和擦除操作。在链表的任何位置进行插入/删除操作都非常快。
forward_list的特点:
forward_list只提供钱箱迭代器,因此不支持反向迭代器,比如rbegin()等成员函数。
forward_list不提供size()成员函数。
forward_list没有指向最末元素的锚点,因此不提供back()、push_back()和pop_back()。
forward_list不提供随机访问,这一点跟list相同。
插入和删除元素不会造成“指向至其他元素”的指针,引用和迭代器失效。
容器成员函数总结就不写了,太多影响阅读,感兴趣小伙伴戳
http://www.cplusplus.com/reference/stl/list
list双向链表,是序列容器,允许在序列中的任何地方进行常数时间插入和擦除操作,并在两个方向上进行迭代,可以高效地进行插入删除元素。
使用list容器之前必须加上头文件:#include;
list容器的底层实现:
和 array、vector 这些容器迭代器的实现方式不同,由于 list 容器的元素并不是连续存储的,所以该容器迭代器中,必须包含一个可以指向 list 容器的指针,并且该指针还可以借助重载的 *、++、--、==、!= 等运算符,实现迭代器正确的递增、递减、取值等操作。
template<tyepname T,...>
struct __list_iterator{
__list_node<T>* node;
//...
//重载 == 运算符
bool operator==(const __list_iterator& x){return node == x.node;}
//重载 != 运算符
bool operator!=(const __list_iterator& x){return node != x.node;}
//重载 * 运算符,返回引用类型
T* operator *() const {return *(node).myval;}
//重载前置 ++ 运算符
__list_iterator<T>& operator ++(){
node = (*node).next;
return *this;
}
//重载后置 ++ 运算符
__list_iterator<T>& operator ++(int){
__list_iterator<T> tmp = *this;
++(*this);
return tmp;
}
//重载前置 -- 运算符
__list_iterator<T>& operator--(){
node = (*node).prev;
return *this;
}
//重载后置 -- 运算符
__list_iterator<T> operator--(int){
__list_iterator<T> tmp = *this;
--(*this);
return tmp;
}
//...
}
stack
stack底层一般用list或deque实现,封闭头部即可,不用vector的原因应该是容量大小有限制,扩容耗时
底层用deque实现:
//deque<T> >中间有个空格是为了兼容较老的版本
template <class T, class Sequence = deque<T> >
class stack {
// 以㆘的 __STL_NULL_TMPL_ARGS 会开展为 <>
friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c; // 底层容器
public:
// 以㆘完全利用 Sequence c 的操作,完成 stack 的操作。
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() { return c.back(); }
const_reference top() const { return c.back(); }
// deque 是两头可进出,stack 是末端进,末端出(所以后进者先出)。
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_back(); }
};
template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
return x.c == y.c;
}
template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
return x.c < y.c;
}
底层用list实现
#include<stack>
#include<list>
#include<algorithm>
#include <iostream>
using namespace std;
int main(){
stack<int, list<int>> istack;
istack.push(1);
istack.push(3);
istack.push(5);
cout << istack.size() << endl; //3
cout << istack.top() << endl;//5
istack.pop();
cout << istack.top() << endl;//3
cout << istack.size() << endl;//2
system("pause");
return 0;
}
queue
queue 是一种容器适配器,用于在FIFO(先入先出)的操作,其中元素插入到容器的一端并从另一端提取。
队列不提供迭代器,不实现遍历操作。
template <class T, class Sequence = deque<T> >
class queue {
friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference front() { return c.front(); }
const_reference front() const { return c.front(); }
reference back() { return c.back(); }
const_reference back() const { return c.back(); }
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_front(); }
};
template <class T, class Sequence>
bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
return x.c == y.c;
}
template <class T, class Sequence>
bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
return x.c < y.c;
}