1. deque
- deque 容器用数组(数组名假设为 map)存储着各个连续空间的首地址。也就是说,map 数组中存储的都是指针
- 如果 map 数组满了怎么办?很简单,再申请一块更大的连续空间供 map 数组使用,将原有数据(很多指针)拷贝到新的 map 数组中,然后释放旧的空间。
deque容器迭代器的底层实现
template<class T,...>
struct __deque_iterator{
...
T* cur;
T* first;
T* last;
map_pointer node;//map_pointer 等价于 T**
}
cur:指向当前正在遍历的元素;
first:指向当前连续空间的首地址;
last:指向当前连续空间的末尾地址;
node:它是一个二级指针,用于指向 map 数组中存储的指向当前连续空间的指针。
借助这 4 个指针,deque 迭代器对随机访问迭代器支持的各种运算符进行了重载,能够对 deque 分段连续空间中存储的元素进行遍历。例如:
//当迭代器处于当前连续空间边缘的位置时,如果继续遍历,就需要跳跃到其它的连续空间中,该函数可用来实现此功能
void set_node(map_pointer new_node){
node = new_node;//记录新的连续空间在 map 数组中的位置
first = *new_node; //更新 first 指针
//更新 last 指针,difference_type(buffer_size())表示每段连续空间的长度
last = first + difference_type(buffer_size());
}
//重载 * 运算符
reference operator*() const{return *cur;}
pointer operator->() const{return &(operator *());}
//重载前置 ++ 运算符
self & operator++(){
++cur;
//处理 cur 处于连续空间边缘的特殊情况
if(cur == last){
//调用该函数,将迭代器跳跃到下一个连续空间中
set_node(node+1);
//对 cur 重新赋值
cur = first;
}
return *this;
}
//重置前置 -- 运算符
self& operator--(){
//如果 cur 位于连续空间边缘,则先将迭代器跳跃到前一个连续空间中
if(cur == first){
set_node(node-1);
cur == last;
}
--cur;
return *this;
}
deque容器的底层实现
//_Alloc为内存分配器
template<class _Ty,
class _Alloc = allocator<_Ty>>
class deque{
...
protected:
iterator start;
iterator finish;
map_pointer map;
...
}
//begin() 成员函数
iterator begin() {return start;}
//end() 成员函数
iterator end() { return finish;}
//front() 成员函数
reference front(){return *start;}
//back() 成员函数
reference back(){
iterator tmp = finish;
--tmp;
return *tmp;
}
//size() 成员函数
size_type size() const{return finish - start;}//deque迭代器重载了 - 运算符
//enpty() 成员函数
bool empty() const{return finish == start;}
总结
- deque并不是真的连续,是通过迭代器的操作符重载实现的所谓序列化容器。
- deque是靠两个迭代器和一个指针数组实现的
list
- 双向迭代器
list容器的底层实现
1. 双向列表
2. 双向循环列表
- node: 可以看到,双向链表的各个节点中存储的不仅仅是元素的值,还应包含 2 个指针,分别指向前一个元素和后一个元素。
template<typename T,...>
struct __List_node{
//...
__list_node<T>* prev;
__list_node<T>* next;
T myval;
//...
}
list容器迭代器的底层实现
template<tyepname T,...>
struct __list_iterator{
__list_node<T>* node;
//...
//重载 == 运算符
bool operator==(const __list_iterator& x){return node == x.node;}
//重载 != 运算符
bool operator!=(const __list_iterator& x){return node != x.node;}
//重载 * 运算符,返回引用类型
T* operator *() const {return *(node).myval;}
//重载前置 ++ 运算符
__list_iterator<T>& operator ++(){
node = (*node).next;
return *this;
}
//重载后置 ++ 运算符
__list_iterator<T>& operator ++(int){
__list_iterator<T> tmp = *this;
++(*this);
return tmp;
}
//重载前置 -- 运算符
__list_iterator<T>& operator--(){
node = (*node).prev;
return *this;
}
//重载后置 -- 运算符
__list_iterator<T> operator--(int){
__list_iterator<T> tmp = *this;
--(*this);
return tmp;
}
//...
}
- 主要是一个node指针
list容器的底层实现
不同版本的 STL 标准库中,list 容器的底层实现并不完全一致,但原理基本相同。这里以 SGI STL 中的 list 容器为例,讲解该容器的具体实现过程。
template <class T,...>
class list
{
//...
//指向链表的头节点,并不存放数据
__list_node<T>* node;
//...以下还有list 容器的构造函数以及很多操作函数
}
- 也是一个node指针
- 但是为了更方便的实现 list 模板类提供的函数,该模板类在构建容器时,会刻意在容器链表中添加一个空白节点,并作为 list 链表的首个节点(又称头节点)。
注意:
使用双向链表实现的 list 容器,其内部通常包含 2 个指针,并分别指向链表中头部的空白节点和尾部的空白节点(也就是说,其包含 2 个空白节点)。
- 经常构造空的 list 容器,其用到的构造函数如下所示:
list() { empty_initialize(); }
// 用于空链表的建立
void empty_initialize()
{
node = get_node();//初始化节点
node->next = node; // 前置节点指向自己
node->prev = node; // 后置节点指向自己
}
//故
//begin()成员函数
__list_iterator<T> begin(){return (*node).next;}
//end()成员函数
__list_iterator<T> end(){return node;}
//empty()成员函数
bool empty() const{return (*node).next == node;}
//front()成员函数
T& front() {return *begin();}
//back()成员函数
T& back() {return *(--end();)}
注意:end()返回的是node即头节点
4 . 显然,即便是创建空的 list 容器,它也包含有 1 个节点。文章来源:https://www.toymoban.com/news/detail-652023.html
- 除此之外,list 模板类中还提供有带参的构造函数,它们的实现过程大致分为以下 2 步:
调用 empty_initialize() 函数,构造带有头节点的空 list 容器链表;
将各个参数按照次序插入到空的 list 容器链表中
forward_list
forward_list 是 C++ 11 新添加的一类容器,其底层实现和 list 容器一样,采用的也是链表结构,只不过 forward_list 使用的是单链表,而 list 使用的是双向链表(如图 所示)。
文章来源地址https://www.toymoban.com/news/detail-652023.html
到了这里,关于面试之快速学习STL-deuqe和list的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!