C++：list

目录

List的模拟实现

List节点类

List链表结构

List迭代器类

结构

T& operator*();

T& operator->();

Self& operator++();

Self operator++(int);

Self& operator--();

Self& operator--(int);

bool operator!=(const Self& l);

bool operator==(const Self& l);

List的构造

构造函数

迭代器区间构造

拷贝构造

运算符重载

析构函数

List iterator

begin

end

List Capacity

size

empty

List Access

front

back

List Modify

在pos位置前插入值为val的节点

删除pos位置的节点

clear

其它功能进行复用

---

学习目标

1.会模拟实现list的基础功能

2.const迭代器（模板类的参数）

3.->的重载

List的模拟实现

List节点类

1.指针域         2.数据域

	//1,定义节点template<class T>struct list_node {list_node<T>* _pre;list_node<T>* _next;T _data;//构造函数list_node(const T& x = T()) :_pre(nullptr),_next(nullptr),_data(x){}};

List链表结构

1.结构：双向带头循环链表

	//2.list(链表)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;//构造函数(初始化)list() {_head = new node;_head->_pre = _head;_head->_next = _head;}private:node* _head;};

List迭代器类

链表的成员都是节点，需要使用节点指针，于是不再使用原生指针，而对原生指针进行封装

1.迭代器要么是原生指针

2.迭代器要么是自定义类型对原生指针的封装，模拟指针的行为

（Vector中由于存储空间连续，指针ptr++就跳到下一个成员的位置 ）

（ List中，存储空间不是连续的，指针ptr++不一定会跳到下一个成员的位置）

结构

	//3.list的迭代器类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* n):pnode(n){}};

T& operator*();

		//*(解引用)Ref operator*(){return pnode ->_data;}

T& operator->();

		Ptr operator->() {return &pnode->_data;}

Self& operator++();

		self& operator++() {pnode = pnode->_next;return *this;}

Self operator++(int);

		self operator++(int) {self tmp(*this);//拷贝构造pnode = pnode->_next;return tmp;}

Self& operator--();

		self& operator--() {pnode = pnode->_pre;return *this;}

Self& operator--(int);

		self operator--(int){self tmp(*this);pnode = pnode->_pre;return tmp;}

bool operator!=(const Self& l);

		bool operator==(const self& I) {return pnode == I.pnode;}

bool operator==(const Self& l);

		bool operator!=(const self& I){return pnode != I.pnode;}

List的构造

构造函数

		//构造函数void init(){_head = new node;_head->_pre = _head;_head->_next = _head;}list() {_head = new node;_head->_pre = _head;_head->_next = _head;}list(int n, const T& value = T()) {init();while (n--) {push_back(value);}}

迭代器区间构造

		//迭代器区间构造template <class Iterator>list(Iterator first, Iterator last) {init();while (first != last) {push_back(*first);++first;}}

拷贝构造

		void swap(list<T>& L) {std::swap(_head,L._head);}//拷贝构造(现代写法)list(const list<T>& L) {init();list<T> tmp(L.begin(), L.end());swap(tmp);}

运算符重载

		//运算符重载(现代写法)list<T>& operator=(const list<T> L) {swap(L);return *this;}

这里不加引用就是用其拷贝构造,若加了引用,赋值后改变这个list,L也会被改变

析构函数

		//析构函数~list() {clear();delete _head;_head = nullptr;}

List iterator

迭代器

		//迭代器typedef __list_iterator<T, T&,T*> iterator;typedef __list_iterator<T, const T&,const T*> const_iterator;

begin

		iterator begin() {return iterator(_head->_next);}const_iterator begin()const{return const_iterator(_head->_next);}

end

		iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}

List Capacity

size

		size_t size()const {size_t count = 0;const_iterator it = begin();while (it != end()) {count++;++it;}return count;}

empty

		bool empty()const {return _head->_next == _head;}

List Access

front

		T& front() {return _head->_next->_data;}const T& front()const {return _head->_next->_data;}

back

		T& back() {return _head->_pre->_data;}const T& back()const {return _head->_pre->_data;}

List Modify

头插，头删，尾插，尾删，在pos位置插入val，删除pos位置的节点并返回下一节点位置

clear，swap

在pos位置前插入值为val的节点

		iterator insert(iterator pos, const T& val) {node* cur = pos.pnode;node* pre = cur->_pre;node* new_node = new node(val);pre->_next = new_node;//pos前的节点与new_node连接new_node->_pre = pre;new_node->_next = cur;//new_node与pos的节点连接cur->_pre = new_node;return new_node;}

删除pos位置的节点

返回该节点的下一个位置

		iterator erase(iterator pos) {node* pre = pos.pnode->_pre;node* next = pos.pnode->_next;pre->_next = next;//连接pos的前后节点next->_pre = pre;delete pos.pnode;//删除pos位置的节点return next;}

clear

		void clear() {iterator it = begin();while (it != end()) {//it = erase(it);erase(it++);}}

其它功能进行复用

		void push_back(const T& val){insert(end(), val);}void pop_back() { erase(--end());}void push_front(const T& val) { insert(begin(), val);}void pop_front() { erase(begin());}

效果展示:

尾插,头插,在pos位置插入值