Ⅳ. list 的拷贝构造和赋值重载
0x00 引入：list 的同样涉及深浅拷贝问题
❓ 思考：这里的拷贝构造是深拷贝还是浅拷贝？
void test_list4() { list<int> L1; L1.push_back(1); L1.push_back(2); L1.push_back(3); list<int> L2(L1); for (auto e : L2) cout << e << " "; }
🚩 运行结果：
💡 这里默认生成的拷贝构造是浅拷贝：
比如这里 浅拷贝导致 L1 和 L2 指向同一块地址，析构的时候会导致一块空间被释放两次。
这些知识我们在之前讲解深浅拷贝的时候就说过，这里没崩仅仅是因为我们还没设计析构。
这里只是勉强 "逃过一杰" 。
综上所述，我们这里依然要自己去实现一个拷贝构造，去完成 "深拷贝" 。
我们下面实现一下 ~list，再回来看看。
0x01 clear 清空链表中所有数据
在实现链表 list 的析构函数前，为了方便清空，我们先实现一下 clear()
💬 代码：清空链表数据
/* 清空链表所有数据 */ void clear() { // 利用迭代器去遍历整个链表 iterator cur = begin(); while (cur != end()) { iterator del = cur++; // 巧妙利用后置++的特性 delete del._node; // 删除当前结点，后置++生效 } // 删完之后我们还需要将其恢复到初始状态 _pHead->_next = _pHead; _pHead->_prev = _pHead; }
🔨 测试代码：
void test_list5() { list<int> L; L.push_back(1); L.push_back(2); L.push_back(3); cout << "删除前："; print_list(L); cout << "删除后："; L.clear(); print_list(L); }
🚩 运行结果：
当然，这里的删除结点我们也可以用 erase 去完成。
用 erase 可以省去我们将其恢复 _pHead 的前驱和后继指向自己的操作。
删除掉最后一个有效元素后， erase 的 "缝合操作" 自然会做到：
💬 代码：用迭代器 + erase 的方式去逐个访问并删除每个节点
void clear() { iterator cur = begin(); while (cur != end()) { iterator del = cur++; erase(del); // 直接反复调用erase删除结点 } }
⚡ 简化：还可以进一步简化：
/* 清空链表所有数据 */ void clear() { iterator cur = begin(); while (cur != end()) { // iterator del = cur++; erase(cur++); // 直接反复调用erase删除结点 } }
0x02 ~list 析构
实现了 clear 后，我们再去实现 list 的析构函数就很简单了。
我们只需要把哨兵位头结点 _pHead 给干掉就行了，并且记得要置成空指针。
💬 代码：析构函数的实现
~list() { // 清空链表有效数据 clear(); // 干掉头结点 delete _pHead; _pHead = nullptr; }
实现好了析构函数，我们再回过头来测刚才 "逃过一劫" 的浅拷贝导致的两个结点指向同一地址的问题，现在问题就变得严重起来了，因为它会被析构两次：
void test_list4() { list<int> L1; L1.push_back(1); L1.push_back(2); L1.push_back(3); list<int> L2(L1); for (auto e : L2) cout << e << " "; }
🚩 运行结果：（崩溃）
刚才得益于我们还没有去实现析构函数，让浅拷贝带来的问题 "逃过一杰" 。
但是现在可谓是在劫难逃了 ——
自动生成的拷贝构造是浅拷贝，为了解决这个问题，我们需要手动实现一个深拷贝的拷贝构造！
0x03 拷贝构造的实现
💬 代码：传统写法
/* 拷贝构造：L2(L1) */ list(const list<T>& L) { _pHead = new Node(); _pHead->_next = _pHead; _pHead->_prev = _pHead; for (auto e : L) { push_back(e); } }
💬 代码：现代写法
template<class InputIterator> list(InputIterator first, InputIterator last) { _pHead = new Node(); _pHead->_next = _pHead; _pHead->_prev = _pHead; while (first != last) { push_back(*first); first++; } } /* 拷贝构造（现代写法）：L2(L1) */ list(const list<T>& L) { _pHead = new Node(); _pHead->_next = _pHead; _pHead->_prev = _pHead; list<T> tmp(L.begin(), L.end()); swap(_pHead, tmp._pHead); // 交换两个结点的指针 }
0x04 赋值重载
💬 代码：传统写法
/* 赋值：L2 = L1 */ list<T>& operator=(list<T> L) { if (this != &L) { clear(); for (auto e : L) { push_back(e); } } return *this; }
💬 代码：现代写法
/* 赋值（现代写法）：L2 = L1 */ list<T>& operator=(list<T> L) { swap(_pHead, L._pHead); return *this; }
Ⅴ. 完整代码
0x00 list.h
（注：未采用申明与定义分离的形式）
#define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include <assert.h> using namespace std; namespace chaos { /* 定义结点 */ template<class T> struct ListNode { T _data; // 用来存放结点的数据 ListNode<T>* _next; // 指向后继结点的指针 ListNode<T>* _prev; // 指向前驱结点的指针 ListNode(const T& data = T()) // 全缺省构造（初始化） : _data(data) , _next(nullptr) , _prev(nullptr) {} }; /* 定义迭代器 */ template<class T, class Ref, class Ptr> struct __list_iterator { typedef ListNode<T> Node; typedef __list_iterator<T, Ref, Ptr> self; // 为了方便我们重命名为self typedef Ref reference; typedef Ptr pointer; Node* _node; __list_iterator(Node* x) : _node(x) {} /* 解引用 */ Ref operator*() { return _node->_data; // 返回结点的数据 } Ptr operator->() { return &_node->_data; } /* ++it */ self& operator++() { _node = _node->_next; // 让 _node 指向下一个结点 return *this; // 返回加加后的值 } /* it++ */ self operator++(int) { self tmp(*this); // 拷贝构造一个tmp存储原来的值 _node = _node->_next; return tmp; } /* != */ bool operator!=(const self& it) { return _node != it._node; // 它们结点的指针不一样吗？T or F } /* --it */ self& operator--() { _node = _node->_prev; return *this; } /* it-- */ self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } }; ///* 定义const迭代器 */ //template<class T> //struct __const_list_iterator { // typedef ListNode<T> Node; // Node* _node; // __const_list_iterator(Node* x) // : _node(x) // {} // /* 解引用 */ // const T& operator*() { // return _node->_data; // 返回结点的数据 // } // /* ++it */ // __const_list_iterator<T>& operator++() { // _node = _node->_next; // 让 _node 指向下一个结点 // return *this; // 返回加加后的值 // } // /* it++ */ // __const_list_iterator<T> operator++(int) { // __const_list_iterator<T> tmp(*this); // 拷贝构造一个tmp存储原来的值 // _node = _node->_next; // return tmp; // } // /* != */ // bool operator!=(const __const_list_iterator<T>& it) { // return _node != it._node; // 它们结点的指针不一样吗？T or F // } // /* --it */ // __const_list_iterator<T>& operator--() { // _node = _node->_prev; // return *this; // } // /* it-- */ // __const_list_iterator<T> operator--(int) { // __list_iterator<T> tmp(*this); // _node = _node->_prev; // return tmp; // } //}; /* 定义链表 */ template<class T> class list { typedef ListNode<T> Node; // 重命名为Node public: /* 迭代器 */ typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; iterator begin() { return iterator(_pHead->_next); } iterator end() { return iterator(_pHead); } const_iterator begin() const { return const_iterator(_pHead->_next); } const_iterator end() const { return const_iterator(_pHead); } /* 构造函数：初始化头结点 */ list() { _pHead = new Node(); _pHead->_next = _pHead; _pHead->_prev = _pHead; } list(size_t n, const T& val = T()) { // 初始化n个结点 _pHead = new Node(); _pHead->_next = _pHead; _pHead->_prev = _pHead; for (size_t i = 0; i < n; i++) { push_back(val); } } list(int n, const T& val = T()) { // 初始化n个结点 _pHead = new Node(); _pHead->_next = _pHead; _pHead->_prev = _pHead; for (int i = 0; i < n; i++) { push_back(val); } } template<class InputIterator> list(InputIterator first, InputIterator last) { _pHead = new Node(); _pHead->_next = _pHead; _pHead->_prev = _pHead; while (first != last) { push_back(*first); first++; } } /* 拷贝构造（现代写法）：L2(L1) */ list(const list<T>& L) { _pHead = new Node(); _pHead->_next = _pHead; _pHead->_prev = _pHead; list<T> tmp(L.begin(), L.end()); swap(_pHead, tmp._pHead); } /* 拷贝构造：L2(L1) */ /*list(const list<T>& L) { _pHead = new Node(); _pHead->_next = _pHead; _pHead->_prev = _pHead; for (auto e : L) { push_back(e); } }*/ ///* 赋值：L2 = L1 */ //list<T>& operator=(list<T> L) { // if (this != &L) { // clear(); // for (auto e : L) { // push_back(e); // } // } // return *this; //} /* 赋值（现代写法）：L2 = L1 */ list<T>& operator=(list<T> L) { swap(_pHead, L._pHead); return *this; } /* 在pos位置前插入 */ void insert(iterator pos, const T& x) { Node* cur = pos._node; // 找到pos位置的结点 Node* cur_prev = cur->_prev; // 因为要在pos位置前插入，所以要找到当前pos位置的前一个结点 Node* new_node = new Node(x); // 创建新节点 // 缝合： cur_prev <-> new_node <-> cur cur_prev->_next = new_node; new_node->_prev = cur_prev; new_node->_next = cur; cur->_prev = new_node; } /* 尾插：push_back */ void push_back(const T& x) { //Node* pTail = _pHead->_prev; // pHead的前驱就是pTail //Node* new_node = new Node(x); // 创建新结点（会调用构造，自动创建） // //pTail->_next = new_node; //new_node->_prev = pTail; //new_node->_next = _pHead; //_pHead->_prev = new_node; insert(end(), x); // 在end(头结点)前插入，即尾插 } /* 头插：push_front */ void push_front(const T& x) { insert(begin(), x); // 在begin（头结点的下一个结点）前插入，即头插 } /* 任意位置删除 */ iterator erase(iterator pos) { assert(pos != end()); // 防止头结点被删除 Node* cur = pos._node; // 找到pos位置的结点 Node* cur_prev = cur->_prev; // 找到pos的前驱 Node* cur_next = cur->_next; // 找到pos的后继 // 删除cur delete cur; // 缝合： cur_prev <-> cur(删) <-> cur_next cur_prev->_next = cur_next; cur_next->_prev = cur_prev; return iterator(cur_next); } /* 尾删 */ void pop_back() { erase(--end()); // 删除最后一个元素，即尾结点 } /* 头删 */ void pop_front() { erase(begin()); // 删除头结点的下一个结点（即begin位置的结点） } /* 清空链表所有数据 */ void clear() { 利用迭代器去遍历整个链表 //iterator it = begin(); //while (it != end()) { // iterator del = it++; // 巧妙利用后置++的特性 // delete del._node; // 删除当前结点，后置++生效 //} 删完之后我们还需要将其恢复到初始状态 //_pHead->_next = _pHead; //_pHead->_prev = _pHead; iterator it = begin(); while (it != end()) { // iterator del = it++; erase(it++); // 直接反复调用erase删除结点 } } ~list() { // 清空链表有效数据 clear(); // 干掉头结点 delete _pHead; _pHead = nullptr; } private: Node* _pHead; }; void print_list(const list<int>& L) { list<int>::const_iterator it = L.begin(); while (it != L.end()) { // *it = 100; cout << *it << " "; it++; } cout << endl; } void test_list1() { list<int> L; L.push_back(1); L.push_back(2); L.push_back(3); L.push_back(4); list<int>::iterator it = L.begin(); while (it != L.end()) { *it *= 2; cout << *it << " "; it++; } cout << endl; } void test_list2() { list<int> L; L.push_back(2); L.push_back(4); L.push_back(6); L.push_back(8); print_list(L); } struct Date { int _year; int _month; int _day; Date(int year = 1, int month = 1, int day = 1) : _year(year) , _month(month) , _day(day) {} }; void test_list3() { list<Date> L; L.push_back(Date(2022, 5, 1)); L.push_back(Date(2022, 5, 2)); L.push_back(Date(2022, 5, 3)); list<Date>::iterator it = L.begin(); while (it != L.end()) { cout << it->_year << "/" << it->_month << "/" << it->_day << endl; it++; } cout << endl; } void test_list4() { list<int> L1; L1.push_back(1); L1.push_back(2); L1.push_back(3); list<int> L2(L1); for (auto e : L2) cout << e << " "; } void test_list5() { list<int> L; L.push_back(1); L.push_back(2); L.push_back(3); cout << "删除前："; print_list(L); cout << "删除后："; L.clear(); print_list(L); } }
0x01 test.cpp
#define _CRT_SECURE_NO_WARNINGS 1 #include "list.h" int main(void) { chaos::test_list1(); return 0; }
0x02 reverse_iterator.h
#define _CRT_SECURE_NO_WARNINGS 1 #include "list.h" namespace chaos { // Iterator是哪个容器的迭代器，reverse_iterator<Iterator>就可以 // 适配出哪个容器的反向迭代器。复用的体现 //template <class Iterator, class Ref, class Ptr> /* 定义反向迭代器 */ template <class Iterator> class reverse_iterator { typedef reverse_iterator<Iterator, Ref, Ptr> self; typedef typename Iterator::Ref reference; typedef typename Iterator::Ptr pointer; public: reverse_iterator(Iterator it) :_it(it) {} Ref operator*() { //return *_it; Iterator prev = _it; return *--prev; } Ptr operator->() { return &operator*(); } self& operator++() { --_it; return *this; } self& operator--() { ++_it; return *this; } bool operator!= (const self& rit) const { return _it != rit._it; } private: Iterator _it; }; }
