C++STL-＞list模拟实现

---

theme: smartblue

list list文档

list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向 其前一个元素和后一个元素。list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高 效。与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率 更好。 5.与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间 开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素) list类的函数接口 namespace ding { //结点类 template<class T> struct _list_node { //构造函数 _list_node(const T& val = T()); T _data; _list_node<T>* _next; _list_node<T>* _prev; }; //迭代器类 template<class T, class Ref, class Ptr> struct _list_iterator { typedef _list_node<T> node; typedef _list_iterator<T, Ref, Ptr> self; //构造函数 _list_iterator(node* pnode); self operator++(); self operator--(); self operator++(int); self operator--(int); bool operator==(const self& s) const; bool operator!=(const self& s) const; Ref operator*(); Ptr operator->(); //成员变量 node* _pnode; }; //list类 template<class T> class list { public: typedef _list_node<T> node; typedef _list_iterator<T, T&, T*> iterator; typedef _list_iterator<T, const T&, const T*> const_iterator; //Member functions list(); list(const list<T>& lt); list<T>& operator=(const list<T>& lt); ~list(); //Iterators: iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; //Element access: T& front(); T& back(); const T& front() const; const T& back() const; //Modifiers: void insert(iterator pos, const T& x); iterator erase(iterator pos); void push_back(const T& x); void pop_back(); void push_front(const T& x); void pop_front(); //Capacity: size_t size() const; void resize(size_t n, const T& val = T()); void clear(); bool empty() const; void swap(list<T>& lt); private: node* _head; }; } 结点类的实现

list底层采用了带头双向循环链表的结构实现。

在实现list前，需要定义出一个一个结点出来。直接定义一个结点类，让结点类完成结点的构造即可。

template<class T> struct _list_node { _list_node(const T& val = T()) :_data(val) ,_next(nullptr) ,_prev(nullptr) {} T _data; _list_node<T>* _next; _list_node<T>* _prev; }; 迭代器类的实现 list底层物理空间不再连续，不再支持[]+下标的方式进行访问

只能用迭代器进行访问list迭代器的实现不能再像string或者vector那种底层物理空间连续的容器使用原生指针进行实现。底层空间连续，使用原生指针实现，指针自增或者自减就可以访问到对应的元素，而list由于底层物理空间不来连续的原因，不能再使用原生指针

解决方法：

定义一个迭代器类，迭代器相关的操作(比如++,!=,*)等操作但都在迭代器类中重载

结合之前string类和vector类的实现得知迭代器要么就是原生指针，要么就是自定义类型对原生指针的一种封装，去模拟指针的行为。比如对结点指针自增就能指向下一个结点

构造函数

迭代器就是对结点指针进行封装，这里只需要一个结点指针成员变量即可。

_list_iterator(node* node) { _node = node; } ++运算符重载 self operator++() { _node = _node->_next; return *this; } self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } 这里的self是经过typedef后的typedef _list_iterator<T, Ref, Ptr> self就是迭代器类类型前置++与后置++重载语法规定后置++的形参必须为int。后置++先记录一下当前结点，再让结点指向后一个，返回自增前的即可。 –运算符重载 self operator--() { _node = _node->_prev; return *this; } self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } *运算符重载

解引用操作符，是想拿到地址的内容，直接返回当前结点的数据内容即可。

Ref operator*() { return _node->_data; }

注意： 这里的返回值是Ref,在定义迭代器类是时候定义了三个模板参数，T就是指定的类型，Ref则是指定类型的引用类型，也就是T&，Ptr则是指定类型的指针类型，也就是T*。 在list的实现中，

typedef _list_iterator<T, T&, T*> iterator; typedef _list_iterator<T, const T&, const T*> const_iterator; STL底层源码就是这样设计的，主要就是为了解决const迭代器的问题，如果不用模板解决的话，可以在定义一个const iterator类也可以解决问题，但是在实现以一个const迭代器与普通迭代器的区别就仅仅只是*返回值类型不一样而已，利用模板参数解决更妙。普通迭代器返回T&类型，const迭代器返回const T&类型。这里返回引用类型，主要是因为解引用后可能需要对数据进行修改。 != && ==

迭代器经常需要进行判断两个迭代器是否相等不相等的操作，这里这需要判断两个迭代器中的结点是否相等即可，不需要做其他操作，定义出成const更为合理。

bool operator==(const self& s) const { return _node == s._node; } bool operator!=(const self& s) const { return _node != s._node; } ->操作符重载

这个操作符对于迭代器类型并不是很常用，但是为了模拟指针的行为，指针有->操作符，迭代器就模拟实现了。

运算符 -> 必须是一个成员函数。如果使用了 -> 运算符，返回类型必须是指针或者是类的对象。也就是这里返回值必须是Ptr 指定类型T*类型。

Ptr operator->() { return &(_node->_data); }

使用->场景： 当list中存放的是自定义类型，

class Date { public: Date(int year) { _year = year; } int _year = 0; }; int main() { std::list<Date>lt; lt.push_back(2023); lt.push_back(2024); auto it = lt.begin(); cout << it->_year << endl; return 0; }

可以使用->访问类的成员变量。

list类的实现 Member functions 构造函数 list() { _head = new node; _head->_prev = _head; _head->_next = _head; }

这里的node是经过typedef得。typedef _list_node<T> node;对结点类起的别名 构造一个链表即可，这里得空链表是需要一个头节点得。并且让自己指向自己。

拷贝构造

申请一个新的头结点，再将源容器中的数据依次尾插到新容器中即可

list(const list<T>& lt) { _head = new node; _head->_next = _head; _head->_prev = _head; for (auto val : lt) { push_back(val); } } 赋值运算符重载 将原来容器中的数据清空，在依次尾插新元素即可注意要判断是否自己给自己赋值，不能自己给自己赋值，自己给自己赋值clear后数据丢失了 list<T>& operator=(const list<T>& lt) { if (this != &lt) { clear(); for (const auto e : lt) { push_back(e); } } return *this; } 迭代器构造 template<class InputIterator> list(InputIterator first, InputIterator last) { _head = new node; _head->_prev = _head; _head->_next = _head; while (first != last) { push_back(*first); ++first; } } 析构函数

先清空容器在释放头节点即可

~list() { clear(); delete _head; _head = nullptr; } clear函数 void clear() { auto it = begin(); while (it != end()) { erase(it++); } } Iterators begin && end

begin函数返回的是第一个有效数据的迭代器，end函数返回的是最后一个有效数据的下一个位置的迭代器 底层是双向循环链表实现的，所以头结点的下一个就是gebin，头节点就是end。

iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head->_prev); } const_iterator begin() const { return iterator(_head->_next); } const_iterator end() const { return iterator(_head->_prev); } Modifiers insert

在pos位置前面插入一个结点

void insert(iterator pos, const T& x) { node* newnode = new node(x);//创建新结点 node* cur = pos._node;//pos位置的结点指针 node* prev = cur->_prev;//pos前一个 //连接关系 prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; } push_back && push_front 尾插 && 头插在链表的尾部插入一个结点 && 在链表的头部插入一个结点有了insert和迭代器，直接函数复用即可 //尾插 void push_back(const T& x) { insert(end(), x); } //头插 void push_front(const T& x) { insert(begin(), x); } eraser

删除pos位置的结点

iterator erase(iterator pos) { node* cur = pos._node;//当前结点指针 node* prev = cur->_prev;//pos位置前一个结点 node* next = cur->_next;//pops位置后一个结点 //连接关系 prev->_next = next; next->_prev = prev; //释放删除的结点 delete cur; return iterator(next);//防止迭代器失效，返回pos位置下一个迭代器 } pop_back && pop_front 尾删和头删复用迭代器和rease即可end是头节点，尾删时需要–end() 才是尾部结点 void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } Capacity size 求容器元素个数遍历容器求个数(效率太低不推荐) size_t size() const { size_t size = 0; auto it = begin(); while (it != end()) { size++; it++; } return size; } 在定义一个成员变量统计元素个数(以空间换时间，更推荐) clear 清空list中的结点，除了头结点。利用迭代器遍历尾删即可 void clear() { auto it = begin(); while (it != end()) { pop_back(); } } empty bool empty() const { return _head->_next; } resize 扩容加初始化函数resize规则若当前容器的size小于所给n，则尾插结点，直到size等于n为止。若当前容器的size大于所给n，则只保留前n个有效数据。 void resize(size_t n, const T& val = T()) { size_t sz = size(); if (sz < n)//扩容 { for (; sz < n; ++sz) { push_back(val); } } else//不扩容 { if (sz > n)//缩容 { int len = sz - n; cout << len << endl; while (len--) { pop_back(); } } } } swap函数

交换两个容器的头指针即可

void swap(list<T>& lt) { std::swap(_head, lt._head); } 参考源码 gitee 码云 - 开源中国欢迎在评论区提出问题或留下你的观点