deque

deque 容器

1. 基本概念

  • 功能：双端数组，可以对头端进行插入删除操作,deque的迭代器支持随机访问
  • 和vector的区别
    1. vector对于头部的插入删除效率低，数据量越大，效率越低
    2. deque相对而言，对头部的插入删除速度比vector快
    3. vector访问元素时的速度没有deque快

  • 内部工作原理

    1. deque有一个中控器，维护每段缓冲区的内容，缓冲区中存放真实数据
    2. 中控器维护的是每个缓冲区的地址，是的使用deque时像一片连续的内存空间
    3. 这种结构决定了比vector插入数据时要快，然而访问数据比vector慢

2. 构造函数

  • 函数原型
    1. deque< T > deq; //默认构造函数
    2. deque(beg,end); //构造函数将[begin,end)区间的元素拷贝给本身
    3. deque(n,elem); //构造函数将n个elem拷贝给本身
    4. deque(const deque &deq);//拷贝构造函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<deque>
using namespace std;
void printDeque(const deque<int>& deq) {
	for (deque<int>::const_iterator it = deq.begin(); it != deq.end(); it++) {
		//*it = 100;//报错，限定为只读状态
		cout << *it << " ";
	}
}
int main() {
	deque<int> deq;
	for (int i = 0; i < 10; i++) {
		deq.push_back(i);
	}
	printDeque(deq);
	deque<int> d1(deq.begin(),deq.end());
	deque<int> d2(10, 100);
	deque<int>d3(d1);
	return 0;
}

3.赋值操作

  • 函数原型
    1. deque& operator = (const deque &deq);
    2. assign(beg,end);// 将[begin,end)区间的元素拷贝给本身
    3. assign(n,elem);//将n个elem拷贝给本身

4. 大小操作

  • 函数原型
    1. deque.empty(); //判断容器是否为空
    2. deque.size();//返回容器中元素的个数
    3. deque.resize(num);//重新指定容器的长度为num,若瑢变长，则以默认值填充新位置，如果变短，则末尾超出的容器长度的元素将会被删除
    4. deque.resize(n,elem);//多出的值用elem填充

5. 插入删除

  • 函数原型

    两端插入操作

    1. push_back();//在容器尾部插入一个数据
    2. push_front(); //在容器头部插入一个数据
    3. pop_back();//删除容器最后一个数据
    4. pop_front();//删除容器第一个数据

    指定位置操作

    1. insert(pos,elem);//在pos位置插入一个elem,返回新数据的位置
    2. insert(pos,n,elem);//在pos位置插入n个elem元素，无返回值
    3. insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值
    4. clear();
    5. erase(beg,end);//删除[beg,end)区间的数据，无返回值
    6. erase(pos);//删除pos位置的元素，返回下一个数据的位置

6. 数据存取

  • 函数原型
    1. at(int idx);
    2. operator[];
    3. front();
    4. back();

7.排序

  • 函数原型

    sort(iterator beg,iterator end);//默认升序

    对于支持随机访问的迭代器的访问，都可以利用sort直接排序