手机网站设计报价,在网上注册公司的流程,北师大 网页制作与网站建设 考试,怎么开通网络在了解学习list实现之前我们首先了解一下关于迭代器的分类#xff1a;
按功能分类#xff1a;
正向迭代器 反向迭代器
const正向迭代器 const反向迭代器
按性质分类#xff1a;
单向迭代器 只能 例如单链表 双向迭代器 可#xff0c;也可-- 例如双…在了解学习list实现之前我们首先了解一下关于迭代器的分类
按功能分类
正向迭代器 反向迭代器
const正向迭代器 const反向迭代器
按性质分类
单向迭代器 只能 例如单链表 双向迭代器 可也可-- 例如双链表 map和set 随机迭代器 可加加可减减可可减 如顺序表vector string,deque(双端队列)
这些都是由容器的底层实现。 可以看到库中提供的list模板是带头双向链表故此我们实现它就大部分操作都是在数据结构中实现双链表时是一样。
目录
1.成员变量
节点类型的定义
迭代器
重载前置/--
重载后置/--
重载*与-
重载!与
const迭代器
迭代器的优化 成员函数
构造函数
析构函数
拷贝构造函数
容量
size
修饰符
insert()
erase ()
push_front()
pop_front()
push_back()
pop_back()
clear() 1.成员变量
templateclass Tclass mylist{typedef list_nodeT Node;typedef _list_iteratorT, T, T* iterator;typedef _list_iteratorT,const T,const T* const_iterator;
private:Node* _head;size_t _size;
......
}
因为实现的是链表故此我们的成员变量是链表头节点与链表的大小这里我们还需要给出
节点类型的定义
typedef list_nodeT Node;
templateclass Tstruct list_node{//我们给一个缺省值为T的匿名对象list_node(const T x T()):data(x), _next(nullptr), _prev(nullptr){}T data;list_nodeT* _next;list_nodeT* _prev;};
迭代器
因为我们实现的是链表那么迭代器的操作也就是链表节点的操作节点并非一般的数据类型
故此我们这里需要封装迭代器迭代器本质是节点的地址
//迭代器//认真思考的话迭代器模拟的是一个双链表节点的运动故我们封装迭代器里面一定是节点这里放入节点的地址//并且重载对应的运算符封装之后我们在定义为iteratortemplateclass Tstruct _list_iterator{//利用节点的指针实现迭代器typedef list_nodeT Node;typedef _list_iteratorT self;Node* _node;_list_iterator(Node* node):_node(node){}};
封装之后我们还需要重载对于迭代器的运算符这些重载都是在迭代器中的我只是为了吧方法一个个体现出来分开了。
重载前置/-- //重载加加self operator(){_node _node-_next;return *this;}self operator--(){_node _node-_prev;return *this;}
重载后置/-- self operator(int){self tmp(*this);_node _node-_next;return tmp;}self operator--(int){self tmp(*this);_node _node-prev;return tmp;}
重载*与- T* operator-(){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 iterator去认为是const迭代器,这样反而不能对迭代器进行等操作而需要我们去重新定义 定义const迭代器即内容是无法被修改由于我们访问内容是通过解引用的方法故我们需要修改访问的的这两个操作符其引用返回为const即内容无法被修改了。
templateclass Tstruct _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--(){_node _node-prev;return *this;}self operator(int){self tmp(*this);_node _node-_next;return tmp;}self operator--(int){self tmp(*this);_node _node-prev;return tmp;}const T* operator-(){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;}};
由于const迭代器与普通的迭代器区别也就在于访问的内容无法被修改也就是修改*与-这两个访问内容的操作符重新实现较为麻烦库中实现是增加了两个模板参数Ref,Ptr利用我们传的参数不一样从而决定用的是哪一个迭代器。
迭代器的优化
多出两个模板参数之后我们的*与-返回类型就是到时候传入时候的类型故这里我们直接用Ref与Ptr代替即可。
templateclass T,class Ref,class Ptrstruct _list_iterator{//利用节点的指针实现迭代器typedef list_nodeT Node;typedef _list_iteratorT,Ref,Ptr self;Node* _node;_list_iterator(Node* node):_node(node){}
} Ptr operator-(){return _node-data;}Ref operator*(){return _node-data;} 在list中对于模板迭代器我们传参不一样决定了是const还是普通
typedef _list_iteratorT, T, T* iterator;
typedef _list_iteratorT,const T,const T* const_iterator;iterator begin(){//return iterator(_head-data);return _head-_next;}iterator end(){return _head;//哨兵位就是链表的结束标志}const_iterator begin()const{return _head-_next;}const_iterator end()const{return _head;} 成员函数
构造函数 //通过调用一个初始化链表的函数来实现构造函数mylist(){empty_init();}
析构函数 //通过调用clear函数释放链表的节点在释放哨兵位即为析构~mylist(){clear();delete _head;_head nullptr;}
拷贝构造函数
//拷贝构造,将节点尾插入新的对象mylist(mylistT p){empty_init(p);for (auto it : p){push_back(it);}}
容量
size
size_t size(){return _size;}
修饰符
insert()
在基于实现insert我们的其他对list的操作都可以调用insert不需要都去对链表节点一个个操作
其次我们设计insert的返回值及参数位置都是迭代器直接用。
iterator insert(iterator pos, const T x)//插入也会使迭代器失效原位置节点找不到了{Node* cur pos._node;Node* newnode new Node(x);Node* prev cur-_prev;//链接节点prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return iterator(newnode);}
erase ()
//删除 这里删除cur节点释放掉会导致迭代器失效,因此要返回下一节点的迭代器iterator erase(iterator pos){Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;delete cur;prev-_next next;next-_prev prev;_size--;return iterator(next);}
push_front()
void push_front(){insert(begin());}
pop_front()
//头删void pop_front(){erase(begin());}
push_back()
//尾插void push_back(const T x){//Node* tail _head-preav;//Node* newnode new Node(x);连接节点//tail-_next newnode;//newnode-_next _head;//newnode-prev tail;//tail-_prev newnode;//tail newnode;//return (tail);insert(end(), x);}
pop_back()
//尾删void pop_back(){erase(end());}
clear()
//清数据void clear(){iterator it begin();while (it ! end()){it erase(it);}}
至此我们对list的简单实现就完成了。
