目录
介绍
list的实现
1.自定义节点
2.迭代器封装
构造函数
前置++和后置++
前置--和后置--
*操作符和->操作符
==和!=操作符
iterator和const_iterator
3. list类
构造函数和析构函数
=赋值操作
头尾迭代器
插入和删除
头插头删尾插尾删
list接口函数总代码
介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)List原文档，我们可以去cplusplus网站去查看详情
https://cplusplus.com/reference/list/list/?kw=list
list的实现
1.自定义节点
因为是双向链表,所以我们只需要定义前指针和后指针,以及该节点的值data,因为我们以后要经常访问里面的内容所以使用结构体更合适.另外需要一个默认构造函数来方便以后的拷贝和初始化;
template<class T>
struct Node
{struct Node* next;struct Node* prev; T data;Node(const T& val=T()):prev(nullptr), next(nullptr), data(val)//初始化{}
};2.迭代器封装
迭代器作为STL中一个万能的访问方式,在任何一个容器中都是可以使用++,*像这样的操作的,我们之前在vector中iterator是对T*进行别名的,因为vector是连续性的容器,所以T*是可以++来进行遍历操作的,但是list是链表,其地址是不连续的,所以无法直接对迭代器进行++等操作,因此我们需要对Node* 和多个重载运算符来封装成iterator 和const iterator;
迭代器包装的还是T* ,在这里是Node*,后面++操作需要对迭代器本身处理,所以我们也把listiterator<T>简化成self;
构造函数
//封装迭代器 template<class T>class listiterator{typedef Node<T> node;typedef listiterator <T> self;public:listiterator(node* node) //拷贝节点 迭代器还是node* 只是多添加了些运算符操作:_node(node){}node* _node;};iterator只需要一个拷贝构造函数即可;直接将_node初始化为node;
前置++和后置++
这个迭代器本身就是一个类,所以自增后返回的是一个类,这就用到了self,前置++:直接将_node指针后移指向next即可;然后返回*this;后置的就需要一个中间变量来储存操作前的迭代器,然后返回临时变量,需要注意的是后置++返回的是临时变量,因此返回的类型不能使用引用.
//前置++self operator ++(){_node = _node->next;return *this;}//后置++self operator++(int){self tmp(*this);_node = _node->next;return tmp;}前置--和后置--
与上面的操作模版相同,返回的是上一个节点;
//前置--self& operator --(){_node = _node->prev;return *this;}//后置--self operator --(int){self tmp(*this);_node = _node->prev;return tmp;}*操作符和->操作符
解引用操作直接返回节点的值即可,这里比较难以理解的就是->返回的是值data的地址,这里调用时省略了一个operator->(),因为迭代器本身就是一个类重载的操作符->指向的就是_node,然后_node才能访问data,这里这样写可以直接访问到data;
//*迭代器T& operator*(){return _node->data;}//->迭代器T* operator->(){return &_node->data;}==和!=操作符
这里直接比较就行了;
bool operator !=(const self& it)const
{return it._node != _node;
}
//迭代器相等
bool operator ==(const self& it)const
{return it._node == _node;
}iterator和const_iterator
我们知道const_iterator是不能够改变内部的值的,所以我们为了写出一个const_iterator直接通过模版来让编译器来写;其中与能够改变内部值的只有*和->操作,我们只需要把返回值改成const T&和const T*就能实现常迭代器,为此,我们直接将这两个函数的返回值定义为模版ref和ptr;这样就能轻松完成两种迭代器了;
template<class T,class ref,class ptr>
class listiterator
{typedef Node<T> node; typedef listiterator <T ,ref,ptr> self;
public: //*迭代器ref operator*(){return _node->data; } //->迭代器ptr operator->() {return &_node->data; }
}3. list类
list的源码中私有成员是只有一个节点哨兵位_head的;我们先来把封装好的节点和迭代器造个别名再实现下构造函数;
构造函数和析构函数
因为构造函数和拷贝构造函数都需要先创造一个哨兵位,所以我们把哨兵位的创建写成函数.
拷贝构造函数直接遍历形参调用尾插push_back即可;
析构函数需要挨个的把所有的节点释放掉,最后释放掉哨兵位;这里消除节点我们可以直接用后面实现的erase;
template<class T>
class list
{typedef Node<T> node;//节点
public:typedef listiterator<T,T&,T*> iterator; //迭代器typedef listiterator <T, const T&, const T*>const_iterator; //常量迭代器//创建哨兵位void init(){_head = new node(); _head->next = _head->prev =_head ; }//构造函数list() {init(); }//拷贝构造函数list(const list<T>&it){init(); for (const auto& x : it){push_back(x); }}
//析构函数
~list()
{clear(); delete _head; _head = nullptr;
}
//销毁函数
void clear()
{auto it = begin(); while (it != end()){it = erase(it); }
}=赋值操作
将一个类赋值给另一个类,我们现代的写法就是,形参不引用,使用swap与形参交换数据.
//list赋值操作
list<T>& operator=(list<T> x)
{swap(_head, x._head); //直接交换哨兵位return *this;
}头尾迭代器
//头迭代器
iterator begin() //it是局部变量,返回值不能引用
{iterator it(_head->next); return it;
}
//常量迭代器
const_iterator begin()const
{const_iterator it(_head->next);return it;
}
//尾迭代器
iterator end()
{iterator it(_head);return it;
}
//常量尾迭代器
const_iterator end()const
{const_iterator it(_head); return it;
}插入和删除
插入就比较简单了并且没有迭代器失效的风险,改变对应两个前后两个节点的指向就行了.虽然不需要返回迭代器,但是最好按照文档来;
删除需要注意的是需要将删掉的节点释放掉,返回pos原来节点的下一个位置的迭代器;
//插入
iterator insert(iterator pos, T x)
{node* cur = pos._node; node* net = cur->next; node* newnode = new node(x); cur->next = newnode;newnode->prev = cur;newnode->next = net;net->prev = newnode; return iterator(newnode); //返回迭代器
}
//删除
iterator erase(iterator pos)
{assert(pos != end()); node* cur = pos._node; node* pre = cur->prev; node* net = cur->next; pre->next = net; net->prev = pre;delete cur; return iterator(net);
}头插头删尾插尾删
直接调用对应的insert和erase,begin()就是_head后面的第一个有效数据,end()就是哨兵位,所以我们需要--一下,回到尾节点;
//头插void push_front(T x){insert(begin(), x); }//头删void pop_front() {erase(begin());}//尾插void push_back(T x) {insert(--end(), x); }//尾删void pop_back(){erase(--end()); }list接口函数总代码
#pragma once
#include<iostream>
#include<assert.h>
#include<algorithm>
using namespace std;
namespace bit
{template<class T>struct Node{struct Node* next;struct Node* prev; T data;Node(const T& val=T()):prev(nullptr), next(nullptr), data(val)//初始化{}};
//封装迭代器
template<class T,class ref,class ptr>
class listiterator
{typedef Node<T> node; typedef listiterator <T ,ref,ptr> self;
public: listiterator(node* node) //拷贝节点 迭代器还是node* 只是多添加了些运算符操作:_node(node) {}//前置++self operator ++(){_node = _node->next; return *this; }//后置++self operator++(int){self tmp(*this);_node = _node->next;return tmp; }//前置--self& operator --() {_node = _node->prev; return *this; } //后置--self operator --(int){self tmp(*this);_node = _node->prev; return tmp; }//*迭代器ref operator*(){return _node->data; } //->迭代器ptr operator->() {return &_node->data; }//bool operaotr != ( const self& it) //{// return _node != iit. //}//迭代器不相等bool operator !=(const self& it)const { return it._node != _node; }//迭代器相等bool operator ==(const self& it)const {return it._node == _node; }node* _node;
};
//list实现template<class T> class list{typedef Node<T> node;//节点public:typedef listiterator<T,T&,T*> iterator; //迭代器typedef listiterator <T, const T&, const T*>const_iterator; //常量迭代器//创建哨兵位void init(){_head = new node(); _head->next = _head->prev =_head ; }//构造函数list() {init(); }//拷贝构造函数list(const list<T>&it){init(); for (const auto& x : it){push_back(x); }}//析构函数~list(){clear(); delete _head; _head = nullptr; }//销毁函数void clear(){auto it = begin(); while (it != end()){it = erase(it); }}//list赋值操作list<T>& operator=(list<T> x) {swap(_head, x._head); return *this; }//头迭代器iterator begin() //加不加引用都可以,加引用就是引用的常量;不加引用就是拷贝的常量 {iterator it(_head->next); return it; }//常量迭代器const_iterator begin()const{const_iterator it(_head->next);return it;}//尾迭代器iterator end(){iterator it(_head);return it; }//常量尾迭代器const_iterator end()const{const_iterator it(_head); return it; }void print(){node* cur = _head->next; while (cur != _head){cout << cur->data<<" ";cur = cur->next; }cout << endl; }//插入iterator insert(iterator pos, T x){node* cur = pos._node; node* net = cur->next; node* newnode = new node(x); cur->next = newnode;newnode->prev = cur;newnode->next = net;net->prev = newnode; return iterator(newnode); //返回迭代器 }//删除iterator erase(iterator pos){assert(pos != end()); node* cur = pos._node; node* pre = cur->prev; node* net = cur->next; pre->next = net; net->prev = pre;delete cur; return iterator(net);}//头插void push_front(T x){insert(begin(), x); }//头删void pop_front() {erase(begin());}//尾插void push_back(T x) {insert(--end(), x); }//尾删void pop_back(){erase(--end()); }private:node* _head; };void test(){bit::list<int>t;t.push_back(1);t.push_back(2);t.push_back(3);t.push_back(4); t.push_back(5);t.print();bit::list<int>t2;t2 = t;auto it = t2.begin(); //验证赋值操作t2.print();bit::list<int>t3(t2);auto it3 = t3.begin();while (it3 != t3.end()){cout << *it3 << " ";it3 = t3.erase(it3);}/*it++;cout << typeid(it).name()<<*it<<endl;auto it2 = t.end();cout << typeid(it2).name()<<*it << endl;bit::list<int>::iterator ita = t.begin();cout << *(it++) << endl; */}
}
