【STL】顺序容器之deque用法总结

       

一、基本原理

       vector是单向开口的连续线性空间，在头部操作效率奇差，无法被接受。deque则是一种双向开口的连续线性空间，可以在头尾两端分别做元素的插入和删除操作。
       deque和vector的最大差异，一是在于deque允许于常数时间内对其头部进行元素的插入和删除操作，认识在于deque没有所谓容量（capacity）的概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。也就是说，在deque中不存在像vector那样“因旧空间不足而重新配置一块更大的空间，然后赋值元素，释放旧空间”的事情。

        deque也支持随机访问，你或许会觉得deque的实现复杂度和vector差不多，实际上deque的实现代码量远比vector或list都多得多。
        如图，deque采用一小块连续空间作为主控，主控中的每个元素都是指针，指向另一段较大的连续线性空间，称为缓冲区，缓冲区是deque的存储空间主体。deque由一段一段的定量连续空间构成，为了维持整体连续的假象，deque数据结构的设计和迭代器的前进后退等操作都颇为繁琐，它的迭代器并不是普通指针。

       

       

       

二、用法

       以下都以容器deque中的元素为int为例，若要保存其他类型的元素，将int换成其他类型即可。
       

初始化

创建一维队列的方法	deque<类型名>    队列名;
deque<int>   d1;	创建一个名为d1的空队列，d1中的元素类型为int
deque<int>   d1(100,7);	d1中的元素为100个7
deque<int>   d1{1,2,3,……};	元素为1,2,3,……的d1
deque<int>   d2(d1);	队列d2中包含和队列d1一样的元素
deque<int>   d2=d1;	队列d2中包含和队列d1一样的元素

       

访问元素

访问元素
d1[n]	访问下标为n的那个元素
d1.at(n);	访问下标为n的那个元素
d1.front();	访问d1的队首元素
d1.back();	访问d1的队尾元素
*iter	访问迭代器iter指向的元素

获取迭代器
d1.begin();	获取指向d1队首元素的迭代器
d1.end();	获取指向d1队尾元素的后一个位置的迭代器
d1.rbegin();	获取指向d1队首元素的前一个位置的迭代器
d1.rend();	获取指向d1队尾元素的迭代器
d1.cbegin(); d1.cend();	含义同上，但获取到的是const_iterator
d1.crbegin(); d1.crend();	含义同上，但获取到的是const_iterator

       

遍历容器

1、普通for语句

for (int i = 0; i < d1.size(); ++i) {
    
		cout << d1[i] << endl;   // 输出当前元素并换行
}

使用迭代器

for (deque<int>::iterator iter = d1.begin(); iter != d1.end();++iter) {
    
	cout << *iter << endl;		// 输出当前元素并换行
}

2、范围for语句

for (auto it : d1) {
    
	cout << it << endl;		// 输出当前元素并换行
}

       

添加与删除元素

添加
d1.push_front(a);	在d1队首添加一个元素a
d1.emplace_front(a);	在d1队首添加一个元素a
d1.push_back(a);	在d1队尾添加一个元素a
d1.emplace_back(a);	在d1队尾添加一个元素a
d1.insert(iter,a);	迭代器iter指向的元素之前添加一个元素a
d1.insert(iter,n,a);	迭代器iter指向的元素之前添加 n 个元素a
d1.insert(iter,{a,b,c});	迭代器iter指向的元素之前添加大括号内的所有元素，这里添加的元素是a、b、c

删除
d1.pop_front();	在d1队首删除一个元素
d1.pop_back();	在d1队尾删除一个元素
d1.erase(iter);	删除迭代器iter指向的元素
d1.erase(iter1,iter2);	删除迭代器iter1和ter2指向的范围中元素
d1.clear();	删除d1中的所有元素

       

替换元素

swap、assign
d1=d2;	将d1中的元素替换为d2
d1.swap(d2);	交换d1和d2的元素，swap通常比从d2向d1拷贝元素要快得多
swap(d1,d2);	交换d1和d2的元素，swap通常比从d2向d1拷贝元素要快得多
d1={1,2,3,……};	将d1中的元素替换为初始化列表中的元素1,2,3,……
d1.assign(iter1,iter2);	将d1中的元素替换为迭代器iter1和iter2所指范围中的元素。迭代器iter1、iter2不能指向d1中的元素
d1.assign({1,2,3,……});	将d1中的元素替换为初始化列表中的元素1,2,3,……
d1.assign(7, 1);	将d1中的元素替换为7个1（仅为举例，换成别的也行）

       

deque的大小

d1.szie();	获得d1实际上使用的空间的大小
d1.empty();	若d1为空返回值为true，否则返回值为false
d1.maxsize()	可保存的最大元素的数目
d1.shrink_to_fit();	退回容器不需要的内存空间，调用该函数不保证一定退回内存空间
d1.resize(n)	调整d1的大小为n个元素，若n<d1.size()，多余的元素会被丢弃。若要添加新元素，新元素会被默认初始化（比如0）
d1.resize(n,t)	调整d1的大小为n个元素，任何添加的新元素值会被初始化为t

       

查找、替换、排序、去重、求和

       请使用C++标准库里的泛型算法（find、replace、sort、unique、accumulate……），标准库提供了100多个算法，这些算法适用于大多数容器。

       

       

       

       

       

三、时间复杂度

操作
随机访问	O(1)
查找	O(n)
在队首或队尾添加元素	若不重新分配空间，O(1)
在队首或队尾删除元素	O(1)

       

       

       

四、注意事项：下标越界、迭代器失效

下标越界
       当你使用d1[n]访问队列元素时，如果n>=d1.size()，函数的行为是未定义的，编译器并不会帮你检查队列下标是否合法，保证下标合法是程序员的责任。
       如果你使用d1.at(n)访问队列元素，如果下标n越界，at函数会跑出一个out_of_range异常。

       

迭代器失效

向容器中添加或删除元素都有可能会使容器的迭代器失效。

向容器添加元素后：

• （1） deque和string：若存储空间重新分配，则迭代器全部失效。若存储空间没有重新分配，则指向插入位置之前的元素的迭代器仍有效，之后的元素的迭代器将会失效。
• （2） deque:插入元素到除了首尾位置之外的任何位置，都会使迭代器、指针、引用失效。插入元素到首尾，迭代器会失效，指向原来元素的指针和引用仍有效。
• （3） list和forward_list：迭代器、指针、引用仍然有效。

在容器中删除一个元素后：

• （1） deque和string：指向被删除元素之前的迭代器、引用、指针仍有效。当我们删除元素时，尾后迭代器总是会失效。
• （2） deque:在首尾位置之外的任何位置删除元素，迭代器、指针、引用都会失效。如果删除的是尾元素，那么尾后迭代器失效，其他迭代器、引用、指针仍有效。如果删除的是首元素，迭代器、指针、引用仍有效。
• （3） list和forward_list：指向除删除元素外的其他元素的迭代器、指针、引用仍然有效。