3.list模拟实现完整代码
下面就看看整体的代码，个人感觉只有这样整体观察才能理解更多·。因为一些比如push_back、push_front、pop_back、pop_front我们在实现string、vector的时候已经描述过，都是以复用的形式出现的，整体看才会明白
3.1 list.h
#pragma once namespace cfy { template<class T> struct list_node { list_node<T>* _next;//不加<T>也没错，但是写上好一些 list_node<T>* _prev; T _data; list_node(const T& x)//构造 :_next(nullptr) , _prev(nullptr) , _data(x) {} }; //typedef __list_iterator<T, T&, T*> iterator; //typedef __list_iterator<T, const T&, const T*> const_iterator; template<class T, class Ref, class Ptr>//模仿大佬在STL中的写法，能避免副本造成的代码冗余 struct __list_iterator//封装成类的迭代器 { typedef list_node<T> node; typedef __list_iterator<T, Ref, Ptr> Self; node* _pnode; __list_iterator(node* p) :_pnode(p) {} // iterator it // *it // ++it Ref operator*()//const迭代器看这个 { return _pnode->_data; } Ptr operator->()//const迭代器看这个 { return &_pnode->_data; } 那么能不能重载一个T&？ 像下面： const iterator *it ++it 不能调++了，因为const不能调用非const，那这个时候可不可以将++的运算符继续重载？ 不能，++是写的函数，不可能把他变成const， 因此像下面这样重载，可以解引用，但是不能++， 所以换思路，可以将迭代器这整个类再写一个const版本的出来，就是会产生代码冗余 //const T& operator*() const //{ // return _pnode->_data; //} Self& operator++()//前置 { _pnode = _pnode->_next; return *this; } Self& operator++(int)//后置 //自己加的，这里写成T对于自己加的Pos会报错 { //Self it = *this; Self it(*this); _pnode = _pnode->_next; return it; } Self& operator--()//前置 { _pnode = _pnode->_prev; return *this; } bool operator!=(const Self& it) const { return _pnode != it._pnode; } bool operator==(const Self& it) const { return _pnode == it._pnode; } }; template<class T> class list { typedef list_node<T> node; public: typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; //虽然是一个类模板，但是T不同就不是一个类 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() { //iterator it(_head); //return it; //直接利用匿名对象更为便捷 return iterator(_head); } void empty_initialize() { _head = new node(T()); _head->_next = _head; _head->_prev = _head; _size = 0;//实现计算动态大小 } list() // 不是list<T>的原因：构造函数和类名相同，和类型list<T>不同 { empty_initialize(); } ~list() { clear(); delete _head; _head = nullptr; } lt2(lt1) 传统写法 //list(const list<T>& lt)//实现const迭代器之后就没有错误了 //{ // empty_initialize(); // for (const auto& e : lt) // { // push_back(e); // } //} //list<T>& operator=(const list<T>& lt)//实现const迭代器之后就没有错误了 //{ // if (this != <) // { // clear(); // for (const auto& e : lt) // { // push_back(e); // } // } // return *this; //} void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } template <class InputIterator> list(InputIterator first, InputIterator last)//迭代器区间构造，和vector的对应 { empty_initialize(); while (first != last) { push_back(*first); ++first; //first++; } } // 拷贝构造的现代写法 list(const list<T>& lt) //list(const list& lt) 官方库是这样写的，也可以，语法设计问题，但是不建议自己这样写 { empty_initialize();//初始化头结点，防止交换后tmp野指针不能正常的调用析构 list<T> tmp(lt.begin(), lt.end()); swap(tmp); } //lt3 = lt list<T>& operator=(list<T> lt)//不能加引用，lt是调用拷贝构造生成的 //list& operator=(list lt) 官方库是这样写的，也可以 { swap(lt); return *this; } size_t size() const//增加一个计数的成员，以空间换时间 { return _size; } bool empty() { return _size == 0; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } _size = 0; } void push_back(const T& x) { /*node* newnode = new node(x); node* tail = _head->_prev; tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode;*/ insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_front() { erase(begin()); } void pop_back() { erase(--end()); } iterator insert(iterator pos, const T& x) { node* newnode = new node(x); node* cur = pos._pnode; node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; cur->_prev = newnode; newnode->_next = cur; ++_size; return iterator(pos); } iterator erase(iterator pos) { assert(pos != end()); node* prev = pos._pnode->_prev; node* next = pos._pnode->_next; prev->_next = next; next->_prev = prev; delete pos._pnode; --_size; return iterator(next); } private: node* _head; size_t _size; }; void test_list1() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.insert(++lt.begin(), 10); //iterator 1、内嵌类型 2、像指针一样 list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; for (auto e : lt) { cout << e << " "; } cout << endl; } void test_list2() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_front(10); lt.push_front(20); lt.push_front(30); lt.pop_back(); lt.pop_back(); lt.pop_back(); lt.pop_front(); lt.pop_front(); for (auto e : lt) { cout << e << " "; } cout << endl; } void test_list3() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); for (auto e : lt) { cout << e << " "; } cout << endl; list<int> lt1(lt);//默认是浅拷贝,指向同一块 lt.pop_back(); lt.pop_back(); for (auto e : lt1) { cout << e << " "; } cout << endl; list<int> lt3 = lt1; for (auto e : lt3) { cout << e << " "; } } //const T* p1 //T* const p2; //const迭代器类似p1的行为，保护指向的对象不被修改，迭代器本身可以修改 //void print_list(const list<int>& lt) //{ // //const list<int>::iterator cit = lt.begin(); // //不符合const迭代器的行为，因为他保护迭代器本省不能修改，那么我们也就不能用++迭代器 //} //void print_list(const list<int>& lt) //{ // list<int>::const_iterator it = lt.begin(); //重载了，找的另一个类的迭代器 // while (it != lt.end()) // { // (*it) += 2;//不能写 // cout << *it << " "; // ++it; // } // cout << endl; //} void test_list4() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); list<int>::iterator it = lt.begin(); while (it != lt.end()) { (*it) += 2; cout << *it << " "; ++it; //it++; } cout << endl; //print_list(lt); list<int> lt1(lt); for (auto e : lt1) { cout << e << " "; } cout << endl; list<int> lt2 = lt; for (auto e : lt2) { cout << e << " "; } cout << endl; cout << lt.size() << endl; } struct Pos { int _row; int _col; Pos(int row=0, int col=0) :_row(row) ,_col(col) {} }; void print_list(const list<Pos>& lt) { list<Pos>::const_iterator it = lt.begin(); //重载了，找的另一个类的迭代器 while (it != lt.end()) { //it->_row++; 增加第三个模板参数 cout << it->_row << ":" << it->_col << endl; ++it; } cout << endl; } void test_list5() { list<Pos> lt; Pos p1(1, 1); lt.push_back(p1); lt.push_back(p1); lt.push_back(p1); lt.push_back(Pos(2, 3)); lt.push_back(Pos(2, 3)); list<Pos>::iterator it = lt.begin(); while (it != lt.end()) { //cout << (*it)._row << ":" << (*it)._col << endl; cout << it->_row << ":" << it->_col << endl;//编译器为了可读性，做了特殊处理，省略了一个->, //那么省略之前应该是it->->_row //cout << it.operator->()->_col << ":" << it.operator->()->_row << endl; ++it; } cout << endl; print_list(lt); } } //实现const迭代器的两种方法： // 1. 重新写一个类，里面只有一个函数是不一样的，目的为了const // 2. 利用模板！ // 类名和类型的问题： // 普通类 类名 等价于 类型 // 类模板 类名 不等价于 类型 // 如： list模板 类名list 类型list<T> // 类模板里面可以用类名代表类型，但是不建议那么用 //vector和list对比： //vector优点： //1、下标随机访问 //2、尾插尾删效率高（但不明显） //3、CPU高速缓存命中率高：因为物理空间连续 // //vector缺点： //1、前面部分插入删除效率低 //2、扩容有消耗，还存在一定空间浪费，扩容开多了浪费，开少了频繁扩容 // //list优点： //1、按需申请释放，无需扩容 //2、任意位置插入删除O(1)，前提是已经知道这个位置了，查找是O(n) // //list缺点： //1、不支持下标的随机访问 //2、CPU高速缓存命中率低 // // //总结：vector和list不是敌对关系，而是互补配合 //总结迭代器失效问题： //vector -> insert/erase //list -> erase // //string有没有迭代器失效？->insert/erase失效，和vector类似 //但一般不关注string的迭代器失效，因为string insert/erase常用接口函数都是下标支持，迭代器支持用的很少
3.2Test.cpp
#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<algorithm> #include<vector> #include<list> #include<assert.h> using namespace std; #include"list.h" void test_list1() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; it++; } cout << endl; lt.push_front(10); lt.push_front(20); lt.push_front(30); lt.push_front(40); for (auto e : lt) { cout << e << " "; } cout << endl; lt.pop_back(); lt.pop_back(); lt.pop_front(); lt.pop_front(); for (auto e : lt) { cout << e << " "; } cout << endl; } void test_list2() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); auto pos = find(lt.begin(), lt.end(), 3); if (pos != lt.end()) { //insert之后pos是否失效呢？不失效,因为链表不存在挪动空间和扩容的问题 lt.insert(pos, 30); } cout << *pos << endl; //(*pos)++; for (auto e : lt) { cout << e << " "; } cout << endl; lt.erase(pos);//erase之后，pos就失效了，因为空间都被干掉了 //cout << *pos << endl; for (auto e : lt) { cout << e << " "; } cout << endl; } //Operations: void test_list3() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(5); lt.push_back(3); lt.push_back(4); lt.push_back(4); lt.push_back(4); lt.push_back(5); lt.push_back(6); lt.push_back(7); lt.push_back(6); for (auto e : lt) { cout << e << " "; } cout << endl; lt.remove(3); lt.remove(30); for (auto e : lt) { cout << e << " "; } cout << endl; lt.sort(); //迭代器·功能分类 //1、单向 ++ //2、双向 ++ -- list //3、随机 + - for (auto e : lt) { cout << e << " "; } cout << endl; //去重：建立在有序的基础上 lt.unique(); for (auto e : lt) { cout << e << " "; } cout << endl; } void test_op() { srand(time(0)); const int N = 10000000; vector<int> v; v.reserve(N); list<int> lt1; list<int> lt2; for (int i = 0; i < N; ++i) { auto e = rand(); //v.push_back(e); lt1.push_back(e); lt2.push_back(e); } // 拷贝到vector排序，排完以后再拷贝回来 int begin1 = clock(); for (auto e : lt1) { v.push_back(e); } sort(v.begin(), v.end()); size_t i = 0; for (auto& e : lt1) { e = v[i++]; } int end1 = clock(); int begin2 = clock(); // sort(lt.begin(), lt.end()); lt2.sort(); int end2 = clock(); printf("vector sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2); } int main() { //test_op(); cfy::test_list5(); return 0; }
下面也是上述代码实现的链接。
C++/list模拟实现最终版 · 蓝桉/CPP - 码云 - 开源中国 (gitee.com)
4.模拟实现的注意事项
4.1深拷贝的问题
对于vector，我们知道有深浅拷贝的问题，即浅拷贝会造成析构两次导致出现错误，但我们此次的list实现方式
则不存在这种问题：
4.2类名和类型的问题
普通类： 类名等价于类型
类模板： 类名不等于类型
举例：list模板类名为list，但是实际上的类型是list，这两个在具体函数返回值还是有区别的，但是在类模板里面可以直接用类名来代替类型，不过不建议这么用，因为对其他人不好理解。举个例子看看。
例1:
就是我们节点类这里，指针直接不写也是可以的。
例2： 这个就看代码吧
// 赋值运算符重载 list<T>& operator=(list<T> lt) { swap(lt); return *this; }
也就是说这个在类中也可以变成这样，这也是正确的：
// 赋值运算符重载写法2(赋值运算符重载都可以这么干) list& operator=(list lt) { swap(lt); return *this; }
5.vector与list的优缺点
1. vector优点与缺点
优点：
- 支持下标随机访问。
- 尾删尾插效率高（但不明显）。
- CPU高速缓存命中率高：因为物理空间连续。
缺点：
- 前面部分插入删除效率低。
- 扩容有消耗，还存在一定的空间浪费，扩容开多了浪费，开少了浪费空间。
2. list优点与缺点
优点：
- 按需申请释放，无需扩容。
- 任意位置插入删除是O(1)，前提是已经知道这个位置了，查找是O(n)。
缺点：
- 不支持下标的随机访问
- CPU高速缓存命中率低
因此vector与list不是相互替代的关系，而是互补配合。
