合肥市网站建设 小程序,wordpress半透明,东莞网站建设公司怎么做,铁道部售票网站多少钱建设1. 标准库中的list类
list 类 的介绍#xff1a;
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代
2. list与forward_list非常相似#xff1a;最主要的不同在于forward_list是单链表
3. 与其他的序列式容器相比(a…1. 标准库中的list类
list 类 的介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代
2. list与forward_list非常相似最主要的不同在于forward_list是单链表
3. 与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好只是不支持任意位置的随机访问 a. list 的构造函数
list() (无参构造函数)list (const list x) 拷贝构造list (InputIterator first, InputIterator last) 用[first, last)区间中的元素构造list
list (size_type n, const value_type val value_type()) 构造的list中包含n个值为val的元素
注意
list 的迭代器是双向迭代器完成 , --可以支持传单向迭代器( 完成 ) 和双向迭代器 b. list 增删查改
push_back (尾插)push_front (头插)pop_back (尾删)pop_front (头删)insert (在某一位置前增加新节点) 代码举例1 #include iostream
#include list
using namespace std;int main()
{listint lt;lt.push_back(0);lt.push_back(10);lt.push_back(20);lt.push_back(30);listint ::iterator it lt.begin();it;lt.insert(it,70);it lt.begin();while(it ! lt.end()){cout *it endl;it;}
} 运行结果 earse (删除某一位置的节点) 代码举例2 #include iostream
#include list
using namespace std;int main()
{listint lt;lt.push_back(0);lt.push_back(10);lt.push_back(20);lt.push_back(30);listint ::iterator it lt.begin();it;lt.erase(it);it lt.begin();while(it ! lt.end()){cout *it endl;it;}
} 运行结果 swap ( 交换两个list中的元素 ) 代码举例3 #include iostream
#include list
using namespace std;int main()
{listint lt;lt.push_back(10);lt.push_back(20);lt.push_back(30);listint llt;llt.push_back(4);llt.push_back(5);llt.push_back(6);lt.swap(llt);auto it lt.begin();while(it ! lt.end()){cout *it ;it;}cout endl;for (auto i : llt){cout i ;}
} 运行结果 clear (清除有效节点即不包括哨兵位) c. list 容量 d. list 获取元素 e. list 迭代器
begin end ( 返回第一个元素的迭代器 返回最后一个元素下一个位置的迭代器 ) 画图分析 rbegin rend 返回第一个元素的reverse_iterator,即end位置返回最后一个元素下一个位置的 reverse_iterator,即begin位置 注意
反向迭代器的模拟实现和我们理解的有偏差图上为了理解我们可以认为rbegin是最后一个元素rend是第一个元素的前一个位置
但是实际上rbegin指向的位置就是end的位置rend指向的位置就是rbegin的位置但是在解引用时会运算符重载 *得到该位置的上一个位置 详情看 list 模拟实现 2. 迭代器失效
list 迭代器类似一个指针指向节点的地址 (具体详情看 list 的模拟实现)
所以在发生 erase 的时候容易造成迭代器失效(即野指针) 3. list 类的模拟实现 代码 namespace lhy
{templateclass T
struct ListNode
{
public:ListNode* prev;ListNode* next;T val;ListNode(const T t T()){prev next nullptr;val t;}
};
templateclass T,class Ref,class Ptr
class list_iterator
{
public:typedef list_iteratorT,Ref,Ptr self;list_iterator(ListNodeT* n):_node(n){}Ptr operator-(){return _node-val;}Ref 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 tmp;}bool operator!(const list_iterator t){return _node ! t._node;}bool operator(const list_iterator t){return _node t._node;}ListNodeT* _node;
};templateclass iterator,class Ref,class Ptrclass list_converse_iterator{private:iterator com;public:typedef list_converse_iterator self;list_converse_iterator(iterator it):com(it){}Ptr operator-(){return (*com);}Ref operator*(){iterator tmp com;--tmp;return *tmp;}self operator(){--com;return *this;}self operator(int){self tmp *this;--*this;return tmp;}self operator--(){com;return *this;}self operator--(int){self tmp *this;*this;return tmp;}bool operator!(const self t){return com ! t.com;}bool operator(const self t){return com t.com;}};templateclass Tclass List{public:typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;typedef list_converse_iteratoriterator, T, T* converse_iterator;typedef list_converse_iteratoriterator, const T,const T* const_converse_iterator;List(){node new ListNodeT;node-next node;node-prev node;}iterator begin(){return iterator(node-next);}const const_iterator begin() const{return const_iterator(node-next);}iterator end(){return iterator(node);}const const_iterator end() const{return const_iterator(node);}converse_iterator rbegin(){return converse_iterator(end());}const_converse_iterator rbegin() const{return const_converse_iterator(end());}converse_iterator rend(){return converse_iterator(begin());}const_converse_iterator rend(){return const_converse_iterator(begin());}void push_back(const T val){ListNodeT* ptail node-prev;ListNodeT* newnode new ListNodeT(val);ptail-next newnode;newnode-next node; newnode-prev ptail;node-prev newnode;}void push_front(const T x){insert(begin(), x);}void insert(iterator pos,const T x){ListNodeT* cur pos._node;ListNodeT* newnode new ListNodeT(x);newnode-next cur;newnode-prev cur-prev;cur-prev-next newnode;cur-prev newnode;}void earse(iterator pos){ListNodeT* cur pos._node;assert(cur ! node);ListNodeT* _prev cur-prev;ListNodeT* _next cur-next;_prev-next _next;_next-prev _prev;delete cur;}
private:ListNodeT* node;
};
} list 迭代器的实现 单看这一个类的实现可能会疑惑已经有一个 List 类了为什么还要加一个 list_iterator 类并且很容易发现两个类的成员变量是一样的 如listint :: iterator it; 我们希望 *it 得到的是T类型的变量这里是int 类型 而 it 得到的是下一个节点的地址 如果是只有 List 类无法实现 因为如果 typedef ListNode* iterator 那么 *it 的类型就是 ListNode; it 也不是下一个结点的地址这是链表开辟的空间不是连续的 所以这里的 list_iterator 类是为了运算符重载 *和 代码注意事项 可以和下面的对应 注意 const iterator 修饰的是 ListNodeT*即指针不可以更改但是指针所指向的内容可以更改 const_iterator 修饰的是 const ListNodeT* ,即指针所指向的内容不可更改 注意 对于这个运算符重载实际写的时候只要写一个 - 就行编译器简化两个 - 模板第一个传的是 正向迭代器利用正向迭代器来实现反向迭代器的功能 这里 运算符重载* 让正向迭代器--再解引用是为了得到 原先T 类型的数据的前一个数据原因如下 这里传递是 end() 但是 对应的数据不是我们想要的 才会在解引用得到前一个数据的值
