北京 企业建网站,我有域名跟空间能教我做网站吗,网站建设进度计划,如何做微信个人网站目录
前言
一、list的结构
二、默认成员函数
构造函数
析构函数
clear
拷贝构造
赋值重载
swap
三、容量相关
empty
size
四、数据访问
front/back
五、普通迭代器
begin/end
六、const迭代器
begin/end
七、插入数据
insert
push_back
push_front
八、…目录
前言
一、list的结构
二、默认成员函数
构造函数
析构函数
clear
拷贝构造
赋值重载
swap
三、容量相关
empty
size
四、数据访问
front/back
五、普通迭代器
begin/end
六、const迭代器
begin/end
七、插入数据
insert
push_back
push_front
八、删除数据
erase
pop_back
pop_front
九、代码
总结 前言
我们之前讲解了string和vector的模拟实现它们都是类似于顺序表的结构string的底层是一个指针一个元素的数量一个空间总容量而vector的底层是三个指针这是它们结构上不一样的地方但是实现的方法和原理还是大差不差的那本篇我们来谈谈listlist的迭代器和之前的容器是不一样的而且是一个双向带头循环链表任意位置的插入删除效率都是O(1)那我们开始正题 一、list的结构
list的结构是一个一个的节点所以我们在定义的时候就要去定义一个节点
templateclass T
struct list_node
{list_nodeT* _prev;list_nodeT* _next;T _val;
}; _prev指向前一个节点 _next指向下一个节点 _val表示节点中存储的值 list_node这个类可以写成class然后放成公有也可以直接定义成struct的因为这个类中的成员在list这个类中会用到所以像这种节点类就直接放成公有就好 templateclass T
class list
{typedef list_nodeT Node;
private:Node* _head;size_t _size;
}; 对于list这个类我们需要先把list_node这个类给typedef否则一直用他太长了而且要带上模版参数要注意的是typedef也会受到访问限定符的限制所以在外面是看不到Node的然后我们用这个Node来定义一个头结点也就是指向头节点的指针_head然后还有一个成员函数是_size_size是用来返回链表内的数据个数的如果没有_size的话就只能遍历求一遍这样增加一个成员变量代价反而小了 二、默认成员函数
构造函数 构造函数要来初始化成员变量所以就需要先去给_head去new一个节点然后它的前驱和后继都指向自己_size初始化成0就好了因为头节点不存储有效数据所以也就不算做元素个数了 list()
{_head new Node;_head-_next _head;_head-_prev _head;_size 0;
}
对于Node这个类在new的时候会去调用它的构造函数所以我们要给Node类补上一个构造用匿名对象做这里的缺省参数
templateclass T
struct list_node
{list_nodeT* _prev;list_nodeT* _next;T _val;list_node(const T val T()):_prev(nullptr), _next(nullptr), _val(val){}
}; 析构函数
析构函数需要把所有的节点都释放了因为所有节点都是new出来的那就先来实现一个clear函数
clear clear是要清空除头节点外链表中所有的节点就要从头节点的下一个节点开始去删除每一个节点但是删除了当前节点就会找不到下一个节点所以要先保存一下下一个节点 void clear()
{Node* cur _head-_next;while (cur ! _head){Node* next cur-_next;delete cur;cur next;}
} cur表示的是当前节点next记录下一个节点的位置循环判断的条件就是不等于头结点就继续删删到最后一个节点那它的next就是头结点了也就证明删完了循环结束 那在析构函数中就先去调用clear先把后面链接的节点全部删掉然后再把头节点删掉并置空就好了 ~list()
{clear();delete _head;_head nullptr;
} 拷贝构造 这里就不能再去用memcpy或者赋值来写了因为list在物理上并不是连续的空间不可以用下标来访问所以采用的方法是遍历有数据的这个容器然后依次尾插进被拷贝的容器中 //l2(l1)
list(const listT l)
{_head new Node;_head-_next _head;_head-_prev _head;_size 0;for (auto e : l){push_back(e);}
} 然后这里的l2在插入数据前一定要去初始化要把头节点new出来再把前后都指向自己否则在访问时会出问题这里用的是范围for那就需要支持迭代器才可以并且push_back也还没有实现所以暂时这个拷贝构造是不能跑的大家可以等下面的实现完再回来看 赋值重载
赋值就写一个现代写法去调用拷贝构造就可以这个我们很详细的说过了在这里就不再多赘述了
swap
void swap(listT l)
{std::swap(_head, l._head);std::swap(_size, l._size);
} //l2 l1
listT operator(listT l)
{swap(l);return *this;
} 三、容量相关
empty 判空的逻辑是判断头节点的前驱和后继是不是指向自己且元素个数是否为0 bool empty() const
{return _head-_next _head _head-_prev _head _size 0;
} size size函数只需要返回_size的值就可以 size_t size() const
{return _size;
} 四、数据访问
front/back front就是返回第一个节点里存储的值back返回最后一个节点里的值一定要注意是第一个存储有效数据的节点所以是头结点的下一个节点而不是头节点中存储的值 front和back各自分别有两个版本一个普通版本一个const版本跟我们之前讲的一样普通对象优先调用普通版本如果没有普通版本再去调用const版本const对象只能调用const版本 T front()
{return _head-_next-_val;
}const T front() const
{return _head-_next-_val;
}T back()
{return _head-_prev-_val;
}const T back() const
{return _head-_prev-_val;
} 五、普通迭代器
我们在最开始的时候说过list的迭代器与前面的有些不一样我们就来看看list的迭代器有哪些不一样可以说list最重要的部分就是迭代器大家先来看可不可以这么写我们的迭代器呢
typedef Node* iterator 答案显而易见肯定是不可以的因为迭代器我们解引用是要拿到数据但是现在解引用拿到的是一个节点而且要向下一个位置走--要向前一个位置走现在这个迭代器走到哪去谁能知道呢所以我们要用运算符重载来控制这里的逻辑也就要再封装一个迭代器的类来控制 templateclass T
struct __list_iterator
{typedef list_nodeT Node;Node* _node;
};
在外面需要去访问这个类中的成员函数所以我们把这个迭代器类定义成struct的里面有一个节点的指针_node我们先来实现下*和-*就是返回数据的引用-是返回数据的地址
T operator*()
{return _node-_val;
}T* operator-()
{return (_node-_val);
} 然后是和--就是向下一个节点走--就是向前一个节点走而和--呢又分为前置和后置我们先实现前置前置的话就是_node走完返回迭代器的本身那这个迭代器类的名字太长了我们也同样来typedef一下 typedef __list_iteratorT Self;
这个typedef就和Node的typedef放在一起就行
Self operator()
{_node _node-_next;return *this;
} Self operator--()
{_node _node-_prev;return *this;
}
前置返回的是迭代器走完的结果所以就可以用引用返回 后置是返回或者--之前的值那就需要先保存一份才可以然后返回保存的这一份区分前置和后置就是给后置加上一个int类型的参数 Self operator(int)
{Self tmp(*this);_node _node-_next;return tmp;
}Self operator--(int)
{Self tmp(*this);_node _node-_prev;return tmp;
} 迭代器判断循环结束的条件还有一个不等于我们来实现一下就是比较两个指针一不一样就可以了 bool operator!(const Self s)
{return _node ! s._node;
}bool operator(const Self s)
{return _node s._node;
} begin/end begin就是返回头节点的下一个位置因为迭代器是左闭右开所以end应该返回的是最后一个有效数据的下一个位置也就是头节点_head iterator begin()
{return _head-_next;
}iterator end()
{return _head;
}
那在list这个类中需要用到iterator我们就把这个类给嵌到list这个类里这个要放成公有的外面要用迭代器
public:typedef __list_iteratorT iterator; 而且还要给迭代器类实现一个构造函数用节点指针去构造迭代器现在的begin和end是隐式类型转换构造加拷贝构造拷贝构造我们不需要实现迭代器去浅拷贝就可以了也可以返回匿名对象或者是先构造出来对象再返回这个对象这三种都可以我们这种是最简单的直接隐式类型的转换 __list_iterator(Node* node):_node(node)
{} 我们再结合迭代器的使用来看
int main()
{hx::listint l;hx::listint::iterator it l.begin();while (it ! l.end()){cout *it ;it;}cout endl;return 0;
}
需要什么我们就写什么就可以了迭代器也就是需要这几个函数不需要实现其他功能了那我们的普通迭代器就实现好了 六、const迭代器
下面我们来看一下const迭代器有了刚才的封装那const迭代器可不可以直接套上一个const呢
typedef __list_iteratorT iterator;
typedef const __list_iteratorT const_iterator; 这样写也是不行的因为这样写就是修饰迭代器本身不能修改了那迭代器本身都不能修改了还怎么/--呢所以const迭代器也是需要我们自己去封装一个自定义类型来控制那我们就照葫芦画瓢来实现一个 templateclass T
struct __list_const_iterator
{typedef __list_const_iteratorT Self;typedef list_nodeT Node;Node* _node;__list_const_iterator(Node* node):_node(node){}const T operator*(){return _node-_val;}const T* 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 Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
};那大家有没有发现普通迭代器和const迭代器不一样的地方就在于*和-的返回值其他的地方全都一样那这样设计就太冗余了我们有没有办法可以就用一个类来控制一下*和-的返回值呢其实很好办只需要增加模版参数就可以 templateclass T, class Ref, class Ptr
struct __list_iterator
{typedef __list_iteratorT, Ref, Ptr Self;typedef list_nodeT Node;Node* _node;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node-_val;}Ptr 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 Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
}; Ref是引用也就是operator*的返回值Ptr是指针也就是operator-的返回值然后不要忘记在typedef Self的时候把这两个模版参数给加上然后在list类中我们把后面的两个模版参数写死就可以了 typedef __list_iteratorT, T, T* iterator;
typedef __list_iteratorT, const T, const T* const_iterator;
begin/end
const_iterator begin() const
{return _head-_next;
}const_iterator end() const
{return _head;
}
begin和end还是一样的实现逻辑返回值变一样再设计成const成员函数就可以
那迭代器部分我们就说到这里因为这里可能会比较复杂三个类互相缠绕所以在文章的最后会把所有的代码给贴出来如果大家对这里还有不太懂的地方可以去参考 七、插入数据
insert insert是在某个迭代器插入一个val那就是把这个迭代器里存的节点指针定义出来然后找到前一个再新创建一个节点把他们之间互相链接起来就行了最后返回新插入的这个节点的迭代器 iterator insert(iterator pos, const T val)
{Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(val);prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return newnode;
} push_back
push_back是尾插直接去复用insert给一个迭代器位置
void push_back(const T val)
{insert(end(), val);
} end就是头结点那在头节点的前面插入也就是尾插 push_front
push_back是头插直接去复用insert给一个迭代器位置
void push_front(const T val)
{insert(begin(), val);
}
begin就是头结点的下一个位置在begin之前插入也就是在头结点和第一个节点之间插入就是头插 八、删除数据
erase erase是要删除某个迭代器位置那也是把迭代器里存的节点指针定义出来然后找到前后节点把前后节点互相连起来就好了最后再删除然后要返回删除的这个位置的下一个节点的迭代器 iterator erase(iterator pos)
{Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;--_size;return next;
} pop_back
pop_back是尾删直接去复用erase给一个迭代器位置
void pop_back()
{erase(--end());
}
end是头节点的位置那--end就是头结点的前一个也就是最后一个节点 pop_front
pop_front是头删直接去复用erase给一个迭代器位置 void pop_front(){erase(begin());}
begin是头结点的下一个位置也就是第一个存放有效数据的节点 九、代码
namespace hx
{templateclass Tstruct list_node{list_nodeT* _prev;list_nodeT* _next;T _val;list_node(const T val T()):_prev(nullptr), _next(nullptr), _val(val){}};templateclass T, class Ref, class Ptrstruct __list_iterator{typedef __list_iteratorT, Ref, Ptr Self;typedef list_nodeT Node;Node* _node;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node-_val;}Ptr 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 Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}};templateclass Tclass list{typedef list_nodeT Node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;iterator begin(){return _head-_next;}iterator end(){return _head;}const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head;}list(){_head new Node;_head-_next _head;_head-_prev _head;_size 0;}//l2(l1)list(const listT l){_head new Node;_head-_next _head;_head-_prev _head;_size 0;for (auto e : l){push_back(e);}}//l2 l1listT operator(listT l){swap(l);return *this;}~list(){clear();delete _head;_head nullptr;}void swap(listT l){std::swap(_head, l._head);std::swap(_size, l._size);}bool empty() const{return _head-_next _head _head-_prev _head _size 0;}size_t size() const{return _size;}void clear(){Node* cur _head-_next;while (cur ! _head){Node* next cur-_next;delete cur;cur next;}}T front(){return _head-_next-_val;}const T front() const{return _head-_next-_val;}T back(){return _head-_prev-_val;}const T back() const{return _head-_prev-_val;}iterator insert(iterator pos, const T val){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(val);prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return newnode;}iterator erase(iterator pos){Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;--_size;return next;}void push_back(const T val){insert(end(), val);}void pop_back(){erase(--end());}void push_front(const T val){insert(begin(), val);}void pop_front(){erase(begin());}private:Node* _head;size_t _size;};
} 总结
本篇文章我们讲了list以及关于迭代器部分list的迭代器类型是一个自定义类型跟以前不太一样但是这种方式在以前也还是很常见的比如map/setunordered map/unordered set还是要这么用迭代器部分都要去这样封装大家还是要习惯这种方式那本篇文章就到这里啦如果觉得下篇写的不错的小伙伴可以给小编一个一键三连表示支持感谢大家
