STL学习笔记-- deque

deque 双端队列容器

    deque 双端队列容器 ( double-ended queue ) 与 vector 非常相似，不仅可在尾部插入和删除元素，还可以在头部插入和删除，算法的时间复杂度也是常数阶 O(1),是一个实现了 Random access container 、Back insertion sequence 和 Front insertion sequence 概念的模型。
    deque 内部的数据机制和执行性能与 vector 不同，一般来说，当考虑到容器元素的内存分配策略和操作的性能时，deque 相对 vector 有优势。
    deque 的 C++ 标准头文件为 deque，需要用宏语句 "#include <deque>" 进行导入，才可使用 deque 进行开发应用。

创建 deque 对象
可用如下的几个构造函数创建 deque 容器对象
1.    deque()
    创建一个没有任何元素的 deque 对象。此构造函数的更一般形式是 " deque(const A& a = A()) "， A 是一个内存分配器，可缺省。
    所创建的 deque 容器实际已具有一个 deque 块，只是头尾迭代器重叠，容器还没有任何元素。例如，下面的一行代码创建了 deque 对象 dInt
    deque<int>  dInt;
    
2.    deque(size_type n)
    创建一个具有 n 个元素的 deque 对象，每个元素采用他的类型下的默认值。此时，deque 头尾迭代器已指向 deque 的头尾元素。
    例如，下面一行代码创建了具有 10 个元素的 deque 对象 dInt，每个元素初始值为 0
    deque<int>  dInt(10);

3.    deque(size_type n, const T& value)
    创建一个具有 n 个元素的 deque 对象，这些元素的初始值为 value。
    例如，下面一行代码创建了一个具有 10 个元素的 deque 对象 dDou，每个元素的初始值为 3.1415
    deque<double>  dDou(10, 3.1415);

4.    deque(const deque&)
    deque的拷贝构造函数，通过拷贝一个 deque 对象的元素值，创建一个新的 deque 对象。此时，新旧 deque 对象具有相同块数的 deque 块，各自块内部的元素也对应相等。
    例如，下面使用了 deque 对象 d1，创建了新的 deque 对象 d2。此时，d2 对象的 5 个元素值也具有字符值 "K"
    deque<char>  d1(5, 'K');
    deque<char>  d2(d1);

5.    deque(const InputIterator first, const InputIterator last, const A& a = A())
    将迭代器区间 [first, last) 所指的元素拷贝到一个新创建的 deque 对象中，其中，内存分配器可缺省。
    // 利用 int 数组 iArray,创建了一个 deque 对象 d
    int iArray[] = {1, 2, 3, 4, 5};
    deque<int>  d(iArray, iArray + 5);




初始化赋值
deque 提供的 push_back() 函数，可在尾部压人新元素 value，常用作 deque 容器的初始化赋值



元素的遍历访问
deque 的元素同样可采用数组、 .at() 函数或者迭代器的方式进行遍历访问。

 

-------------------------------------------------------- 用数组方式访问 deque 元素
#include <deque>
#include <iostream>
using namespace std;
int main()
{

deque<int> dInt;

dInt.push_back(1);

dInt.push_back(3);

dInt.push_back(5);

dInt.push_back(7);


for (int i=0; i<dInt.size(); i++)

{

// 打印 d[0], d[1], d[2], d[3]。访问越界时，不产生异常

cout << "d[" << i << "]=" << dInt[i] << endl;


// 输出 dInt 中各个元素。当访问越界时，会抛出异常
//
cout << dInt.at(i) << endl;

}


return 0;
}

 

-------------------------------------------------------- 用迭代器访问 deque 元素
#pragma warning(disable:4786)
// 必须放在首行，忽略长字符的截断警告
#include <deque>
#include <iostream>
#include <string>
using namespace std;
int main()
{

deque<string> dStr;

dStr.push_back("北京");

dStr.push_back("2008");

dStr.push_back("奥运");


// 迭代器 i 和 iend

deque<string>::iterator i, iend;

iend = dStr.end();

int j;

// 打印 “北京2008奥运”

for (i=dStr.begin(), j=0; i!=iend; ++i, ++j)

cout << *i;

cout << endl;


return 0;
}

 

/*
解释：

由于 deque 使用了两个迭代器分别指向双端队列的首尾，因此，deque 具有高效的【头部】插入元素的函数 push_front()
其他位置的插入，将涉及相关元素的移位拷贝。
*/

-------------------------------------------------------- 头部和中间位置插入 deque 元素
#include <deque>
#include <iostream>
using namespace std;
int main()
{

deque<int> dInt;

dInt.push_back(6);

dInt.push_back(7);


// 头部插入

dInt.push_front(5);

for (int i=0; i<dInt.size(); i++)

cout << dInt[i] << ' ';

cout << endl;


// 中间位置插入

// 在第2个元素之前插入9， 即 5 9 6 7 

dInt.insert(dInt.begin() + 1, 9);

for (int j=0; j<dInt.size(); j++)

cout << dInt[j] << ' ';

cout << endl;


return 0;
}

 

/*
解释：

deque 容器提供了删除首元素的 pop_front 函数，删除尾元素的 pop_back 函数，删除任意位置或迭代器区间上元素的 erase 函数，以及删除所有元素的 clear 函数。
1.
void pop_front();
删除 deque 的第一个元素
2.
void pop_back();
删除 deque 的最后一个元素
3.
iterator erase(iterator pos);
删除 pos 所指向的元素
4.
iterator erase(iterator first, iterator last);
删除 迭代器区间 [first, last) 所指向的所有元素。
5.
void clear();
删除所有元素
*/

-------------------------------------------------------- 头尾和其他位置删除 deque 元素
#include <deque>
#include <iostream>
using namespace std;
int main()
{

deque<int> dInt;

dInt.push_back(4);

dInt.push_back(5);

dInt.push_back(3);

dInt.push_back(3);

dInt.push_back(3);

dInt.push_back(6);

for (int i=0; i<dInt.size(); i++)

cout << dInt[i] << ' ';

cout << endl;


// 头尾和任意删除元素

dInt.erase(dInt.begin() + 1);
// 删除第 2 个元素 dInt[1]

dInt.pop_front();
// 删除首元素

dInt.pop_back();
// 删除末尾元素

for (int j=0; j<dInt.size(); j++)

cout << dInt[j] << ' ';

cout << endl;

// 删除所有元素

dInt.clear();

cout << "执行 clear() " << endl << "deque 元素全部清除" << endl;


return 0;
}

 

-------------------------------------------------------- deque 元素的反向遍历
#include <deque>
#include <iostream>
using namespace std;
int main()
{

deque<int> dInt;

dInt.push_back(1);

dInt.push_back(3);

dInt.push_back(5);

dInt.push_back(7);

dInt.push_back(9);

dInt.push_back(11);

// deque元素的前向遍历

deque<int>::iterator i,iend;

iend = dInt.end();

for (i=dInt.begin(); i!=iend; ++i)

cout << *i << ' ';


cout << endl;

// deque元素的反向遍历

deque<int>::reverse_iterator ri, riend;

riend = dInt.rend();

for (ri=dInt.rbegin(); ri!=riend; ++ri)

cout << *ri << ' ';

cout << endl;


return 0;
}

 

-------------------------------------------------------- 两个 deque 容器的元素交换
#include <deque>
#include <iostream>
using namespace std;

void print(deque<int>& d);

int main()
{

// d1

deque<int> d1;

d1.push_back(11);

d1.push_back(12);

d1.push_back(13);

cout << "d1 = ";

print(d1);


// d2

deque<int> d2;

d2.push_back(90);

d2.push_back(91);

d2.push_back(92);

cout << "d2 = ";

print(d2);


// d1 和 d2 交换

d1.swap(d2);

cout << "d1 和 d2 交换后" << endl;

cout << "d1 = ";

print(d1);

cout << "d2 = ";

print(d2);


return 0;
}

// deque 元素打印
void print(deque<int>& d)
{


for (int i=0; i<d.size(); i++)

cout << d[i] << ' ';

cout << endl;
}

 

/*
解释：

deque 其他函数的说明，参加 Random access container 、 Back insertion sequence 和 Front insertion sequence 概念的函数定义要求，下面给出 deque 的其他几个常用函数的用法。
bool
empty()
判断 deque 容器是否已有元素，是则返回 true，否则返回 false
size_type
size()
当前 deque 容器的元素个数
size_type
max_size()
系统所支持的 deque 容器的最大元素个数
reference
front()
deque容器的首元素（引用返回），要求 deque 不为空
reference
back()
deque容器的末元素（引用返回），要求 deque 不为空
*/

-------------------------------------------------------- deque 其他常用函数的使用
#pragma warning(disable:4786)
#include <deque>
#include <iostream>
#include <string>
using namespace std;
int main()
{

deque<string> dStr;

// 打印 deque 为空

cout << "dStr是否为空: " << dStr.empty() << endl;

// 装入deque 元素

dStr.push_back("红楼梦");

dStr.push_back("三国演义");

dStr.push_back("西游记");

dStr.push_back("水浒传");

dStr.push_back("史记");

dStr.push_back("莫言");

dStr.push_back("金庸");

dStr.push_back("何亮到此一游");

// 打印 deque 所有元素

deque<string>::iterator i, iend;

iend = dStr.end();

for (i=dStr.begin(); i!=iend; ++i)

cout << *i << "
";

cout << endl;

// 打印首元素

cout << "deque 首元素为: " << dStr.front() << endl;

// 打印末元素

cout << "deque 末元素为: " << dStr.back() << endl;

// 打印元素个数

cout << "deque 元素个数为: " << dStr.size() << endl;

// 打印可支持的最大 deque 元素个数

cout << "deque 最大元素个数为: " << dStr.max_size() << endl;


return 0;
}

 

 

 

------------------ deque 小结
    deque 双端队列容器采用分块的线型结构来存储数据，两个迭代器分别指向容器的首尾元素，具有高效的首尾元素的 push_front() 和 pop_front() 函数。
    由于 deque 容器是以 deque 块为单位进行内存分配，并使用了二级的 Map 进行管理，因此，不易于实现类似于 vector 的 capacity 和 reverse 函数，而且，deque 容器也不需要这样的获取和调整容器大小的函数。

　　deque 缺点：频繁的插入删除的时候， deque 不合适。
　　deque 优点：看前面的介绍。