1.list 底层
list为任意位置插入删除的容器，底层为带头双向循环链表
begin() 代表第一个结点，end()代表最后一个结点的下一个
2. list的模拟实现
1. list_node 类设计
template<class T> struct list_node { list_node<T>* _next; list_node<T>* _prev; T _data; };
C++中，Listnode作为类名，而next和prev都是类指针，指针引用成员时使用->，而对象引用成员时使用 .
通过显示实例化，将两个类指针指定类型为T
2. list类如何调用类型
Listnode 代表类型
Listnode 代表类名 + 模板参数 才是类型
而_head 以及创建新节点前都需加上类型
3 .push_back(正常实现)
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; }
当我们想要创建一个节点时，需要调用node的构造函数
typedef list_node node ，node是由 list_node 类提供的
list_node(const T& x=T())//list类的构造函数 :_next(nullptr) , _prev(nullptr) , _data(x) { }
最好在构造函数处提供全缺省，对于内置类型int可以使用0，但对于自定义类型来说就不可以，所以为了满足泛型的要求，使用匿名对象调用默认构造函数
4. 迭代器的实现
若在数组上有一个int类型的指针，解引用是int类型的数据，再++可以加载下一个位置，因为物理空间是连续的
同样若在链表上，解引用类型为 node，再++不能到下一个节点，因为物理空间不连续
所以构造迭代器通过封装节点的指针来进行构造 (后面会讲)
第一个模板参数T
创建一个_list_iterator的类，来实现迭代器功能
template<class T> struct _list_iterator { typedef list_node<T> node; typedef _list_iterator<T> self; node* _node; _list_iterator(node* n) :_node(n) { } T& operator*()//解引用 { return _node->_data; } _list_iterator<T>& operator++()//返回迭代器 { _node = _node->_next;//指向下一个节点 return *this; } bool operator!=(const self&s) { return _node != s._node; } };
在list类中，调用迭代器实现begin()和end()功能
typedef _list_iterator<T,T&,T*> iterator，
通过typedef 将_list_node类模板定义为iterator
iterator begin() { return iterator(_head->_next);//通过匿名对象访问第一个数据 } iterator end() { return iterator(_head);//通过匿名对象访问最后一个数据的下一个 }
在list类中实现begin()和end()，内部调用_list_node类的构造函数
const迭代器
假设第一个代表的是T * ，而第二个代表的 T * const，保护迭代器本身不可以被修改，而我们想要保护迭代器指向的内容不可被修改即 const T*
复制_list_iterator类中的内容，并将名字修改为const_list_iterator
只需修改*operator类型为cosnt T& ，说明解引用后的数据返回不能被修改
template<class T> struct _list_const_iterator { typedef list_node<T> node; typedef _list_const_iterator<T> self; node* _node; _list_const_iterator(node* n) :_node(n) { } const T& operator*()//解引用 { return _node->_data; } self& operator++()//前置++ { _node = _node->_next;//指向下一个节点 return *this; } self& operator++(int)//后置++ { self ret = *this; _node = _node->_next; return ret; } self& operator--()//前置-- { _node = _node->_prev; return *this; } self& operator--(int)//后置-- { self ret = *this; _node = _node->_prev; return ret; } bool operator!=(const self& s)//!= { return _node != s._node; } bool operator==(const self& s)//== { return _node == s._node; } };
第二个模板参数Ref
迭代器和const迭代器只有 *operator 的返回值不同，只需在模板中添加一个参数即可使用一个迭代器实现迭代器和const 迭代器的功能
第三个模板参数Ptr
对于内置类型int使用解引用找到对应数据，而自定义类型需使用->寻找下一个节点
AA作为自定义类型，想要找到下一个节点需要使用->，在迭代器中 重载 - >
it->_a1，实际上是 it->->_a1，
it->返回值为AA* ,再通过这个指针使用->指向_a1
但是为了增强可读性，省略了一个->
it->_a1 实际上为 it.operator->()->._a1
对list封装的理解
在不考虑封装的情况下，两者等价
从物理空间上来看，it与pnode都是指向1的地址
pnode作为一个原生指针，解引用指针就会拿到这个地址，找到这个地址指向空间的内容
++pnode，找到下一个节点的地址，但是下一个节点不一定是要的节点
*it 识别成为自定义类型就会调用函数
5. insert
void insert(iterator pos,const T&x)//在pos位置前插入x { node* cur = pos._node; node* prev = cur->_prev; node* newnode = new node(x); prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; }
6.push_back与 push_front(复用)
两者都可以通过复用 insert的方式实现
void push_back(const T&x)//尾插 { /*node* tail = _head->_prev; node* newnode = new node(x); tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode;*/ insert(end(), x); } void push_front(const T&x)//头插 { insert(begin(), x); }
7. erase
void erase(iterator pos)//删除pos位置 { //头节点不可以删除 assert(pos != end()); node* cur = pos._node; node* prev = cur->_prev; node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; }
由于头节点不可以删除，所以使用assert断言的方式
8. pop_back与pop_front (复用)
void pop_back()//尾删 { erase(--end()); } void pop_front()//头删 { erase(begin()); }
9. clear 清空数据
void clear()//清空数据 //但是要注意不要把head清掉 { iterator it = begin(); while (it != end()) { it=erase(it);//为了防止迭代器失效设置返回值 //返回值为当前节点的下一个 } }
迭代器失效是指迭代器所指向的节点失效 即节点被删除了
erase函数执行后，it所指向的节点被删除，因此it无效，在下一次使用it时，必须先给it赋值
为了防止迭代器失效所以使erase设置返回值，返回值为当前节点的下一个
10. 迭代器区间构造
void empty_init() { _head = new node; _head->_next = _head; _head->_prev = _head; } template <class Iterator> list(Iterator first, Iterator last) { empty_init(); while (first != last) { push_back(*first); ++first; } }
想要尾插的前提时，需要有头节点的存在，所以设置一个函数对头节点初始化
12. 拷贝构造
传统写法
void empty_init() { _head = new node; _head->_next = _head; _head->_prev = _head; } list(const list<T>& It)//拷贝构造 传统写法 { empty_init();//初始化头节点 for (auto e : It) { push_back(e); } }
现代写法
void swap(list<T>& tmp) { std::swap(_head, tmp._head); } list(const list<T>& It)//拷贝构造现代写法 { empty_init();//将头节点初始化 list<T> tmp(It.begin(), It.end()); swap(tmp); }
通过调用std中的swap来达到交换的目的
13. 赋值
void swap(list<T>& tmp) { std::swap(_head, tmp._head); } list<T>& operator=(list<T> It) { swap(It); return *this; }
参数不可以使用 list &，虽然可以达到赋值的目的，但是It的值也会发生改变
3.完整代码
#include<iostream> #include<list> #include<assert.h> using namespace std; namespace yzq { template<class T> struct list_node { list_node<T>* _next; list_node<T>* _prev; T _data; list_node(const T& x=T())//构造函数 :_next(nullptr) , _prev(nullptr) , _data(x) { } }; //迭代器 template<class T,class Ref,class Ptr> struct _list_iterator { typedef list_node<T> node; typedef _list_iterator<T,Ref,Ptr> self; node* _node; _list_iterator(node* n) :_node(n) { } Ref operator*()//解引用 { return _node->_data; } Ptr operator->()//-> { return &_node->_data; } self& operator++()//前置++ { _node = _node->_next;//指向下一个节点 return *this; } self& operator++(int)//后置++ { self ret = *this; _node = _node->_next; return ret; } self& operator--()//前置-- { _node = _node->_prev; return *this; } self& operator--(int)//后置-- { self ret = *this; _node = _node->_prev; return ret; } bool operator!=(const self&s)//!= { return _node != s._node; } bool operator==(const self& s)//== { return _node == s._node; } }; //const迭代器 //template<class T> //struct _list_const_iterator //{ // typedef list_node<T> node; // typedef _list_const_iterator<T> self; // node* _node; // _list_const_iterator(node* n) // :_node(n) // { // } // const T& operator*()//解引用 // { // return _node->_data; // } // self& operator++()//前置++ // { // _node = _node->_next;//指向下一个节点 // return *this; // } // self& operator++(int)//后置++ // { // self ret = *this; // _node = _node->_next; // return ret; // } // self& operator--()//前置-- // { // _node = _node->_prev; // return *this; // } // self& operator--(int)//后置-- // { // self ret = *this; // _node = _node->_prev; // return ret; // } // bool operator!=(const self& s)//!= // { // return _node != s._node; // } // bool operator==(const self& s)//== // { // return _node == s._node; // } //}; 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;//const迭代器 //typedef _list_const_iterator<T> const_iterator; void empty_init() { _head = new node; _head->_next = _head; _head->_prev = _head; } list()//构造函数 { empty_init(); } template <class Iterator> list(Iterator first, Iterator last) { empty_init(); while (first != last) { push_back(*first); ++first; } } //list(const list<T>& It)//拷贝构造 //{ // empty_init();//初始化头节点 // for (auto e : It) // { // push_back(e); // } //} void swap(list<T>& tmp) { std::swap(_head, tmp._head); } list(const list<T>& It)//拷贝构造现代写法 { empty_init();//将头节点初始化 list<T> tmp(It.begin(), It.end()); swap(tmp); } list<T>& operator=(list<T> It)//赋值 { swap(It); return *this; } ~list()//析构函数 { //将头节点也要释放掉 clear(); delete _head; _head = nullptr; } void clear()//清空数据 //但是要注意不要把head清掉 { iterator it = begin(); while (it != end()) { it=erase(it);//为了防止迭代器失效设置返回值 //返回值为当前节点的下一个 } } void push_back(const T&x)//尾插 { /*node* tail = _head->_prev; node* newnode = new node(x); 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 insert(iterator pos,const T&x)//在pos位置前插入x { node* cur = pos._node; node* prev = cur->_prev; node* newnode = new node(x); prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; } iterator erase(iterator pos)//删除pos位置 { //头节点不可以删除 assert(pos != end()); node* cur = pos._node; node* prev = cur->_prev; node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return iterator(next); } void pop_back()//尾删 { erase(--end()); } void pop_front()//头删 { erase(begin()); } iterator begin() { return iterator(_head->_next);//通过匿名对象访问第一个数据 } iterator end() { return iterator(_head);//通过匿名对象访问最后一个数据的下一个 } const_iterator begin()const { return const_iterator(_head->_next); } const_iterator end()const { return const_iterator(_head); } private: node* _head; }; /*void test(const list<int>&e) { list<int>::const_iterator it = e.begin(); while (it != e.end()) { cout << *it << " "; ++it; } cout << endl; } void test2() { const list<int> v; test(v); }*/ //void test1() //{ // list<int> v; // v.push_back(1); // v.push_back(2); // v.push_back(3); // v.push_back(4); // list<int>::iterator it= v.begin(); // while (it != v.end()) // { // cout << *it << " "; // ++it; // } // cout << endl; //} /*struct AA { int _a1; int _a2; AA(int a1=0,int a2=0) :_a1(a1) ,_a2(a2) { } };*/ /*void test3() { list<AA>v; v.push_back(AA(1, 1)); v.push_back(AA(2, 2)); v.push_back(AA(3, 3)); list<AA>::iterator it = v.begin(); while (it != v.end()) { cout << it->_a1 << " :"<<it->_a2<<" "; cout << endl; it++; } }*/ //void test4() //{ // list<int> v; // v.push_back(1); // v.push_back(2); // v.push_back(3); // v.push_back(4);// 1 2 3 4 // for (auto e : v) // { // cout << e << " "; // } // cout << endl; // v.clear(); // v.push_back(4);// 4 // for (auto e : v) // { // cout << e << " "; // } //} //void test4() //{ // list<int> v; // v.push_back(1); // v.push_back(2); // v.push_back(3); // v.push_back(4);// 1 2 3 4 // for (auto e : v) // { // cout << e << " "; // } // cout << endl; // list<int> v2(v); // for (auto e : v2)// 1 2 3 4 // { // cout << e << " "; // } //} void test4() { list<int> v; v.push_back(1); v.push_back(2);//v1 = 1 2 list<int> v2; v2.push_back(5); v2.push_back(6);//v2=5 6 v2 = v; for (auto e : v2)// v2=1 2 { cout << e << " "; } cout << endl; for (auto e : v)// v1=1 2 { cout << e << " "; } } } int main() { yzq::test4(); return 0; }
