C++基础知识（十五）--- deque 容器

目录

deque 迭代器：

deque 容器实现原理：

deque 常用API：

1. deque 构造函数

2. deque 赋值操作

3. deque 大小操作

4. deque 返回操作

5. deque 双端插入和删除操作 

6. deque 插入和删除操作

---

vector 容器是单向开口的连续内存空间，deque 则是一种双向开口的连续线性空间。

所谓的双向开口，是可以在头尾两端分别做元素的插入和删除操作。

其实 vector 容器也可以在头尾两端插入元素，但效率不高。

deque 迭代器：

随机迭代器。除非有必要，尽可能使用 vector。

deque 容器实现原理：

deque 容器逻辑上是连续的存储空间，这让我们想到 array 和 vector 。array 无法增长，vector 只能向尾端增长（假增长：申请更大空间、原数据复制至新空间、释放原空间），并且每次配置新的空间都有余裕。

实际上，deque 容器是由一段一段定量的块空间通过中央控制连起来的。一旦需要在deque 前端或尾端增加新的空间，便配置一段连续定量的空间，串接在deque 的头端或尾端。

deque 采用一块所谓的 map（不是STL的 map 容器）作为主控，来维持整体连续的假象。这个 map 是一小块连续的内存空间，其中每个元素（结点）都是一个指针，指向另一段连续内存空间，称作缓冲区。缓冲区才是 deque 存储空间的主体。

 

deque 常用API：

1. deque 构造函数

deque deq;       //默认构造形式
deque(begin, end);  //构造函数将[begin, end)区间中的元素拷贝给本身
deque(n, elem);     //构造函数将n个elem拷贝给本身
deque(const deque &deq); //拷贝构造函数

2. deque 赋值操作

assign(begin, end);   //将[begin, end)区间中的数据拷贝赋值给本身。
assign(n, elem);      //将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号操作符 
swap(deq);            // 将deq与本身的元素互换

3. deque 大小操作

deque.size();      //返回容器中元素的个数
deque.empty();     //判断容器是否为空
deque.resize(num); //重新指定容器的长度为num,若容器变长，则以默认值填充新位置。
                   //如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem);  //重新指定容器的长度为num,若容器变长，则以elem值填充新位置,
                          //如果容器变短，则末尾超出容器长度的元素被删除。

4. deque 返回操作

at(idx);    //返回索引idx所指的数据，如果idx越界，抛出out_of_range。
operator[]; //返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
front();    //返回第一个数据。
back();     //返回最后一个数据

5. deque 双端插入和删除操作 

push_back(elem);  //在容器尾部添加一个数据
push_front(elem); //在容器头部插入一个数据
pop_back();       //删除容器最后一个数据
pop_front();      //删除容器第一个数据

6. deque 插入和删除操作

insert(pos,elem);    //在pos位置插入一个elem元素的拷贝，返回新数据的位置
insert(pos,n,elem);  //在pos位置插入n个elem数据，无返回值
insert(pos,begin,end); //在pos位置插入[begin,end)区间的数据，无返回值
 
clear();           //移除容器的所有数据
erase(begin,end);  //删除[begin,end)区间的数据，返回下一个数据的位置
erase(pos);        //删除pos位置的数据，返回下一个数据的位置