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位置的数据，返回下一个数据的位置