想建设一个网站 一般多少钱,网站建设问卷,浙江网商银行,网页版有意思的游戏排行榜1.什么是list list是CSTL容器中的一部分#xff0c;list是带头双向链表#xff0c;list的作用是它可以存储数据#xff0c;头删尾删的时间复杂度为O(1),但不支持随机访问。list与forward_list非常相似#xff1a;最主要的不同在于forward_list是单链表#xff0c;只能朝前…1.什么是list list是CSTL容器中的一部分list是带头双向链表list的作用是它可以存储数据头删尾删的时间复杂度为O(1),但不支持随机访问。list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。 2.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
list最重要的是迭代器的使用由于list是链表组成的所以list在空间中是不连续的只能用指针去访问不能使用[]来使用。
begin end返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器rbegin rend返回第一个元素的reverse_iterator,即end位置返回最后一个元素下一个位置的 reverse_iterator,即begin位置
3.list模拟实现
ps:要模拟实现list必须要熟悉list的底层结构以及其接口的含义
#pragma once
#include iostream
#include assert.h
//using namespace std;
namespace sss
{templateclass T//链表节点struct List_node{List_nodeT* prev;List_nodeT* next;T value;List_node(const T valT()):prev(nullptr),next(nullptr),value(val){}};//迭代器templateclass T, class Ref, class Ptrstruct iterator_iterator{typedef List_nodeT Node;typedef iterator_iteratorT,Ref,Ptr Self;//构造函数iterator_iterator(Node* nodenullptr):_node(node){;}//重载*Ref operator*(){return _node-val;}//重载-Ptr operator-(){return _node-val;}Self operator(){return _node-next;}//重载Self operator(int){Node* tmp(*this);_node _node-next;return tmp;}//重载--Self operator--(){return _node-prev;}Self operator--(int){Node* tmp(*this);_node _node-prev;return tmp;;}bool operator!(const Self l){return _node ! l._node;}bool operator(const Self l){return _node l._node;}private:Node* _node;};templateclass Tclass List{typedef List_nodeT* PNode;public:typedef iterator_iteratorT,T,T* iterator;typedef iterator_iteratorT,const T,const T* const_iterator;//返回头结点iterator begin(){return _Head-next;}const_iterator begin() const{return _Head-next;}//返回尾节点iterator end(){return _Head;}const_iterator end() const{return _Head;}//初始化为空void empty_init(){_Head new List_nodeT();_Head-prev _Head;_Head-next _Head;_size 0;}//构造函数List(){empty_init();}//拷贝构造函数List(const List_nodeT it){List(_Head);swap(it);}//赋值重载函数const List_nodeT operator(const List_nodeT it){swap(it);return *this;;}//析构函数~List(){clear();delete _Head;_Head nullptr;_size 0;}size_t size()const{return _size;}//判空bool empty() const{return _size 0;}T front(){return _Head-next-value;}const T front() const{return _Head-next-value;;}T back(){return _Head-prev-value;}const T back() const{return _Head-prev-value;}//尾插void push_back(const T val) { insert(begin(), val); }//尾删void pop_back() { erase(--end()); }//头插void push_front(const T val) { insert(begin(), val); }//头删void pop_front() { erase(begin()); }// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){PNode cur pos._node;PNode newnode new List_nodeT(val);PNode _prev cur-prev;//前_prev-next newnode;newnode-next cur;//后newnode-prev _prev;cur-prev newnode;//大小_size;return newnode;}// 删除pos位置的节点返回该节点的下一个位置iterator erase(iterator pos){PNode cur pos._node;PNode _next cur-next;//换位置cur-next _next;_next-prev cur-prev;//删除delete[] cur;//大小_size--;return _next;}void clear(){assert(_size ! 0);iterator it begin();while (it!end()){iterase(it);it;}}void swap(ListT l){std::swap(_Head, l._Head);std::swap(_size, l._size);}private:PNode _Head;size_t _size;};
}
4.list和vector的对比
vector:为动态顺序表支持随机访问空间利用率高为原生指针底层直接使用指针进行指针的加加在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效。多应用于高校存储不关心删除效率的场景。
list: 为链式存储不支持随机访问空间利用率不高为原生指针的封装在插入元素使迭代器不会失效但在删除元素是迭代器需要重新赋值否则会失效多应用于大量插入和删除操作不关心随机访问。
