insert 和 erase
iterator insert(iterator pos, const T& x) { node* cur = pos._pnode; // 迭代器中节点的指针 node* prev = cur->_prev; node* newnode = new node(x); // prev newnode cur prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; return iterator(newnode); // 返回值为新插入节点的迭代器 }
iterator erase(iterator pos) { assert(pos != end()); // pos不能等于end() node* cur = pos._pnode; node* prev = cur->_prev; node* next = cur->_next; // prev cur next prev->_next = next; next->_prev = prev; delete cur; return iterator(next); // 返回值为删除节点的下一个节点的迭代器 }
有了 insert 和 erase 函数，那么 push_back 和 push_front 函数就可以改成下面的样子了。
void push_back(const T& x) { insert(end(), x); // end()是哨兵位头节点 } void push_front(const T& x) { insert(begin(), x); // begin()是第一个数据的迭代器 }
pop_back 和 pop_front
void pop_back() { /*node* tail = _head->_prev; node* prev = tail->_prev; // _head prev tail _head->_prev = prev; prev->_next = _head; delete tail;*/ erase(--end()); // --end()为尾结点 } void pop_front() { /*node* head = _head->_next; node* next = head->_next; // _head head next _head->_next = next; next->_prev = _head; delete head;*/ erase(begin()); }
测试样例
void listTest2() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; // 1 2 3 4 5 ++it; } cout << endl; it = lt.begin(); while (it != lt.end()) { *it *= 2; ++it; } for (auto e : lt) { cout << e << " "; // 2 4 6 8 10 } cout << endl; lt.push_front(10); lt.push_front(20); lt.push_front(30); lt.push_front(40); lt.pop_back(); lt.pop_back(); for (auto e : lt) { cout << e << " "; // 40 30 20 10 2 4 6 } cout << endl; }
clear 和 析构函数
void clear() { iterator it = begin(); while (it != end()) { it = erase(it); // erase返回下一个位置的迭代器 } } ~list() { clear(); delete _head; _head = nullptr; }
clear 函数依次释放链表中的节点（除了哨兵位头节点），析构函数则需要将所有节点释放点。所有析构函数可以先复用 clear 函数，再释放哨兵位头节点，再将其置为nullptr。
拷贝构造
传统写法
void empty_init() { // 创建并初始化哨兵位头节点 _head = new node; _head->_prev = _head; _head->_next = _head; } // 拷贝构造传统写法 lt2(lt1) list(const list<T>& lt) { empty_init(); for (const auto& e : lt) // 加引用避免自定义类型的拷贝构造 { push_back(e); } }
现代写法
template <class InputInterator> list(InputInterator first, InputInterator last) { empty_init(); while (first != last) { push_back(*first); ++first; } } void swap(list<T>& x) { std::swap(_head, x._head); // 交换哨兵位的头节点 } // 拷贝构造现代写法 lt2(lt1) list(const list<T>& lt) { // 注意：_head不能为nullptr，因为链表至少要有哨兵位头节点 empty_init(); // 先初始化哨兵位的头节点，防止报错 list<T> tmp(lt.begin(), lt.end()); // 迭代器区间初始化 swap(tmp); // 交换哨兵位头节点 }
赋值运算符重载
传统写法
list<T>& operator=(const list<T>& lt) { if (this != <) // 防止自己给自己赋值 { clear(); // 清理数据 for (const auto& e : lt) { push_back(e); } } return *this; }
现代写法
// l2 = l1 list<T>& operator=(list<T> lt) { swap(lt); return *this; }
用 n 个 val 来构造对象
list(int n, const T& val = T()) { empty_init(); for (int i = 0; i < n; ++i) { push_back(val); } }
size 和 empty
为了避免频繁调用 size 函数，降低效率，所以我们可以多加一个成员变量_size。那么所以跟_size有关的函数接口都需要修改。不过也可以采用不增加成员变量的方式，自己喜欢吧。
增加成员变量的写法
size_t size() const { return _size; } bool empty() const { return _size == 0; }
不增加成员变量的写法
size_t size() const { iterator it = begin(); size_t Size = 0; while (it != end()) { ++Size; ++it; } return Size; } bool empty() const { return _head->_next == _head && _head->_prev == _head; }
注：因为有了 size 和 empty 函数接口，所以之前的 erase、pop_back 等函数接口，都需要进行判空检查。
类名和类型
对于普通类而言，类名就等价于类型；对于类模板而言，类名不等于类型。如：list 模板，类名 list，类型list<T>。而在类模板里面可以用类名代表类型，但是建议不要那么用。但是在类外，类名不等同于类型。
front 和 back
T& front() { assert(!empty()); return *begin(); } const T& front() const { assert(!empty()); return *begin(); } T& back() { assert(!empty()); return *(--end()); } const T& back() const { assert(!empty()); return *(--end()); }
完整代码
namespace Joy { template <class T> struct list_node { list_node* _prev; list_node* _next; T _data; list_node(const T& val = T()) : _prev(nullptr) , _next(nullptr) , _data(val) {} }; // 像指针一样的对象 template <class T, class Ref, class Ptr> struct __list_iterator { typedef list_node<T> node; typedef __list_iterator<T, Ref, Ptr> Self; // Ref是T&，Ptr是T*，Self是迭代器 node* _pnode; // 正向迭代器的成员变量，_pnode是指向节点的指针 __list_iterator(node* pnode = nullptr) : _pnode(pnode) {} Ref operator*() { return _pnode->_data; } bool operator!=(const Self& it) const { return _pnode != it._pnode; } bool operator==(const Self& it) const { return _pnode == it._pnode; } Ptr operator->() { return &(operator*()); } // ++it Self& operator++() { _pnode = _pnode->_next; return *this; } // it++ Self operator++(int) { Self tmp(*this); _pnode = _pnode->_next; return *this; } // --it Self& operator--() { _pnode = _pnode->_prev; return *this; } // it-- Self operator--(int) { Self tmp(*this); _pnode = _pnode->_prev; return tmp; } }; 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; // const正向迭代器 const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } list() { /*_head = new node; _head->_prev = _head; _head->_next = _head;*/ empty_init(); } void empty_init() { // 创建并初始化哨兵位头节点 _head = new node; _head->_prev = _head; _head->_next = _head; _size = 0; } // 拷贝构造传统写法 lt2(lt1) /*list(const list<T>& lt) { empty_init(); for (const auto& e : lt) { push_back(e); } }*/ template <class InputInterator> list(InputInterator first, InputInterator last) { empty_init(); while (first != last) { push_back(*first); ++first; } } void swap(list<T>& x) { std::swap(_head, x._head); // 交换哨兵位的头节点 std::swap(_size, x._size); } // 拷贝构造现代写法 lt2(lt1) //list(const list& lt) list(const list<T>& lt) { empty_init(); // 先初始化哨兵位的头节点，防止报错 list<T> tmp(lt.begin(), lt.end()); // 迭代器区间初始化 swap(tmp); // 交换哨兵位头节点 } // 赋值运算符重载传统写法 /*list<T>& operator=(const list<T>& lt) { if (this != <) // 防止自己给自己赋值 { clear(); // 清理数据 for (const auto& e : lt) { push_back(e); } } return *this; }*/ // 赋值运算符现代写法 //list& operator=(list lt) list<T>& operator=(list<T> lt) { swap(lt); return *this; } list(int n, const T& val = T()) { empty_init(); for (int i = 0; i < n; ++i) { push_back(val); } } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } _size = 0; } // 析构函数 ~list() { clear(); delete _head; _head = nullptr; } void push_back(const T& x) { /*node* tail = _head->_prev; node* newnode = new node(x); // _head _tail newnode tail->_next = newnode; newnode->_prev = tail; _head->_prev = newnode; newnode->_next = _head; ++_size;*/ insert(end(), x); } void push_front(const T& x) { /*node* head = _head->_next; node* newnode = new node(x); // _head newnode head _head->_next = newnode; newnode->_prev = _head; newnode->_next = head; head->_prev = newnode; ++_size;*/ insert(begin(), x); } iterator insert(iterator pos, const T& x) { node* cur = pos._pnode; // 迭代器中节点的指针 node* prev = cur->_prev; node* newnode = new node(x); // prev newnode cur prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; ++_size; return iterator(newnode); // 返回值为新插入节点的迭代器 } iterator erase(iterator pos) { assert(!empty()); assert(pos != end()); // pos不能等于end() node* cur = pos._pnode; node* prev = cur->_prev; node* next = cur->_next; // prev cur next prev->_next = next; next->_prev = prev; delete cur; --_size; return iterator(next); // 返回值为删除节点的下一个节点的迭代器 } void pop_back() { /*assert(!empty()); node* tail = _head->_prev; node* prev = tail->_prev; // _head prev tail _head->_prev = prev; prev->_next = _head; delete tail;*/ erase(--end()); } void pop_front() { /*assert(!empty()); node* head = _head->_next; node* next = head->_next; // _head head next _head->_next = next; next->_prev = _head; delete head; --_size;*/ erase(begin()); } size_t size() const { return _size; } bool empty() const { return _size == 0; } T& front() { assert(!empty()); return *begin(); } const T& front() const { assert(!empty()); return *begin(); } T& back() { assert(!empty()); return *(--end()); } const T& back() const { assert(!empty()); return *(--end()); } private: node* _head; // 哨兵位头节点 size_t _size; }; }
👉vector 和 list 的对比👈
注：vector 和 list 的对比是面试中非常喜欢考的知识点，比如：vector 的扩容问题、迭代器失效问题等等。
vector 的扩容问题
为什么 vector 的扩容倍数是二倍？因为二倍比较合适，扩容过多存在空间浪费问题；扩容过少会导致频繁扩容，影响效率。
vector 的 CPU 高速缓存命中率高
CPU 不会直接访问内存拿取内存中的数据，而是先将内存的数据加载到缓存中，然后 CPU 再去缓存获取想要的数据。而将内存的数据加载到缓存中并不是只加载一个数据，而是加载该数据及其后面一段的数据。为什么呢？根据局部性原理，你访问该数据，就有可能访问其周围的数据，所以就把其周围的数据也加载到缓存中，提高效率。因为 vector 的空间是连续的，所以其高速缓存命中率高。而 list 的空间是不连续的，高速缓存命中率不高，还会带来缓存污染的问题。
迭代器失效问题总结
对于 vector，insert 和 erase 函数接口的不正确使用都会带来迭代器失效问题。vector 的 insert 因为扩容问题而带来迭代器失效问题，而 erase 是因为迭代器的意义变了，即相对位置变了。如果再用该迭代器去访问数据就会导致无法意料的结果。而 list 只有 erase 函数接口会失效，因为其节点都被释放掉了。那么 string 会不会有迭代器失效问题呢？其实 string 也会有迭代器失效问题，insert 和 erase 也会导致迭代器失效，原因和 vector 的迭代器失效原因相似。但是因为不经常使用迭代器向 string 对象里插入数据或者删除数据，通常使用下标来插入或删除数据，所以我们不太关心 string 的迭代器失效问题。
👉总结👈
本篇博客主要介绍了 list 的模拟实现，重点的内容是正向迭代器的实现、vector 和 list 的对比和迭代器失效问题总结。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
