八、list
1. list的介绍
是的， list 就是带头双向循环链表。
2. list的使用
通过 string 和 vector 的学习，我们差不多已经很了解容器的使用了，接下来要非常快速的过一遍了。
#include<iostream> #include<list> using namespace std; int main() { 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 << " "; ++it; } cout << endl; for (auto e : lt) { cout << e << " "; } cout << endl; return 0; }
简简单单。
链表嘛，有头插、头删、尾插、尾删。也非常好使用，跟 push_back() 和 pop_back() 一样的用法。看到了 insert 和 erase ，我们知道，vector 的 insert 和 erase 可能会发生迭代器失效的问题，那 list 会出现吗？答案是不会发生，毕竟是链表嘛。
list 的大部分接口我们都了解了，我们就来看看一些之前没见过的东西。
首先我们来看看 reverse 。注意！是 reverse ，不是 reserve ，前者是逆置的意思，后者是保留，扩容的意思。sort 是排序的意思。
非常的简洁明了啊。
#include<iostream> #include<list> using namespace std; int main() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); for (auto e : lt) { cout << e << " "; } cout << endl; lt.reverse(); for (auto e : lt) { cout << e << " "; } cout << endl; lt.sort(); for (auto e : lt) { cout << e << " "; } cout << endl; return 0; }
sort 默认排的都是升序，若是想要排降序，需要用到 仿函数 ，这里先不过多介绍。list 的 sort 效率比较低，当数据量大的时候，经量不要用 list 的 sort 排序。
merge 是合并的意思，用的比较少。
unique 的作用是去重，去除重复元素，要求是必须先有序。
#include<iostream> #include<list> using namespace std; int main() { list<int> lt; lt.push_back(2); lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(5); lt.push_back(1); lt.push_back(5); lt.push_back(4); lt.push_back(4); lt.push_back(4); lt.push_back(5); lt.push_back(1); lt.push_back(2); for (auto e : lt) { cout << e << " "; } cout << endl; // 先排序 lt.sort(); for (auto e : lt) { cout << e << " "; } cout << endl; // 再去重 lt.unique(); for (auto e : lt) { cout << e << " "; } cout << endl; return 0; }
remove 相当于 find + erase ，给你一个值，找到了就删，找不到就不删。
splice 这个接口很怪，它的作用是 转移 。
它可以将某一个链表，或者某个链表的某个值，或者某个链表的某一块区间转移到 position 位置 。也可以自己转移自己。
#include<iostream> #include<list> using namespace std; int main() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); for (auto e : lt) { cout << e << " "; } cout << endl; // 将 lt 链表的 begin() 转移到 lt 链表的 end() lt.splice(lt.end(), lt, lt.begin()); for (auto e : lt) { cout << e << " "; } cout << endl; return 0; }
确实将头部的 1 转移到 尾部的 5 后面了。转移的本质是改变节点的指向，并不是删除或创建节点 。
3. list的模拟实现
我们快速的搭一个 list 框架出来， 这个框架大致基于 STL库里的 list 。注意理解。
#pragma once #include<assert.h> namespace my { // struct 成员默认全公开 节点结构体 template<class T> struct ListNode { // 后继指针 ListNode<T>* _next; // 前驱指针 ListNode<T>* _prev; // 数据域 T _data; // 构造函数 ListNode(const T& x = T()) :_next(nullptr) ,_prev(nullptr) ,_data(x) {} }; template<class T> class list { typedef ListNode<T> Node; public: // 默认构造 list() { _head = new Node; _head->_next = _head; _head->_prev = _head; } private: // 指向头节点的指针 Node* _head; }; }
写一个尾插操作：
// list类的 public域 void push_back(const T& x) { // 实例化新节点 Node* newnode = new Node(x); // 尾部节点 Node* tail = _head->_prev; // 修改新节点的指向 newnode->_next = _head; newnode->_prev = tail; // 修改指向新节点的指针 tail->_next = newnode; _head->_prev = newnode; }
有了尾插，我们就想去测试一下，但是测试需要访问，list 本身不支持 下标 + [] 访问，只能通过迭代器访问。我们之前说过 迭代器是一个行为像指针的东西，但不一定是指针 。那么 list 这里的迭代器可以使用原生指针吗，我们发现，链表本身是不连续的，我们 ++指针 无法访问到到下一个元素，解引用指针 也访问不到元素的数据。
因此，这里的迭代器并不能使用原生指针来代替。我们知道，可以通过重载一系列运算符来改变类的行为 ，就像日期类一样，++日期 可以得到下一天的日期，那么我们也可以将迭代器封装成一个类，然后通过重载运算符来改变其行为。
// my命名空间内 // 迭代器模板 template<class T> struct ListIterator { typedef ListNode<T> Node; // 指向节点的指针 Node* _node; // 构造函数 ListIterator(Node* node) :_node(node) {} };
我们只写了迭代器类的构造函数，并没有写迭代器的拷贝构造函数。我们没写，编译器会自动生成，编译器生成的拷贝构造是浅拷贝，但恰巧我们要的就是浅拷贝（新的节点也指向某个节点）。析构函数需要写吗？也不需要，因为在这个迭代器类里，只有一个指针而已，节点的空间资源并不属于这个类，所以也不需要这个类来释放。
先来控制迭代器的行为：
// 前置++ Self& operator++() { _node = _node->_next; return *this; } // 后置++ Self operator++(int) { // 拷贝构造 Self tmp(*this); _node = _node->_next; return tmp; } // 前置-- Self& operator--() { _node = _node->_prev; return *this; } // 后置-- Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; }
接着是迭代器的解引用：迭代器解引用我们要得到什么？得到节点的值，所以要返回数据
// 可读可写 T& operator*() { return _node->_data; }
判断相等：
bool operator!=(const Self& it) { return _node != it._node; } bool operator==(const Self& it) { return _node == it._node; }
现在我们要实现 begin 和 end 。请问这两个函数在哪里实现？在迭代器类里面实现吗？不对，迭代器类根本不知道链表的组成，这俩函数只能在 list类 里面实现。
// list类里面 iterator begin() { // 匿名对象 return iterator(_head->_next); } iterator end() { // 匿名对象 _head是最后一个节点的下一个节点 return iterator(_head); }
完事儿，迭代器的行为也写完了，我们把当前的完整代码给出来：
#pragma once #include<assert.h> namespace my { // struct 成员默认全公开 节点结构体 template<class T> struct ListNode { // 后继指针 ListNode<T>* _next; // 前驱指针 ListNode<T>* _prev; // 数据域 T _data; ListNode(const T& x = T()) :_next(nullptr) ,_prev(nullptr) ,_data(x) {} }; // 迭代器模板 template<class T> struct ListIterator { typedef ListNode<T> Node; // self : 自己 typedef ListIterator<T> Self; // 指向节点的指针 Node* _node; ListIterator(Node* node) :_node(node) {} // 没写拷贝构造，因为这是内置类型，默认生成的拷贝构造是浅拷贝，我们要的就是浅拷贝 // 也不需要写析构函数，迭代器只有访问权限，资源不属于迭代器 // 前置++ Self& operator++() { _node = _node->_next; return *this; } // 后置++ Self operator++(int) { // 拷贝构造 Self tmp(*this); _node = _node->_next; return tmp; } // 前置-- Self& operator--() { _node = _node->_prev; return *this; } // 后置-- Self operator--(int) { // 拷贝构造 Self tmp(*this); _node = _node->_prev; return tmp; } // 可读可写，引用返回 T& operator*() { return _node->_data; } bool operator!=(const Self& it) { return _node != it._node; } bool operator==(const Self& it) { return _node == it._node; } }; // 链表类 template<class T> class list { typedef ListNode<T> Node; public: typedef ListIterator<T> iterator; iterator begin() { // 匿名对象 return iterator(_head->_next); } iterator end() { // 匿名对象 return iterator(_head); } // 默认构造 list() { _head = new Node; _head->_next = _head; _head->_prev = _head; } void push_back(const T& x) { // 实例化新节点 Node* newnode = new Node(x); // 尾部节点 Node* tail = _head->_prev; // 修改新节点的指向 newnode->_next = _head; newnode->_prev = tail; // 修改指向新节点的指针 tail->_next = newnode; _head->_prev = newnode; } private: // 指向头节点的指针 Node* _head; }; // 测试区 }
我们来测试一下：
// 测试区 void test01() { 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()) { std::cout << *it << " "; ++it; } std::cout << std::endl; }
// test.cpp #include<iostream> #include"list.h" int main() { my::test01(); return 0; }
成功运行，我们的最基础的 list 框架可算是搭建好了。
接下来是 insert 。在 pos 位置前插入 val 。
void insert(iterator pos, const T& val) { // 目标节点 Node* cur = pos._node; // 待插入的节点 Node* newnode = new Node(val); // 目标节点的上一个节点 Node* prev = cur->_prev; newnode->_prev = prev; newnode->_next = cur; prev->_next = newnode; cur->_prev = newnode; }
还有 erase 。
iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; // 返回下一个节点的迭代器，避免迭代器失效 return iterator(next); }
有了 insert 和 erase ，我们就可以把 push_back 给复用一下，然后我们再将其他插入删除给顺便完成了。
void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_back() { // 必须是 -- ，不能是 - 1，因为迭代器不支持 - ，支持 -- erase(--end()); } void pop_front() { erase(begin()); }
来测试一下：
// 测试区 void test02() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_front(3); lt.push_front(4); lt.push_back(5); list<int>::iterator it = lt.begin(); while (it != lt.end()) { std::cout << *it << " "; ++it; } std::cout << std::endl; lt.pop_back(); lt.pop_front(); for (auto e : lt) { std::cout << e << " "; } std::cout << std::endl; }
#include<iostream> #include"list.h" int main() { my::test02(); return 0; }
同样符合预期。
size ：遍历一遍即可。
size_t size() const { Node* begin = _head; size_t num = 0; while (begin->_next != _head) { ++num; begin = begin->_next; } return num; }
list类 实现的差不多了，我们接着完善 迭代器类 。
我们新增一个自定义类型 A 。
struct A { int _a1; int _a2; A(int a1 = 0, int a2 = 0) :_a1(a1) ,_a2(a2) {} };
//测试区 void test03() { list<A> lt; A aa1(1, 1); // 有名对象 lt.push_back(aa1); // 匿名对象 lt.push_back(A(2, 2)); // 多参数的隐式类型转换 {} lt.push_back({ 3,3 }); for (auto e : lt) { std::cout << e << " "; } std::cout << std::endl; }
我们会发现不能运行。
因为内置类型可以使用流插入，自定义类型没写重载流插入就用不了，所以该怎么遍历呢？由于这里的成员变量都是共有的，所以直接访问成员变量就可以了。
// 测试区 void test03() { list<A> lt; A aa1(1, 1); // 有名对象 lt.push_back(aa1); // 匿名对象 lt.push_back(A(2, 2)); // 多参数的隐式类型转换 {} lt.push_back({ 3,3 }); list<A>::iterator it = lt.begin(); while (it != lt.end()) { std::cout << (*it)._a1 << (*it)._a2 << " "; ++it; } std::cout << std::endl; }
#include<iostream> #include"list.h" int main() { my::test03(); return 0; }
就可以遍历了。但是，既然可以 (*it)._a1 那就要可以 it->_a1 。所以我们还需要给迭代器类再重载一个运算符。
T* operator->() { return &_node->_data; }
有人会说，欸？这里怎么返回的是data的地址啊，那咋能访问到 _a1 啊？
void test04() { list<A> lt; A aa1(1, 1); // 有名对象 lt.push_back(aa1); // 匿名对象 lt.push_back(A(2, 2)); // 多参数的隐式类型转换 {} lt.push_back({ 3,3 }); list<A>::iterator it = lt.begin(); while (it != lt.end()) { std::cout << it->_a1 << it->_a2 << " "; ++it; } std::cout << std::endl; }
但确实能跑了。其实是这里编译器做了相关的优化。咱们写的 it->_a1 编译器自动识别成 it->->_a1 ，也就是 it.operator->()->_a1 ，就是 &_data->_a1 。这下终于理解了，原理编译器帮我们省略了一个 -> 。
我们来实现一个 const迭代器 。最简单粗暴的方式就是 再定义一个const迭代器类 然后将其 解引用重载函数 和 ->重载函数 前面加上 const 就能够完成任务，但是如果就这两处不同的话，那普通迭代器和const迭代器代码相似度也太高了，有点冗余，该怎么合并呢？可以用类模板。
// Ref就是引用返回，Ptr就是指针返回 template<class T, class Ref, class Ptr> struct ListIterator { // }; // list类里 typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T, const T&, const T*> const_iterator;
这就相当于：我们写了一个类模板，编译器帮我们实例化生成了普通迭代器类和const迭代器类 。
list 到这里基本差不多了，我们最后收尾一下。
list 的清理：
void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } ~list() { clear(); delete _head; _head = nullptr; }
判空：
bool empty() { return size() == 0; }
拷贝构造：
list(const list<T>& lt) { // 初始的头结点 _head = new Node; _head->_next = _head; _head->_prev = _head; for (auto& e : lt) { push_back(e); } }
复制重载：
void swap(list<T> lt) { std::swap(_head, lt._head); } list<T>& operator=(list<T> lt) { swap(lt); return *this; }
现在大部分接口都已经手到擒来了。
4. list模拟实现的代码整合
1. list.h
#pragma once #include<assert.h> namespace my { // struct 成员默认全公开 节点结构体 template<class T> struct ListNode { // 后继指针 ListNode<T>* _next; // 前驱指针 ListNode<T>* _prev; // 数据域 T _data; ListNode(const T& x = T()) :_next(nullptr) ,_prev(nullptr) ,_data(x) {} }; // 迭代器模板 template<class T, class Ref, class Ptr> struct ListIterator { typedef ListNode<T> Node; // self : 自己 typedef ListIterator<T, Ref, Ptr> Self; // 指向节点的指针 Node* _node; ListIterator(Node* node) :_node(node) {} // 没写拷贝构造，因为这是内置类型，默认生成的拷贝构造是浅拷贝，我们要的就是浅拷贝 // 也不需要写析构函数，迭代器只有访问权限，资源不属于迭代器 // 前置++ Self& operator++() { _node = _node->_next; return *this; } // 后置++ Self operator++(int) { // 拷贝构造 Self tmp(*this); _node = _node->_next; return tmp; } // 前置-- Self& operator--() { _node = _node->_prev; return *this; } // 后置-- Self operator--(int) { // 拷贝构造 Self tmp(*this); _node = _node->_prev; return tmp; } // 可读可写 //T& operator*() Ref operator*() { return _node->_data; } //T* operator->() Ptr operator->() { return &_node->_data; } bool operator!=(const Self& it) { return _node != it._node; } bool operator==(const Self& it) { return _node == it._node; } }; template<class T> class list { typedef ListNode<T> Node; public: typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T, const T&, const T*> const_iterator; iterator begin() { // 匿名对象 return iterator(_head->_next); } iterator end() { // 匿名对象 return iterator(_head); } // 迭代器指向的内容不能修改，const iterator不是我们要的const迭代器 const_iterator begin() const { return iterator(_head->_next); } const_iterator end() const { return iterator(_head); } // 默认构造 list() { _head = new Node; _head->_next = _head; _head->_prev = _head; } list(const list<T>& lt) { // 初始的头结点 _head = new Node; _head->_next = _head; _head->_prev = _head; for (auto& e : lt) { push_back(e); } } void swap(list<T> lt) { std::swap(_head, lt._head); } list<T>& operator=(list<T> lt) { swap(lt); return *this; } bool empty() { return size() == 0; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } ~list() { clear(); delete _head; _head = nullptr; } //void push_back(const T& x) //{ // // 实例化新节点 // Node* newnode = new Node(x); // // 尾部节点 // Node* tail = _head->_prev; // // 修改新节点的指向 // newnode->_next = _head; // newnode->_prev = tail; // // 修改指向新节点的指针 // tail->_next = newnode; // _head->_prev = newnode; //} void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_back() { // 必须是 -- ，不能是 - 1，因为迭代器不支持 - ，支持 -- erase(--end()); } void pop_front() { erase(begin()); } iterator insert(iterator pos, const T& val) { // 目标节点 Node* cur = pos._node; // 待插入的节点 Node* newnode = new Node(val); // 目标节点的上一个节点 Node* prev = cur->_prev; newnode->_prev = prev; newnode->_next = cur; prev->_next = newnode; cur->_prev = newnode; return iterator(newnode); } iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; // 返回下一个节点的迭代器，避免迭代器失效 return iterator(next); } size_t size() const { Node* begin = _head; size_t num = 0; while (begin->_next != _head) { ++num; begin = begin->_next; } return num; } private: // 指向头节点的指针 Node* _head; }; struct A { int _a1; int _a2; A(int a1 = 0, int a2 = 0) :_a1(a1) ,_a2(a2) {} }; void test01() { 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()) { std::cout << *it << " "; ++it; } std::cout << std::endl; } void test02() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_front(3); lt.push_front(4); lt.push_back(5); list<int>::iterator it = lt.begin(); while (it != lt.end()) { std::cout << *it << " "; ++it; } std::cout << std::endl; lt.pop_back(); lt.pop_front(); for (auto e : lt) { std::cout << e << " "; } std::cout << std::endl; std::cout << lt.size(); } void test03() { list<A> lt; A aa1(1, 1); // 有名对象 lt.push_back(aa1); // 匿名对象 lt.push_back(A(2, 2)); // 多参数的隐式类型转换 {} lt.push_back({ 3,3 }); list<A>::iterator it = lt.begin(); while (it != lt.end()) { std::cout << (*it)._a1 << (*it)._a2 << " "; ++it; } std::cout << std::endl; } void test04() { list<A> lt; A aa1(1, 1); // 有名对象 lt.push_back(aa1); // 匿名对象 lt.push_back(A(2, 2)); // 多参数的隐式类型转换 {} lt.push_back({ 3,3 }); list<A>::iterator it = lt.begin(); while (it != lt.end()) { std::cout << it->_a1 << it->_a2 << " "; ++it; } std::cout << std::endl; } }
2. test.cpp
#include<iostream> #include"list.h" int main() { my::test03(); return 0; }
