织梦网站后台密码错误,网页传奇手游,广州网站建设信科分公司,网站上的小动画咋做list的介绍
详细请看#xff08;https://cplusplus.com/reference/list/list/?kwlist#xff09;
1.list是一个可以在常数范围内在任意位置#xff0c;进行插入和删除的序列式容器#xff0c;并且此容器可以前后双向迭代。
2.list的底层实质是一个双向链表结构#xf…list的介绍
详细请看https://cplusplus.com/reference/list/list/?kwlist
1.list是一个可以在常数范围内在任意位置进行插入和删除的序列式容器并且此容器可以前后双向迭代。
2.list的底层实质是一个双向链表结构双向链表里每个元素的存放都互不相关在节点中可以通过指针来指向前一个元素和后一个元素
3.相对于vector等序列式容器list在任意位置上的插入、删除元素的效率会更高。
4.但是list与其他序列式容器相比最大缺陷是不支持任意位置的随机访问必须要从已知位置迭代到当前的位置只有这样才可以进行数据的读取。
简要使用
建立及其数据的尾插
void test_list1()
{listint l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);listint::iterator it l1.begin();//读取需要用迭代器读取不能用下标while (it ! l1.end()){cout *it ;it;}cout endl;for (auto e : l1){cout e ;}cout endl;
}
排序
listint l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
l1.push_back(5);l1.reverse();//进行了逆序
l1.sort();//默认升序//降序
greaterint gt;
l1.sort(gt);//传入这个即可l1.sort(greaterint());//也可以用匿名函数//升序限定范围
sort(v.begin(), v.end());
数据的拷贝
lt2.assign(v.begin(), v.end());//粘贴
去重函数
listint L;
L.push_back(1);
L.push_back(4);
L.push_back(3);
L.push_back(3);L.unique();
//但在注意的是去重函数本质是用一个双指针进行删除连续相同的会留下一个若是多个重复数据若不是连//续的那么结果还是会出现重复的元素。
//——所以需要先进行排序sort
分割函数
listint l1, l2;
for (int i 1; i 4; i)
{l1.push_back(i);
}
for (int i 5; i 8; i)
{l2.push_back(i);
}auto it l1.begin();
l1.splice(it, l2);//将l2中的数据全部插入到l1的it处
list的模拟实现
现在复现list类的简要底层代码——实现的结构体逻辑和用C实现相似。
namespace bit
{templateclass Tstruct list_node//节点的结构,并且对节点进行初始化{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T())
//给缺省值由于不知道是什么类型所以用模板名T进行位置类型变量的初始化(作为缺省)-T():_data(x),_next(nullptr),_prev(nullptr){}};templateclass Tclass list//链表的结构需要一个头结点即可{typedef list_nodeT Node;public:private:Node* _head;};
}
构造函数
void empty_init()
{_headnew Node;_head-_next_head;_head-_prev_head;
}list()
{empty_init();
}
尾插
void push_back(const T x)
{Node*tail_head-_prev;Node* newnodenew Node(x);//建立一个包含x的节点tail-_nextnewnode;newnode-_prevtail;newnode-_next_head;_head-_prevnewnode;_size;
}
节点迭代器
倘若我们有以下的代码
listint l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
l1.push_back(5);listint::iterator it l1.begin();
while (it ! l1.end())
{cout *it ;it;
}
这样子会显示报错这是为什么——结构体存放的是结点解引用出来的是一整个结构体
而且节点存放的空间不是连续存放的所以需要写一个结构体进行对于 节点的指针 的封装。
templateclass T
struct _list_iterator
{ typedef _list_iteratorT self;typedef list_nodeT Node;Node* _node;//结构体里存放的就是节点
}
迭代器的构造
_list_iterator(Node* node)//此迭代器的本质也就是用节点的指针:_node(node)
{}节点指针 self operator()
{_node_node-next;return *this;
}
解引用获取数据
T operator*()//解引用也要进行一个函数的封装,要的是这个数据所以用T
{return _node-_data;
}
指针的比较
bool operator!(const self s)//结点之间比较所以用迭代器的结构体名称
{return _node ! s._node;
}
list类
有了迭代器之后对于list类作补充
templateclass T
class list
{
public:typedef _list_iteratorT iterator;iterator begin(){return _head-_next;}iterator end(){return _head;}}
插入
iterator insert(iterator pos, const T val)//由于插入是利用节点之间的连接进行的且需要用迭代器
{Node* curpos._node;Node* newnodenew Node(val);Node* prevcur-_prev;prev-_nextnewnode;newnode-_prevprev;newnode-_nextcur;cur-_prevnewnode;_size;return iterator(newnode);//insert插入函数的结果会返回插入节点的位置
}
删除
iterator erase(iterator pos)
{Node* curpos._node;Node* prevcur-_prev;Node* nextcur-_next;delete cur;prev-_nextnext;next-_prevprev;--_size;return iterator(next);//erase要返回下一个元素的指针
}
有了insert和erase后可以方便地实现其他函数
void push_front(const T x)//头插
{insert(begin(), x);
}
void pops_front(const T x)//头删
{erase(begin());
}
void pops_back(const T x)//尾删
{erase(end());
}
清理函数
void clear()
{iterator itbegin();while(it!end()){iterase(it);//erase会返回一个指向下一个位置的地址用erase可以减少代码量}
}
拷贝重载/赋值拷贝
void swap(listT lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}listint operator(listint lt)
{swap(lt);return *this;
}list(const listT lt)
{empty_init();for (auto e : lt){push_back(e);//直接用push_back进行数据的插入即可不需要再作拷贝结点}
}析构函数
~list()
{clear();delete _head;_head nullptr;
}
完善节点指针的结构体
templateclass T//用一个迭代器的结构体进行结点的封装
//struct 默认公有但是class类需要做些声明
struct _list_iterator
{typedef list_nodeT Node;typedef _list_iteratorT self;Node* _node;//创造一个结点_list_iterator(Node* node)//用一个结点的指针就能够造出一个迭代器:_node(node)//传入begin就会有对应位置的一个初始化结点出来{}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;}T operator*()//解引用也要进行一个函数的封装,要的是这个数据所以用T{return _node-_data;}T* operator-(){return _node-_data;}bool operator!(const self s)//结点之间比较所以用迭代器的结构体名称{return _node ! s._node;}bool operator(const self s)//结点之间比较所以用迭代器的结构体名称{return _node s._node;}
};
const迭代器
我们知道若无const修饰那么就可以进行 读写 若有const修饰那么就只能进行 读 。
倘若用const修饰迭代器呢(const iterator)——err这样子会是迭代器本身不能修改那么应该怎么表示
——const_iterator 重新定义的一个类型这样本身可以修改指向的内容不能修改。
那么可以在迭代器基础上进行修改成为const迭代器
templateclass T//用一个迭代器的结构体进行结点的封装
//struct 默认公有但是class类需要做些声明
struct _list_const_iterator
{typedef list_nodeT Node;typedef _list_const_iteratorT self;Node* _node;_list_const_iterator(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;}//加上const修改后迭代器里的内容就不能被修改const T operator*()//解引用也要进行一个函数的封装,要的是这个数据所以用T{return _node-_data;}const T* operator-(){return _node-_data;}bool operator!(const self s)//结点之间比较所以用迭代器的结构体名称{return _node ! s._node;}bool operator(const self s)//结点之间比较所以用迭代器的结构体名称{return _node s._node;}
};
现在有了两个迭代器但是这两个迭代器高度相似仅有两个成员函数的返回值类型不同那么有什么方法可以像模板那样子实现类型的简化呢——同一个类模板实例化参数不同就是完全不同的类型。
改进
两个类归为一类
templateclass T,class Ref,class Ptr
struct _list_iterator
{typedef list_nodeT Node;typedef _list_iteratorT,Ref,Ptr self;//模板中的类型T可以用Ref和Ptr来分别取代//其中T 又可以被Ref代替 T* 可以被Ptr代替Node* _node;//创造一个结点_list_iterator(Node* node)//用一个结点的指针就能够造出一个迭代器:_node(node)//传入begin就会有对应位置的一个初始化结点出来{}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 operator!(const self s)//结点之间比较所以用迭代器的结构体名称{return _node ! s._node;}bool operator(const self s)//结点之间比较所以用迭代器的结构体名称{return _node s._node;}
};
那么对于list类要通过两个模板参数进行相关的控制
class list
{typedef list_nodeT Node;
public:typedef _list_iteratorT,T,T* iterator;typedef _list_iteratorT, const T, const T* const_iterator;iterator begin(){return iterator(_head-_next);//两种写法}iterator end(){return _head;}const_iterator begin()const{return const_iterator(_head-_next);}const_iterator end()const{return _head;}
....//
}
