目录

单向、双向、随机迭代器

list的模拟

结点

迭代器

插入

删除

empty

size

获取头部元素

获取尾部元素

尾插尾删

头插头删

clear

swap

拷贝

赋值

完整代码

单向、双向、随机迭代器

算法对迭代器是有要求的，算法迭代器名字就是要求。

迭代器通用的功能++/*（解引用）/！=这几个基本组成。

需要单向迭代器的算法，则在这个算法加入的迭代器就必须是大于单向迭代器的功能的（也就是说后面的迭代器都支持前面迭代器的功能，这里体现了向前兼容特点，也更好的解偶）如果是数据结构stl迭代器是双向迭代器是实现不了随机的功能的，这也导致了有时候使用迭代器时候用不了+ -迭代，这就是因为双向迭代器不支持+，-这些运算符重载。双向迭代器不能支持+-操作，一般能实现的只有随机迭代器（解决办法就是在调用之前使用一个变量存储迭代器然后++\--操作达到想要的指向地址）

list内部的sort算法，如果数据量小，就用，数据量大，用别人的。因为算法库里面的sort是随机迭代器，比list大，所以有些操作不能支持，所以这里需要写sort调用list自己的sort。

list的模拟

结点

双向链表的结点和我们在数据结构中双向链表是一样的。

//链表结点 template<class T> class list_node { T data; //数据内容 list_node* next;//指向下一个结点 list_node* prev;//指向上一个结点 //构造 list_node(const T& value) :data(value) ,next(nullptr) ,prev(nullptr) {} };

迭代器

//迭代器 template<class T,class Ref,class Ptr> struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T, 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(list<T>& l) { std::swap(_head, l._head); std::swap(_size, l._size); }

拷贝

//拷贝 list(const list<T>& l) { _head = new Node; _head->_next = _head; _head->_prev = _head; for (auto& e : l) { push_back(e); } }

赋值

//赋值 list<T>& operator=(const list<T>& l) { //_head = l._head; //_size = l._size; //return *this; if(this != &l) { clear(); list<T> tmp(l); swap(tmp); } return *this; }

完整代码

#pragma once #include<iostream> using namespace std; namespace bear { //链表结点 template<class T> struct list_node { T _data; //数据内容 list_node<T>* _next;//指向下一个结点 list_node<T>* _prev;//指向上一个结点 //构造 list_node(const T& value = T()) :_data(value) ,_next(nullptr) ,_prev(nullptr) {} }; //迭代器 template<class T,class Ref,class Ptr> struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T, 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; } }; template<class T> class list { public: typedef list_node<T> Node; typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, 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 list<T>& l) { _head = new Node; _head->_next = _head; _head->_prev = _head; for (auto& e : l) { push_back(e); } } //赋值 list<T>& operator=(const list<T>& l) { //_head = l._head; //_size = l._size; //return *this; if(this != &l) { clear(); list<T> 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(list<T>& l) { std::swap(_head, l._head); std::swap(_size, l._size); } private: Node* _head; size_t _size = 0; }; }