目录单向、双向、随机迭代器list的模拟结点迭代器插入删除emptysize获取头部元素获取尾部元素尾插尾删头插头删clearswap拷贝赋值完整代码单向、双向、随机迭代器算法对迭代器是有要求的算法迭代器名字就是要求。迭代器通用的功能/*解引用/这几个基本组成。需要单向迭代器的算法则在这个算法加入的迭代器就必须是大于单向迭代器的功能的也就是说后面的迭代器都支持前面迭代器的功能这里体现了向前兼容特点也更好的解偶如果是数据结构stl迭代器是双向迭代器是实现不了随机的功能的这也导致了有时候使用迭代器时候用不了 -迭代这就是因为双向迭代器不支持-这些运算符重载。双向迭代器不能支持-操作一般能实现的只有随机迭代器解决办法就是在调用之前使用一个变量存储迭代器然后\--操作达到想要的指向地址list内部的sort算法如果数据量小就用数据量大用别人的。因为算法库里面的sort是随机迭代器比list大所以有些操作不能支持所以这里需要写sort调用list自己的sort。list的模拟结点双向链表的结点和我们在数据结构中双向链表是一样的。//链表结点 templateclass T class list_node { T data; //数据内容 list_node* next;//指向下一个结点 list_node* prev;//指向上一个结点 //构造 list_node(const T value) :data(value) ,next(nullptr) ,prev(nullptr) {} };迭代器//迭代器 templateclass T,class Ref,class Ptr struct __list_iterator { typedef list_nodeT Node; typedef __list_iteratorT, Ref, Ptr Self; Node* _pNode; //构造 __list_iterator(Node* pNode nullptr) :_pNode(pNode) {} //*解引用访问数据 Ref operator*()//使用引用是为了方便修改数据 { return _pNode-_data; } //-运算符重载 Ptr operator-() { return (_pNode-_data); } //运算符重载 Self operator() { _pNode _pNode-_next; return *this; } //后置 Self operator(int) { Self tmp(*this); _pNode _pNode-_next; return tmp; } //--运算符重载 Self operator--() { _pNode _pNode-_prev; return *this; } //后置-- Self operator--(int) { Self tmp(*this);//拷贝值浅拷贝 _pNode _pNode-_prev; return tmp; } //!运算符重载 bool operator!(const Self l)const { return _pNode l._pNode; } //运算符重载 bool operator (const Self l)const { return _pNode l._pNode; } };插入iterator insert(iterator pos, const T value) { Node* newnode new Node(value); Node* cur pos._pNode; Node* prev pos._pNode-_prev; //newnode newnode-_next cur; newnode-_prev prev; //prev cur prev-_next newnode; cur-_prev newnode; _size; return newnode; }删除//删除 iterator erase(iterator pos) { Node* next pos._pNode-_next; Node* prev pos._pNode-_prev; prev-_next next; next-_prev prev; delete pos._pNode; pos._pNode nullptr; --_size; return next; }empty//empty bool empty() { return _size 0; }size//size size_t size() { return _size; }获取头部元素//获取首元素 T front()const { return _head-_next-_data; }获取尾部元素//获取尾部元素 T back()const { return _head-_prev-_data; }尾插尾删//尾插 void push_back(const T value) { insert(end(), value);//这里不用前置--insert在设计的时候就是在pos位置之前插入 } //尾删 void pop_back() { erase(--end()); }这里为了避免大家翻上面代码我这里把insert和erase的代码放在下面insert//插入 iterator insert(iterator pos, const T value) { Node* newnode new Node(value); Node* cur pos._pNode; Node* prev pos._pNode-_prev; //newnode newnode-_next cur; newnode-_prev prev; //prev cur prev-_next newnode; cur-_prev newnode; _size; return newnode; }erase//删除 iterator erase(iterator pos) { Node* next pos._pNode-_next; Node* prev pos._pNode-_prev; prev-_next next; next-_prev prev; delete pos._pNode; pos._pNode nullptr; --_size; return next; }头插头删//头插 void push_front(const T value) { insert(begin(), value); } //头删 void pop_front() { erase(begin()); }clear//clear void clear() { iterator it begin(); while (it ! end()) { it erase(it); } }swap//swap void swap(listT l) { std::swap(_head, l._head); std::swap(_size, l._size); }拷贝//拷贝 list(const listT l) { _head new Node; _head-_next _head; _head-_prev _head; for (auto e : l) { push_back(e); } }赋值//赋值 listT operator(const listT l) { //_head l._head; //_size l._size; //return *this; if(this ! l) { clear(); listT tmp(l); swap(tmp); } return *this; }完整代码#pragma once #includeiostream using namespace std; namespace bear { //链表结点 templateclass T struct list_node { T _data; //数据内容 list_nodeT* _next;//指向下一个结点 list_nodeT* _prev;//指向上一个结点 //构造 list_node(const T value T()) :_data(value) ,_next(nullptr) ,_prev(nullptr) {} }; //迭代器 templateclass T,class Ref,class Ptr struct __list_iterator { typedef list_nodeT Node; typedef __list_iteratorT, Ref, Ptr Self; Node* _pNode; //构造 __list_iterator(Node* pNode) :_pNode(pNode) {} //*解引用访问数据 Ref operator*()//使用引用是为了方便修改数据 { return _pNode-_data; } //-运算符重载 Ptr operator-() { return (_pNode-_data); } //运算符重载 Self operator() { _pNode _pNode-_next; return *this; } //后置 Self operator(int) { Self tmp(*this); _pNode _pNode-_next; return tmp; } //--运算符重载 Self operator--() { _pNode _pNode-_prev; return *this; } //后置-- Self operator--(int) { Self tmp(*this);//拷贝值浅拷贝 _pNode _pNode-_prev; return tmp; } //!运算符重载 bool operator!(const Self l)const { return _pNode ! l._pNode; } //运算符重载 bool operator (const Self l)const { return _pNode l._pNode; } }; templateclass T class list { public: typedef list_nodeT Node; typedef __list_iteratorT, T, T* iterator; typedef __list_iteratorT, const T, const T* const_iterator; //迭代器 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); } //构造 list() { _head new Node; _head-_next _head; _head-_prev _head; } //拷贝 list(const listT l) { _head new Node; _head-_next _head; _head-_prev _head; for (auto e : l) { push_back(e); } } //赋值 listT operator(const listT l) { //_head l._head; //_size l._size; //return *this; if(this ! l) { clear(); listT tmp(l); swap(tmp); } return *this; } //析构 ~list() { clear(); delete _head; _head nullptr; } //插入 iterator insert(iterator pos, const T value) { Node* newnode new Node(value); Node* cur pos._pNode; Node* prev pos._pNode-_prev; //newnode newnode-_next cur; newnode-_prev prev; //prev cur prev-_next newnode; cur-_prev newnode; _size; return newnode; } //删除 iterator erase(iterator pos) { Node* next pos._pNode-_next; Node* prev pos._pNode-_prev; prev-_next next; next-_prev prev; delete pos._pNode; pos._pNode nullptr; --_size; return next; } //empty bool empty()const { return _size 0; } //size size_t size()const { return _size; } //获取首元素 T front()const { return _head-_next-_data; } //获取尾部元素 T back()const { return _head-_prev-_data; } //尾插 void push_back(const T value) { insert(end(), value); } //尾删 void pop_back() { erase(--end()); } //头插 void push_front(const T value) { insert(begin(), value); } //头删 void pop_front() { erase(begin()); } //clear void clear() { iterator it begin(); while (it ! end()) { it erase(it); } } //swap void swap(listT l) { std::swap(_head, l._head); std::swap(_size, l._size); } private: Node* _head; size_t _size 0; }; }
目录单向、双向、随机迭代器list的模拟结点迭代器插入删除emptysize获取头部元素获取尾部元素尾插尾删头插头删clearswap拷贝赋值完整代码单向、双向、随机迭代器算法对迭代器是有要求的算法迭代器名字就是要求。迭代器通用的功能/*解引用/这几个基本组成。需要单向迭代器的算法则在这个算法加入的迭代器就必须是大于单向迭代器的功能的也就是说后面的迭代器都支持前面迭代器的功能这里体现了向前兼容特点也更好的解偶如果是数据结构stl迭代器是双向迭代器是实现不了随机的功能的这也导致了有时候使用迭代器时候用不了 -迭代这就是因为双向迭代器不支持-这些运算符重载。双向迭代器不能支持-操作一般能实现的只有随机迭代器解决办法就是在调用之前使用一个变量存储迭代器然后\--操作达到想要的指向地址list内部的sort算法如果数据量小就用数据量大用别人的。因为算法库里面的sort是随机迭代器比list大所以有些操作不能支持所以这里需要写sort调用list自己的sort。list的模拟结点双向链表的结点和我们在数据结构中双向链表是一样的。//链表结点 templateclass T class list_node { T data; //数据内容 list_node* next;//指向下一个结点 list_node* prev;//指向上一个结点 //构造 list_node(const T value) :data(value) ,next(nullptr) ,prev(nullptr) {} };迭代器//迭代器 templateclass T,class Ref,class Ptr struct __list_iterator { typedef list_nodeT Node; typedef __list_iteratorT, Ref, Ptr Self; Node* _pNode; //构造 __list_iterator(Node* pNode nullptr) :_pNode(pNode) {} //*解引用访问数据 Ref operator*()//使用引用是为了方便修改数据 { return _pNode-_data; } //-运算符重载 Ptr operator-() { return (_pNode-_data); } //运算符重载 Self operator() { _pNode _pNode-_next; return *this; } //后置 Self operator(int) { Self tmp(*this); _pNode _pNode-_next; return tmp; } //--运算符重载 Self operator--() { _pNode _pNode-_prev; return *this; } //后置-- Self operator--(int) { Self tmp(*this);//拷贝值浅拷贝 _pNode _pNode-_prev; return tmp; } //!运算符重载 bool operator!(const Self l)const { return _pNode l._pNode; } //运算符重载 bool operator (const Self l)const { return _pNode l._pNode; } };插入iterator insert(iterator pos, const T value) { Node* newnode new Node(value); Node* cur pos._pNode; Node* prev pos._pNode-_prev; //newnode newnode-_next cur; newnode-_prev prev; //prev cur prev-_next newnode; cur-_prev newnode; _size; return newnode; }删除//删除 iterator erase(iterator pos) { Node* next pos._pNode-_next; Node* prev pos._pNode-_prev; prev-_next next; next-_prev prev; delete pos._pNode; pos._pNode nullptr; --_size; return next; }empty//empty bool empty() { return _size 0; }size//size size_t size() { return _size; }获取头部元素//获取首元素 T front()const { return _head-_next-_data; }获取尾部元素//获取尾部元素 T back()const { return _head-_prev-_data; }尾插尾删//尾插 void push_back(const T value) { insert(end(), value);//这里不用前置--insert在设计的时候就是在pos位置之前插入 } //尾删 void pop_back() { erase(--end()); }这里为了避免大家翻上面代码我这里把insert和erase的代码放在下面insert//插入 iterator insert(iterator pos, const T value) { Node* newnode new Node(value); Node* cur pos._pNode; Node* prev pos._pNode-_prev; //newnode newnode-_next cur; newnode-_prev prev; //prev cur prev-_next newnode; cur-_prev newnode; _size; return newnode; }erase//删除 iterator erase(iterator pos) { Node* next pos._pNode-_next; Node* prev pos._pNode-_prev; prev-_next next; next-_prev prev; delete pos._pNode; pos._pNode nullptr; --_size; return next; }头插头删//头插 void push_front(const T value) { insert(begin(), value); } //头删 void pop_front() { erase(begin()); }clear//clear void clear() { iterator it begin(); while (it ! end()) { it erase(it); } }swap//swap void swap(listT l) { std::swap(_head, l._head); std::swap(_size, l._size); }拷贝//拷贝 list(const listT l) { _head new Node; _head-_next _head; _head-_prev _head; for (auto e : l) { push_back(e); } }赋值//赋值 listT operator(const listT l) { //_head l._head; //_size l._size; //return *this; if(this ! l) { clear(); listT tmp(l); swap(tmp); } return *this; }完整代码#pragma once #includeiostream using namespace std; namespace bear { //链表结点 templateclass T struct list_node { T _data; //数据内容 list_nodeT* _next;//指向下一个结点 list_nodeT* _prev;//指向上一个结点 //构造 list_node(const T value T()) :_data(value) ,_next(nullptr) ,_prev(nullptr) {} }; //迭代器 templateclass T,class Ref,class Ptr struct __list_iterator { typedef list_nodeT Node; typedef __list_iteratorT, Ref, Ptr Self; Node* _pNode; //构造 __list_iterator(Node* pNode) :_pNode(pNode) {} //*解引用访问数据 Ref operator*()//使用引用是为了方便修改数据 { return _pNode-_data; } //-运算符重载 Ptr operator-() { return (_pNode-_data); } //运算符重载 Self operator() { _pNode _pNode-_next; return *this; } //后置 Self operator(int) { Self tmp(*this); _pNode _pNode-_next; return tmp; } //--运算符重载 Self operator--() { _pNode _pNode-_prev; return *this; } //后置-- Self operator--(int) { Self tmp(*this);//拷贝值浅拷贝 _pNode _pNode-_prev; return tmp; } //!运算符重载 bool operator!(const Self l)const { return _pNode ! l._pNode; } //运算符重载 bool operator (const Self l)const { return _pNode l._pNode; } }; templateclass T class list { public: typedef list_nodeT Node; typedef __list_iteratorT, T, T* iterator; typedef __list_iteratorT, const T, const T* const_iterator; //迭代器 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); } //构造 list() { _head new Node; _head-_next _head; _head-_prev _head; } //拷贝 list(const listT l) { _head new Node; _head-_next _head; _head-_prev _head; for (auto e : l) { push_back(e); } } //赋值 listT operator(const listT l) { //_head l._head; //_size l._size; //return *this; if(this ! l) { clear(); listT tmp(l); swap(tmp); } return *this; } //析构 ~list() { clear(); delete _head; _head nullptr; } //插入 iterator insert(iterator pos, const T value) { Node* newnode new Node(value); Node* cur pos._pNode; Node* prev pos._pNode-_prev; //newnode newnode-_next cur; newnode-_prev prev; //prev cur prev-_next newnode; cur-_prev newnode; _size; return newnode; } //删除 iterator erase(iterator pos) { Node* next pos._pNode-_next; Node* prev pos._pNode-_prev; prev-_next next; next-_prev prev; delete pos._pNode; pos._pNode nullptr; --_size; return next; } //empty bool empty()const { return _size 0; } //size size_t size()const { return _size; } //获取首元素 T front()const { return _head-_next-_data; } //获取尾部元素 T back()const { return _head-_prev-_data; } //尾插 void push_back(const T value) { insert(end(), value); } //尾删 void pop_back() { erase(--end()); } //头插 void push_front(const T value) { insert(begin(), value); } //头删 void pop_front() { erase(begin()); } //clear void clear() { iterator it begin(); while (it ! end()) { it erase(it); } } //swap void swap(listT l) { std::swap(_head, l._head); std::swap(_size, l._size); } private: Node* _head; size_t _size 0; }; }
、中断、异常、接口、系统调用、体系结构)
