deque 双端队列容器 学习笔记

deque双端队列容器与vector一样，采用线性表顺序存储结构，但与vector唯一不同的就是deque采用分块的线性存储结构来存储数据，每块的大小一般为512字节，称为一个deque块，所有的deque块使用一个Map块进行管理，每个Map数据项纪录各个deque块的首地址，这样一来，deque块在头部都可插入和删除新的元素，而不移动其他元素(使用push_back()方法在尾部插入元素，会扩张队列；而使用push_front()方法在首部插入元素和使用insert()方法在中间插入元素，只是将原位置上的元素覆盖，不会增加新元素)。一般来说，当考虑到容器元素的内存分配策略和操作的性能时，deque相对于vector更有优势，双端队列容器结构示意图如图所示：

使用deque需要声明头文件#include <deque>

<创建deque对象>

创建deque对象的方法通常有三种：
<1>. 创建没有任何元素的deque对象，如：
deque <int> d;
deque <float> dd;


<2>. 创建具有n个元素的deque对象，如：
deque <int> d(10); //创建具有10个整型元素的deque对象d;


<3>. 创建具有n个元素的deque对象，并赋初值， 如：
deque <float> d(10, 8.5); //创建具有10个单精度浮点型的元素的deque对象d,每个元素的值为8.5；

<deque插入元素>

<1>. 使用push_back()方法从尾部插入元素，会不断地扩张队列：


#include <iostream>
#include <deque>
using namespace std;


int main(int argc, char *argv[])
{
    //定义deque对象，元素类型为整型;
    deque <int> d;
    //从尾部连续插入三个元素;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    //以数组方式输出元素;
    cout << d[0] << " " << d[1] << " " << d[2] << endl;
    return 0;
}


运行结果为：
1 2 3


<2>. 从头部插入元素，不会增加新元素，只将原有元素覆盖；


#include <iostream>
#include <deque>
using namespace std;


int main(int argc, char *argv[])
{
    //定义deque对象，元素类型为整型;
    deque <int> d;
    //从尾部连续插入三个元素;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    //从头部插入元素，不会增加元素，只将原有元素覆盖;
    d.push_front(10);
    d.push_front(20);
    //以数组方式输出元素;
    cout << d[0] << " " << d[1] << " " << d[2] << endl;
    return 0;
}


运行结果为：
20 10 1


<3>. 从中间插入元素，不会增加新元素，只将原有元素覆盖；


#include <iostream>
#include <deque>
using namespace std;


int main(int argc, char *argv[])
{
    //定义deque对象，元素类型为整型;
    deque <int> d;
    //从尾部连续插入三个元素;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    //从头部插入元素，不会增加元素，只将原有元素覆盖;
    d.insert(d.begin()+1, 88);
    //以数组方式输出元素;
    cout << d[0] << " " << d[1] << " " << d[2] << endl;
    return 0;
}


运行结果为：
1 88 2

<deque前向遍历>

<1>. 以数组方式遍历；


#include <iostream>
#include <deque>
using namespace std;


int main(int argc, char *argv[])
{
    //定义deque对象，元素类型为整型;
    deque <int> d;
    //从尾部连续插入三个元素;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    //以数组方式输出元素;
    for(int i=0; i<d.size(); i++) {
        cout << d[i] << " ";
    }
    cout << endl;
    return 0;
}


运行结果为：
1 2 3


<2>. 以前向迭代器的方式遍历：


#include <iostream>
#include <deque>
using namespace std;


int main(int argc, char *argv[])
{
    //定义deque对象，元素类型为整型;
    deque <int> d;
    //从尾部连续插入三个元素;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    //以数组方式输出元素;
    deque <int> :: iterator it;  //以前向迭代器的方式遍历；
    for(it=d.begin(); it != d.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}

<deque反向遍历>

采用反向迭代器对双端队列容器进行反向遍历；


#include <iostream>
#include <deque>
using namespace std;


int main(int argc, char *argv[])
{
    //定义deque对象，元素类型为整型;
    deque <int> d;
    //从尾部连续插入三个元素;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    //以数组方式输出元素;
    deque <int> :: reverse_iterator rit;
    for(rit=d.rbegin(); rit != d.rend(); rit++) {
        cout << *rit << " ";
    }
    cout << endl;
    return 0;
}


运行结果为：
3 2 1

<deque删除元素>

可以从双端队列容器的首部，尾部和中间删除元素，并可以清空双端队里容器。举例分别如下：


<1>. 采用pop_front()方法从头部删除元素；


#include <iostream>
#include <deque>
using namespace std;


int main(int argc, char *argv[])
{
    //定义deque对象，元素类型为整型;
    deque <int> d;
    //从尾部连续插入五个元素;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    d.push_back(4);
    d.push_back(5);
    //从头部删除元素;
    d.pop_front();
    d.pop_front();
    //以前序迭代器的方式遍历；
    deque <int> :: iterator it;
    for(it=d.begin(); it != d.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}


运行结果为：
3 4 5


<2>. 采用pop_back()方法从尾部删除元素；


#include <iostream>
#include <deque>
using namespace std;


int main(int argc, char *argv[])
{
    //定义deque对象，元素类型为整型;
    deque <int> d;
    //从尾部连续插入五个元素;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    d.push_back(4);
    d.push_back(5);
    //从尾部删除元素;
    d.pop_back();
    d.pop_back();
    //以前序迭代器的方式遍历；
    deque <int> :: iterator it;
    for(it=d.begin(); it != d.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}


运行结果为：
1 2 3


<3>. 使用erase()方法从中间删除元素，其参数是迭代器的位置；


#include <iostream>
#include <deque>
using namespace std;


int main(int argc, char *argv[])
{
    //定义deque对象，元素类型为整型;
    deque <int> d;
    //从尾部连续插入五个元素;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    d.push_back(4);
    d.push_back(5);
    //从尾部删除元素;
    d.erase(d.begin()+1);
    d.erase(d.end()-1);
    //以前序迭代器的方式遍历；
    deque <int> :: iterator it;
    for(it=d.begin(); it != d.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}


运行结果为：
1 3 4


<4>. 使用clear()方法清空deque对象；


#include <iostream>
#include <deque>
using namespace std;


int main(int argc, char *argv[])
{
    //定义deque对象，元素类型为整型;
    deque <int> d;
    //从尾部连续插入五个元素;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    d.push_back(4);
    d.push_back(5);
    //清空元素;
    d.clear();
    //输出容器内元素个数；
    cout << d.size() << endl;
    return 0;
}


运行结果为：
0

deque 双端队列容器 学习笔记

原文：http://blog.csdn.net/keshacookie/article/details/19609503