江西城开建设集团有限公司网站,淮北公司做网站,任务网站开发,购物网站论文目录 1. list的基本介绍
2. list的基本使用
2.1 list的构造
用法示例
2.2 list迭代器 用法示例
2.3. list容量#xff08;capacity#xff09;与访问#xff08;access)
用法示例
2.4 list modifiers
用法示例
2.5 list的迭代器失效
3.list的模拟实现
3.1…目录 1. list的基本介绍
2. list的基本使用
2.1 list的构造
用法示例
2.2 list迭代器 用法示例
2.3. list容量capacity与访问access)
用法示例
2.4 list modifiers
用法示例
2.5 list的迭代器失效
3.list的模拟实现
3.1 构造、析构
3.2 迭代器
3.3 list modifiers
4. list与vector的区别
5.完整代码 1. list的基本介绍 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 2. list的底层是双向带头循环链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 3. list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝后迭代。 4. 与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。 5. 与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素) 下图是list的底层结构。 从图中可以看出list底层由一个双向带头循环链表构成。假设有一链表listint lt, 头节点为_head则lt.begin()指向_head-next, lt.end()指向_head。
2. list的基本使用
2.1 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 list_test1()
{liststring lt(5, xy);//n val构造for (auto e : lt){cout e ;}cout endl;liststring llt(lt);//拷贝构造for (auto e : llt){cout e ;}cout endl;liststring lltt(lt.begin(), --lt.end());//迭代器区间构造for (auto e : lltt){cout e ;}
} 2.2 list迭代器
函数声明接口说明begin end返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器rbegin rend返回第一个元素的reverse_iterator,即end位置返回最后一个元素下一个位置的 reverse_iterator,即begin位置 用法示例
void list_test2()
{listint lt{ 1,2,3,4,5};//这样构造很奇特for (auto e : lt){cout e ;}cout endl;listint::iterator it lt.begin();//正向迭代器while (it ! lt.end()){cout *it ;it;}cout endl;listint::reverse_iterator rit lt.rbegin();//反向迭代器while (rit ! lt.rend()){cout *rit ;rit;}cout endl;
} 那么大家肯定会有一个疑问之前的stringvector迭代器可以是因为他们的底层物理空间是连续的但list底层可是双向带头循环链表啊它的结构物理空间可是不连续的我们不就错了吗
不急我们后面模拟实现的时候细讲。
2.3. list容量capacity与访问access)
函数声明接口说明empty检测list是否为空是返回true否则返回falsesize 返回list中有效节点的个数
front返回list的第一个节点中值的引用back返回list的最后一个节点中值的引用
用法示例
void list_test3()
{listint lt{ 1,2,3,4,5 };//这样构造很奇特for (auto e : lt){cout e ;}cout endl;cout 链表是否为空: ;if (lt.empty())cout true endl;elsecout false endl;cout size: lt.size() endl;cout Front Element: lt.front() endl;cout Back Element: lt.back() endl;lt.clear();cout 已执行链表清空操作链表是否为空: ;if (lt.empty())cout true endl;elsecout false endl;} 2.4 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中的有效元素
用法示例
void list_test4()
{listint lt{ 1,2,3,4,5 };//这样构造很奇特for (auto e : lt){cout e ;}cout endl;lt.push_back(0);lt.push_back(0);lt.push_front(9);lt.push_front(9);for (auto e : lt){cout e ;}cout endl;lt.pop_back();lt.pop_front();for (auto e : lt){cout e ;}cout endl;listint::iterator it lt.begin();while (it ! lt.end()){if (*it 5){it lt.erase(it);break;}it;}lt.insert(it, 999);for (auto e : lt){cout e ;}cout endl;
} 2.5 list的迭代器失效 这里我们将迭代器理解为指针list的迭代器失效是因为指针所指向的空间被销毁导致指针变为野指针。list的底层是双向带头循环链表因此list不存在插入导致迭代器失效的问题。list的迭代器失效出现在erase内如果该节点被删除空间已被销毁那么就必须更新迭代器否则迭代器失效。 3.list的模拟实现
list的模拟实现存在几个难点首先是使用了大量的typedef这会让人头晕眼花其次是模板迭代器的构建。我们快来看看吧。
注意list的迭代器由于list底层空间不连续的问题因此要实现和vector一样的迭代器效果即支持*itit需要对操作符进行重载所以要封装Node*。
list需要创建一个类内类Node用list访问Node类的变量。
下面是ListNode类类内包含双链表节点的三要素。
templateclass T
struct ListNode//节点的创建
{T _Date;ListNodeT* _next;ListNodeT* _prev;ListNode(const T xT())//节点的构造函数:_Date(x),_next(nullptr),_prev(nullptr){}
}; 3.1 构造、析构
这里的构造函数为简易版本只支持创建空链表。 void list_init()//初始化每一个节点
{_head new Node;//new调用Node的默认构造不传参_head-_next _head;_head-_prev _head;
}
list()
{list_init();
}
list(listT lt)//拷贝构造
{list_init();//创建头节点for (const auto e : lt){push_back(e);}
}void swap(listT tmp)
{std::swap(_head, tmp._head);
}//list operator(list lt)
listT operator(listT lt)
{swap(lt);return *this;
}
void clear()
{listT::iterator it this-begin();while (it ! end()){it erase(it);}
}
~list()
{delete _head;_head nullptr;
}
3.2 迭代器
前面说要对等操作符进行重载这时需要重新定义iterator类封装节点的指针通过指针对节点进行操作。且iterator类需要支持普通对象与const对象的访问因此需要定义成模板类。
模板类iterator
templateclass T,class Ref,class Ptr
struct _list_iterator//迭代器本质就是指针这里封装Node*,对Node的指针进行操作重载等操作符
{typedef ListNodeT Node;typedef _list_iteratorT,Ref,Ptr self;//typedef _list_iteratorT self;Node* _node;//成员变量public:_list_iterator(Node* node)//构造函数直接用node构建:_node(node){}//没有参数int 前置self operator()//重载{_node _node-_next;return *this;}self operator(int)//后置{Node* tmp _node;_node _node-_next;return tmp;}self operator--(){_node _node-_prev;return *this;}//返回临时对象出函数即销毁不可传引用self operator--(int)//后置--{Node* tmp _node;_node _node-_prev;return tmp;}Ptr operator-(){return _node-_Date;}Ref operator*(){return _node-_Date;}bool operator!(const self s){return _node ! s._node;}bool operator(const self s){return _node s._node;}
};
list类内的迭代器函数
typedef _list_iteratorT,T,T* iterator; //普通对象的迭代器
typedef _list_iteratorT,const T,const T* const_iterator; //const对象的迭代器
iterator begin()//指向头节点的下一个
{return _head-_next;
}iterator end()//指向头节点
{return _head;
}const_iterator begin() const//指向头节点的下一个
{return _head-_next;
}const_iterator end() const//指向头节点
{return _head;
} 这里模板参数有三个分别是TTT*这是为什么呢 T因为重载普通迭代器的*时返回值需要设为引用类型以便于外界可以更改。 T*重载-时由于list的-逻辑不能自洽list的重载-需要返回数据的地址 这里需要着重解释一下如果是listint,那么重载-完全没有问题但如果是listDate呢 Node的数据域是自定义类型又该怎么办呢 因此我们返回Node.Date的地址然后再解引用如果是内置类型不受影响如果是自定义类型稍加控制就ok了。 我们来看看示例
struct AA
{int _a1;int _a2;AA(int a1 1, int a2 1):_a1(a1), _a2(a2){}
};
void test_list5()
{listAA lt;AA aa1;lt.push_back(aa1);lt.push_back(AA());AA aa2(2, 2);lt.push_back(aa2);lt.push_back(AA(2, 2));listAA::iterator it lt.begin();while (it ! lt.end()){std::cout (*it)._a1 : (*it)._a2 std::endl;std::cout it.operator*()._a1 : it.operator*()._a2 std::endl;std::cout it-_a1 : it-_a2 std::endl;std::cout it.operator-()-_a1 : it.operator-()-_a2 std::endl;it;}std::cout std::endl;
}
Node的数据域存放的是AA类对象Node* ptrptr-Date就是AA类的实例化对象此时返回AA对象的地址也就是AA* p,p-就可以访问AA类对象的成员了。
3.3 list modifiers
这里需要注意erase的迭代器失效问题。
void push_back(const T xT())
{Node* node new Node;Node* tail _head-_prev;node-_Date x;tail-_next node;node-_next _head;_head-_prev node;node-_prev tail;
}iterator insert(iterator pos,const T x T())//不存在迭代器失效问题
{Node* node new Node;node-_Date x;Node* cur pos._node;Node* prev cur-_prev;cur-_prev node;node-_next cur;node-_prev prev;prev-_next node;return node;
}iterator erase(iterator pos)//这里的pos有可能会产生迭代器失效问题
{Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;cur nullptr;return next;//更新pos
}
4. list与vector的区别
list与vector都是cSTL序列容器的重要组成部分由于底层结构的不同造成了他们的功能和特性有所不同详见下表。
vectorlist底 层 结 构动态顺序表一段连续空间带头结点的双向循环链表随 机 访 问支持随机访问访问某个元素效率O(1)不支持随机访问访问某个元素 效率O(N)插 入 和 删 除任意位置插入和删除效率低需要搬移元素时间复杂 度为O(N)插入时有可能需要增容增容开辟新空 间拷贝元素释放旧空间导致效率更低任意位置插入和删除效率高不 需要搬移元素时间复杂度为 O(1)空 间 利 用 率底层为连续空间不容易造成内存碎片空间利用率 高缓存利用率高底层节点动态开辟小节点容易 造成内存碎片空间利用率低 缓存利用率低迭 代 器原生态指针对原生态指针(节点指针)进行封装迭 代 器 失 效在插入元素时要给所有的迭代器重新赋值因为插入 元素有可能会导致重新扩容致使原来迭代器失效删 除时当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效 删除元素时只会导致当前迭代 器失效其他迭代器不受影响使 用 场 景需要高效存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随 机访问 5.完整代码
templateclass T
struct ListNode//节点的创建
{T _Date;ListNodeT* _next;ListNodeT* _prev;ListNode(const T xT())//节点的构造函数:_Date(x),_next(nullptr),_prev(nullptr){}
};templateclass T,class Ref,class Ptr
struct _list_iterator//迭代器本质就是指针这里封装Node*,对Node的指针进行操作重载等操作符
{typedef ListNodeT Node;typedef _list_iteratorT,Ref,Ptr self;//typedef _list_iteratorT self;Node* _node;//成员变量public:_list_iterator(Node* node)//构造函数直接用node构建:_node(node){}//没有参数int 前置self operator()//重载{_node _node-_next;return *this;}self operator(int)//后置{Node* tmp _node;_node _node-_next;return tmp;}self operator--(){_node _node-_prev;return *this;}//返回临时对象出函数即销毁不可传引用self operator--(int)//后置--{Node* tmp _node;_node _node-_prev;return tmp;}Ptr operator-(){return _node-_Date;}Ref operator*(){return _node-_Date;}bool operator!(const self s){return _node ! s._node;}bool operator(const self s){return _node s._node;}
};templateclass T
class list
{typedef ListNodeT Node; //typedef
public:typedef _list_iteratorT,T,T* iterator; //普通对象的迭代器typedef _list_iteratorT,const T,const T* const_iterator; //const对象的迭代器iterator begin()//指向头节点的下一个{return _head-_next;}iterator end()//指向头节点{return _head;}const_iterator begin() const//指向头节点的下一个{return _head-_next;}const_iterator end() const//指向头节点{return _head;}void list_init()//初始化每一个节点{_head new Node;//new调用Node的默认构造不传参_head-_next _head;_head-_prev _head;}list(){list_init();}list(listT lt)//拷贝构造{list_init();//创建头节点for (const auto e : lt){push_back(e);}}void swap(listT tmp){std::swap(_head, tmp._head);}//list operator(list lt)listT operator(listT lt){swap(lt);return *this;}void clear(){listT::iterator it this-begin();while (it ! end()){it erase(it);}}~list(){delete _head;_head nullptr;}void push_back(const T xT()){Node* node new Node;Node* tail _head-_prev;node-_Date x;tail-_next node;node-_next _head;_head-_prev node;node-_prev tail;}iterator insert(iterator pos,const T x T())//不存在迭代器失效问题{Node* node new Node;node-_Date x;Node* cur pos._node;Node* prev cur-_prev;cur-_prev node;node-_next cur;node-_prev prev;prev-_next node;return node;}iterator erase(iterator pos)//这里的pos有可能会产生迭代器失效问题{Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;cur nullptr;return next;//更新pos}size_t size()const//返回size{int cnt 0;listint::const_iterator it begin();while (it ! end()){cnt;it;};return cnt;}bool empty()const//判空{return _head -_next _head;}private:Node* _head;//成员变量为ListNode* 即访问节点的指针
};
