面试之快速学习STL-deuqe和list

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();)}