网站打不开了什么原因,企业网站开发文献综述,呼和浩特做网站哪家公司好,中国建设工程网官网查询cplusplus.com/reference/list/list/?kwlist
当我们大致阅读完list的cplusplus网站的文档时#xff0c;我们会发现它提供的接口大致上与我们的vector相同。当然的#xff0c;在常用接口的简单实现上它们也大体相同#xff0c;但是它们的构造函数与迭代器的实现却大有不同。… cplusplus.com/reference/list/list/?kwlist
当我们大致阅读完list的cplusplus网站的文档时我们会发现它提供的接口大致上与我们的vector相同。当然的在常用接口的简单实现上它们也大体相同但是它们的构造函数与迭代器的实现却大有不同。(食用本文时建议与文末的模拟实现代码一起食用效果更佳)
一list与vector在构造函数上的不同 1.1成员封装的不同
我们在vector中需要封装的成员只有我们顺序表的起始指针有效元素的末尾指针以及用来记录空间结束位置的指针 如果我们在list中便无法再这样封装因为我们的list存放数据的内存并不连续所以我们需要对链表的节点用额外的结构体封装而在原本的list类里面我们封装的成员则是链表的头结点
templateclass T
struct list_node
{T _data;list_nodeT* _next;list_nodeT* _prev;};
templateclass T
class list
{
void empty_init()
{_head new Node();_head-_next _head;_head-_prev _head;
}
list()
{empty_init();
}
typedef list_nodeT Node;
private:Node* _head;
};
1.2迭代器的封装的不同
在vector中迭代器可以直接简单的设置为我们存储数据类型的对应指针。但是在list中我们发现迭代器需要指向的是一个节点有人说那我直接照搬vector不也OK。但是这时候就会有个问题因为我们的节点相当于一个自定义类型后面在进行调用的时候不可避免的会去调用它的构造函数同时我们迭代器又会有许多的函数去使用所以迭代器也需要额外的用一个类来封装。
templateclass T, class Ref, class Ptr
struct list_iterator//tip
{typedef list_nodeT Node;typedef list_iteratorT, Ref, Ptr Self;
}; TIPS:这里将迭代器与结点成员设置为公开是为了方便list类的调用实际上我们在使用list时也无法直接调用这些成员这也是对成员的保护方式。
二list与vector在迭代器上的不同(重点) 2.1对迭代器的const修饰
在我们的vector中由于我们的迭代器本身就是我们存储数据的类型的相应指针所以我们可以通过直接加const的方式来实现我们的const_iterator。但是在list中由于我们的迭代器是指向一个自定义类型的指针而我们的自定义类型中存储数据。如果我们直接用const来修饰会发现我们此时无法修改迭代器指向的结点从而无法完成我们后续的遍历。如果我们要为const来再额外封装一个类会使代码看上去非常冗余。
在stl的源码中有着这样的几行代码
template class T, class Ref, class Ptr
struct __slist_iterator : public __slist_iterator_base
{typedef __slist_iteratorT, T, T* iterator;typedef __slist_iteratorT, const T, const T* const_iterator;typedef __slist_iteratorT, Ref, Ptr self;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef __slist_nodeT list_node;
我们发现它的模板参数有三个。其实由于我们的目的是为了源结点中的值无法被改变只需要我们在返回结点中的值时加上const修饰而我们获取存储数据的方式无非两种一种是对迭代器解引用(其中_node是当前迭代器指向的结点)
T operator*()
{return _node-_data;
}
或者通过-来获取
T* operator-()
{return _node-_data;
} 所以我们只需要对T*与T在模板实例化时用const修饰即可
typedef list_iteratorT,T,T* iterator;//tip
typedef list_iteratorT,const T,const T* const_iterator;//tip TIP:在迭代器的类型中我们又分为随机双向和单向迭代器从左向右为父级关系。在使用库中的sort时对list无法使用快排因为他是双向迭代器而vector之所以可以使用是因为他是随机迭代器。
2.2list反向迭代器的实现
通过上面的多个模板参数的引出我们可以对反向的迭代器Reverse_iterator来封装进行封装
templateclass Iterator
class ReverseListIterator
{// 注意此处typename的作用是明确告诉编译器Ref是Iterator类中的类型而不是静态成员变量// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef ReverseListIteratorIterator Self;
public://// 构造ReverseListIterator(Iterator it) : _it(it) {}//// 具有指针类似行为Ref operator*() {Iterator temp(_it);--temp;return *temp;}Ptr operator-() { return (operator*()); }//// 迭代器支持移动Self operator() {--_it;return *this;}Self operator(int) {Self temp(*this);--_it;return temp;}Self operator--() {_it;return *this;}Self operator--(int){Self temp(*this);_it;return temp;}//
// 迭代器支持比较
bool operator!(const Self l)const{ return _it ! l._it;}
bool operator(const Self l)const{ return _it ! l._it;}
Iterator _it;
};
原理其实就是我们2.1中介绍到的这里我们直接给出模拟实现代码。
三list与vector其他方面不同的总结(不仅是模拟实现上) 附件list的简单模拟实现代码(常用接口) /
#pragma once
#include iostream
#include algorithm
#include assert.h
#include list
using namespace std;namespace ELY {templateclass Tstruct list_node{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T()):_data(x), _next(nullptr), _prev(nullptr){}};templateclass T,class Ref,class Ptrstruct list_iterator//tip{typedef list_nodeT Node;typedef list_iteratorT,Ref,Ptr Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){_node _node-_next;return *this;}Self operator--(){_node _node-_prev;return *this;}Self operator--(int){Self tmp(*this);_node _node-_prev;return tmp;}Self operator(int){Self tmp(*this);_node _node-_next;return tmp;}bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}};templateclass Tclass list{void empty_init(){_head new Node();_head-_next _head;_head-_prev _head;}public:typedef list_nodeT Node;typedef list_iteratorT,T,T* iterator;//tiptypedef list_iteratorT,const T,const T* const_iterator;//tiplist(){empty_init();}list(const listT list){empty_init();for (auto i : list){push_back(i);}}listT operator(listT list){swap(list);return *this;}list(size_t n, const T val T()){empty_init();for (size_t i 0; i n; i){push_back(val);}}iterator begin(){return iterator(_head-_next);}const_iterator begin() const{return const_iterator(_head-_next);}iterator end() {return iterator(_head);}const_iterator end() const{return const_iterator(_head);}void push_back(const T x T()){Node* newnode new Node(x);Node* tail _head-_prev;newnode-_next _head;newnode-_prev tail;tail-_next newnode;_head-_prev newnode;}iterator insert(iterator pos, const T val)//tip{Node* newnode new Node(val);Node* cur pos._node;cur-_prev-_next newnode;newnode-_prev cur-_prev;cur-_prev newnode;newnode-_next cur;return iterator(newnode);}iterator push_front(const T val){return insert(begin(), val);}iterator erase(iterator pos){assert(pos ! end());Node* cur pos._node;cur-_next-_prev cur-_prev;cur-_prev-_next cur-_next;pos cur-_next;delete cur;return pos;}iterator pop_front(){return erase(begin());}iterator pop_back(){return erase(--end());}void clear(){auto i begin();while (i ! end()){i erase(i);}}void swap(listT list){std::swap(_head, list._head);}~list(){clear();delete _head;_head nullptr;}private:Node* _head;};
}
/
mylist.h
