网站开发工程师专业好不好,wordpress keywords插件,网站建设必备,黑龙江建设网官方网站监理查询文章目录 1.list类的介绍2.list的基本用法2.1 基本用法2.2 迭代器失效2.3 reverse(逆置)2.3 sort(排序)2.4 unique(去重)2.5 splice(转移) 3.list的底层(模拟实现)3.1 list的3.2 修改链表问题3.3 完整代码 1.list类的介绍 list是可以在常数范围内在任意位置进行插入和删除的序列… 文章目录 1.list类的介绍2.list的基本用法2.1 基本用法2.2 迭代器失效2.3 reverse(逆置)2.3 sort(排序)2.4 unique(去重)2.5 splice(转移) 3.list的底层(模拟实现)3.1 list的3.2 修改链表问题3.3 完整代码 1.list类的介绍 list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 2.list的基本用法
2.1 基本用法 前面的用法大多都和string和vector差不都这些用法就不再赘述
2.2 迭代器失效 2.3 reverse(逆置) 2.3 sort(排序) 2.4 unique(去重) 2.5 splice(转移) 3.list的底层(模拟实现)
3.1 list的
大致思路还是和之前一样的但是List这里有需要专门说明的地方 因为list的存储空间不像vector一样是连续的链表吗就是一个地址连一个地址。 所以它不能像vector一样随便的和n这样操作。 所以我们需要typedef一个模板来重载我们的运算符 templateclass Tstruct ListIterator{typedef ListNodeT Node;typedef ListIteratorT Self;Node* _node;ListIterator(Node* node):_node(node){}// *itT operator*(){return _node-_data;}// it-T* operator-(){return _node-_data;}// it前置Self operator(){_node _node-_next;return *this;}//it后置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 it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}};3.2 修改链表问题 但是这样分别写两个ListIterator和ListConstIterator就非常的浪费那么有没有什么办法合二为一呢 添加类模板参数 3.3 完整代码
mylist.h:
#pragma once
#includeiostream
using namespace std;namespace my
{// List的节点类templateclass Tstruct ListNode{ListNodeT* _pPre;ListNodeT* _pNext;T _val;ListNode(const T val T()):_pNext(nullptr), _pPre(nullptr), _val(val){}};//List的迭代器类templateclass T, class Ref, class Ptrclass ListIterator{typedef ListNodeT* PNode;typedef ListIteratorT, Ref, Ptr Self;public:PNode _pNode;public:ListIterator(PNode pNode nullptr):_pNode(pNode){}ListIterator(const Self l): _pNode(l._pNode){}T operator*(){return _pNode-_val;}T* operator-(){return _pNode-_val;}Self operator()//前置{_pNode _pNode-_pNext;return *this;}Self operator(int)//后置{Self tmp(*this);_pNode _pNode-_pNext;return tmp;}Self operator--(){_pNode _pNode-_pPre;return *this;}Self operator--(int){Self tmp(*this);_pNode _pNode-_pPre;return tmp;}bool operator!(const Self l) const{return _pNode ! l._pNode;}bool operator(const Self l) const{return _pNode l._pNode;}};//list类templateclass Tclass list{typedef ListNodeT Node;typedef Node* PNode;private:void CreateHead(){// 创建头节点_pHead new Node;_pHead-_pNext _pHead;_pHead-_pPre _pHead;_size 0;}PNode _pHead;size_t _size;public:typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T const_iterator;public:///// List的构造void empty_init(){_pHead new Node;_pHead-_pNext _pHead;_pHead-_pPre _pHead;_size 0;}list(){empty_init();}list(int n, const T value T()){// 创建包含 n 个值为 value 的节点的链表empty_init();for (int i 0; i n; i) {push_back(value);}}template class Iteratorlist(Iterator first, Iterator last){// 通过迭代器范围 [first, last) 创建链表empty_init();while (first ! last) {push_back(*first);first;}}list(const listT l){empty_init();for (auto e : l){push_back(e);}}listT operator(const listT l){if (this ! l) {listT tmp(l);swap(tmp);}return *this;}~list(){clear();delete _pHead;_pHead nullptr;}///// List Iteratoriterator begin(){return _pHead-_pNext;}iterator end(){return _pHead;}const_iterator begin() const{return _pHead-_pNext;}const_iterator end() const{return _pHead;}///// List Capacitysize_t size()const{return _size;}bool empty()const{return _size 0;}// List AccessT front(){// 返回链表的第一个元素return _pHead-_pNext-_val;}const T front()const{// 返回链表的第一个元素常量版本return _pHead-_pNext-_val;}T back(){// 返回链表的最后一个元素return _pHead-_pPre-_val;}const T back()const{// 返回链表的最后一个元素return _pHead-_pPre-_val;}// List Modify/*void push_back(const T x){Node* newnode new Node(x);Node* tail _head-_prev;tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;}*/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()); }// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){Node* cur pos._pNode;Node* newnode new Node(val);Node* prev cur-_pPre;prev-_pNext newnode;newnode-_pPre prev;newnode-_pNext cur;cur-_pPre newnode;_size;return iterator(newnode);}// 删除pos位置的节点返回该节点的下一个位置iterator erase(iterator pos){Node* cur pos._pNode;Node* prev cur-_pPre;Node* next cur-_pNext;prev-_pNext next;next-_pPre prev;delete cur;_size--;return iterator(next);}void clear(){iterator l begin();while (l ! end()){l erase(l);}}void swap(listT l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}};void test_list1(){my::listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);// 使用迭代器遍历链表并修改元素值for (auto it lt.begin(); it ! lt.end(); it){*it 10; // 通过迭代器访问元素值cout *it ;}cout endl;lt.push_front(10);lt.push_front(20);lt.push_front(30);// 使用范围-based for 循环遍历链表for (auto e : lt){cout e ;}cout endl;lt.pop_back();lt.pop_back();lt.pop_front();lt.pop_front();// 再次使用范围-based for 循环遍历链表for (auto e : lt){cout e ;}cout endl;}
};main.cpp:
#define _CRT_SECURE_NO_WARNINGS 1
#includemylist.hint main()
{my::test_list1();return 0;
}
