做网站用小图标在什么网下载,网站建网站建设公司,湛江网站开发哪家专业,如何用eclipse做网站list---模拟实现 list的简介list函数的使用构造函数迭代器的使用list的capacitylist element accesslist modifiers list的模拟实现构造函数#xff0c;拷贝构造函数和迭代器begin和endinsert和eraseclear和析构函数 源码 list的简介
list是用双向带头联表实现的一个容器拷贝构造函数和迭代器begin和endinsert和eraseclear和析构函数 源码 list的简介
list是用双向带头联表实现的一个容器双向联表中每个元素存在互不相关的独立节点中再节点中通过指针指向其前一个元素和后一个元素并且可以再常数范围内再任意位置进行插入和删除的序列式容器。
list函数的使用
构造函数
构造函数 (constructor)接口说明list (size_type n, const value_type val value_type())构造的list中包含n个值为val的元素list()构造空的listlist (const list x)拷贝构造函数list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造list
void ListTest2()
{std::listint a(4, 5);std::cout a的list :;for (auto e : a){std::cout e ;}std::cout std::endl;std::listint b;//Emptystd::listint c(a.begin(), a.end());std::cout c的list :;for (auto e : c){std::cout e ;}}迭代器的使用
函数声明接口说明begin end返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器rbegin rend返回第一个元素的reverse_iterator,即end位置返回最后一个元素下一个位置的 reverse_iterator,即begin位置 std::listint a(4, 5);std::cout a的list :;std::listint::iterator it a.begin();while (it ! a.end()){std::cout *it ;it;}list的capacity
函数声明接口说明empty检测list是否为空是返回true否则返回falsesize返回list中有效节点的个数
list element access
函数声明接口说明front返回list的第一个节点中值的引用back返回list的最后一个节点中值的引用
list modifiers
函数声明接口说明push_front在list首元素前插入值为val的元素pop_front删除list中第一个元素push_back在list尾部插入值为val的元素pop_back删除list中最后一个元素insert在list position 位置中插入值为val的元素erase删除list position位置的元素swap交换两个list中的元素clear清空list中的有效元素
list的模拟实现
要想模拟实现list首先我们可以定义一个节点类。为什么要定义一个节点类呢想想数据结构中的双链表每个元素都在独立的节点中通过节点的前驱指针和后继指针指向前后位置。
list的模拟实现跟vector和string实现是不一样的vector本质上是一个数组数组本身就是一个迭代器而list是一个个的节点通过指针联系在一起所以vector类不用对迭代器进行封装可以直接使用list不一样节点是什么是不清楚的这个时候可以使用运算符重载对–*等进行重载。 templateclass Tstruct list_node{list_nodeT* _next;list_nodeT* _prev;T _val;list_node(const T val T()):_next(nullptr),_prev(nullptr),_val(val){}};再定义一个list类再这个类中完成其他函数的实现 templateclass Tclass list{public:private:Node* _head;size_t _size;};构造函数拷贝构造函数和
list的构造函数实现跟双链表中的初始化是一样的将next指针和prev指针都指向头节点形成一个环。 void EmptyInit(){_head new Node();_head-_next _head;_head-_prev _head;_size 0;}拷贝构造函数再拷贝之前要先开一个头节点的空间然后再头节点后面依次把值进行尾插即可。 list(const listT it){EmptyInit();for (auto e : it){push_back(e);}}赋值重载和vector里面的写法是一样的。 listT operator(listT it){swap(it);return *this;}通过传参创建出一个临时变量然后将其交换。
迭代器
要想实现list的迭代器需要将原生态指针进行封装。
list是由一个个的节点组成节点解引用–等操作是找不到对应的数据的所以需要用自定义类型对指针进行封装从而完成一系列操作。
迭代器有一个const类型的迭代器有一个无const类型的再实现一个无const类型的迭代器之后把代码赋值粘贴也可以改成带const类型的迭代器但这样显然是代码冗余的重复的太多这个时候那些大佬们就通过增加模板参数来解决代码冗余根据参数的类型实列化出不同的类。 //typedef __list_iteratorT, T, T* iterator;
//typedef __list_iteratorT,const T,const T* const_iterator;
templateclass T,class Ref,class Ptrstruct __list_iterator{typedef list_nodeT Node;typedef __list_iteratorT, Ref, Ptr self;Node* _node;//构造方法__list_iterator(Node* node):_node(node){}//对节点解引用是找不到我们存储的数据的因为节点里面存的是valnext和prev重载的目是使其对迭代器解引用可以找到有效数据Ref operator*(){return _node-_val;}Ptr operator-(){return (_node-val);}//指针到下一个位置其实就是让节点向后移动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 *this;}bool operator !(const self it) const{return _node ! it._node;}bool operator(const self it) const{return _node it._node;}};以上就是用自定义的类对指针进行封装。
begin和end
对指针进行封装之后就可以实现begin和end了。
begin只要返回头节点的下一个节点即可
end就是头节点 iterator begin(){return _head-_next;}iterator end(){return _head;}const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head;}insert和erase
有一个insert就可以完成再任意位置插入。 void push_back(const T x){insert(end(), x);}void push_front(const T x){insert(begin(), x);}iterator insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);prev-_next newnode;newnode-_next cur;newnode-_prev prev;cur-_prev newnode;return newnode;}先找到当前节点cur和当前节点的上一个节点prev再new出一个要插入的节点newnode使得cur和newnode进行双向连接prev和newnode进行双向连接。 删除一个节点只需要让当前节点的上一个节点和下一个节点完成双向连接即可。 iterator erase(iterator pos){assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;--_size;return next;}clear和析构函数 void clear(){iterator it begin();while (it ! end()){it earse(it);}_size 0;}~list(){}源码
#pragma once#include assert.h
#include algorithmnamespace HaiFan
{templateclass Tstruct list_node{list_nodeT* _next;list_nodeT* _prev;T _val;list_node(const T val T()):_next(nullptr),_prev(nullptr),_val(val){}};templateclass T,class Ref,class Ptrstruct __list_iterator{typedef list_nodeT Node;typedef __list_iteratorT, Ref, Ptr self;Node* _node;__list_iterator(Node* node):_node(node){}T operator*(){return _node-_val;}T* operator-(){return (_node-val);}T operator(){_node _node-_next;return *this;}T operator(int){self tmp(*this);_node _node-_next;return tmp;}T operator--(){_node _node-_prev;return *this;}T operator--(int){self tmp(*this);_node _node-prev;return *this;}bool operator !(const self it) const{return _node ! it._node;}bool operator(const self it) const{return _node it._node;}};templateclass Tclass list{typedef list_nodeT Node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT,const T,const T* const_iterator;iterator begin(){return _head-_next;}iterator end(){return _head;}const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head;}list(){EmptyInit();}list(const listT it){EmptyInit();for (auto e : it){push_back(e);}}listT operator(listT it){swap(it);return *this;}void swap(listT it){std::swap(_head, it._head);std::swap(_size, it._size);}void clear(){iterator it begin();while (it ! end()){it earse(it);}_size 0;}void push_back(const T x){insert(end(), x);}void push_front(const T x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);prev-_next newnode;newnode-_next cur;newnode-_prev prev;cur-_prev newnode;return newnode;}iterator erase(iterator pos){assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;--_size;return next;}size_t size(){return _size;}void EmptyInit(){_head new Node();_head-_next _head;_head-_prev _head;_size 0;}~list(){}private:Node* _head;size_t _size;};
}
