list

目录

迭代器

介绍

种类 

本质

介绍

模拟实现

注意点

代码 

---

迭代器

介绍

在C++中，迭代器（Iterators）是一种用于遍历容器（如数组、vector、list等）中元素的工具

无论容器的具体实现细节如何,访问容器中的元素的方法都是统一的,使用者不需要知道具体实现的细节

• 迭代器的概念类似于指针，但迭代器更为通用，可以适用于各种不同类型的容器(且不同对象的迭代器,种类也不同)
• 迭代器在算法函数中也可以使用,这样可以兼容不同的容器(比如sort,find),就可以使用通用的算法模板

种类 

迭代器分为几种不同类型，每种类型对应不同的容器特性和访问方式：

1. 输入迭代器（Input Iterator）：仅支持从容器中读取数据，类似于只读操作。它们一次只能移动一个位置，不允许修改容器的元素。

2. 输出迭代器（Output Iterator）：仅支持向容器中写入数据，类似于只写操作。与输入迭代器类似，一次只能移动一个位置。

3. 前向迭代器（Forward Iterator）：支持读取和写入操作，并且可以多次遍历容器。每次移动一个位置。

4. 双向迭代器（Bidirectional Iterator）：与前向迭代器类似，但可以向前和向后移动，每次一个位置。

5. 随机访问迭代器（Random Access Iterator）：具有最强大的功能，可以在常量时间内跳转到容器中的任何位置，支持读取、写入和算术操作

• 这几种迭代器互相有包含关系,比如可以使用双向迭代器的,也可以使用随机迭代器

• 

• 不同的迭代器用以支持遍历不同类型的容器,以及限制了算法函数兼容的容器类型(比如sort就不支持list类型)
• 
• 每个容器都有自己对应的迭代器类型
• 

本质

实际上都是指针,有些容器的迭代器可以直接使用指针(eg:vector),但有些不行(eg: list)

• list的物理空间并不连续,直接使用无法实现++的效果,其他功能也不行
• 因此就需要创建一个类,来规定迭代器的操作

介绍

list是标准模板库（STL）提供的一个双向带头链表容器类

上面有说,list并不支持sort,但list内部有自己的sort

• 虽然是这样没错,但既然不支持,自然有它的道理
• 内部的sort在遇到大数据时,远不如 "将数据拷贝到vector中,由vector使用sort排序,再将排序后的数据恢复成list" 的效率高
• 当然,小数据的时候就不需要这些麻烦的操作了,这时候内部的sort还是很方便嘟

模拟实现

注意点

• 迭代器封装+结点封装(以及进行了重命名,会有各种嵌套)
• 结点类中有前后指针+数据,list类中有头结点指针+结点个数,迭代器是结点指针包装后的产物

• const迭代器的实现 (模板参数)
• 两种迭代器 在list类中传参+重命名 实例化,可以传指针构造,也有拷贝构造

• ' -> '符号的重载 (->重载函数返回指针,因此访问迭代器的实际语法应为 it -> ->begin(),是编译器简化成了只有一个->)
• list的多种拷贝构造

代码 

#include <iostream>
#include <assert.h>
#include <string>using namespace std;namespace bit
{// List的节点类template <class T>struct ListNode // struct默认公有(因为不会有人去访问结点成员的){typedef ListNode<T> *PNode;ListNode(const T &val = T()): _ppre(nullptr), _pnext(nullptr), _val(val){};PNode _ppre;PNode _pnext;T _val;};// List的迭代器类 -- 因为无法直接使用指针作为迭代器,需要手动添加功能template <class T, class Ref, class Ptr> // ref用于标记*时对象的const属性,ptr用于标记->时返回对象的const属性class ListIterator{public:typedef ListNode<T> *PNode;             // 指针重命名typedef ListIterator<T, Ref, Ptr> Self; // 迭代器重命名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){return _pNode != l._pNode;}bool operator==(const Self &l){return _pNode == l._pNode;}};// list类template <class T>class mylist{typedef ListNode<T> Node;typedef Node *PNode;public: // 两种迭代器typedef ListIterator<T, T &, T *> iterator;typedef ListIterator<T, const T &, const T &> const_iterator;public:// List的构造mylist(){CreateHead();}mylist(int n, const T &value = T()){CreateHead();PNode p = _pHead;for (size_t i = 0; i < n; ++i){push_back(value);}_size += n;}template <class Iterator>mylist(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);++first;}}mylist(const mylist<T> &l){CreateHead();for (auto c : l){push_back(c);}}mylist<T> &operator=(const mylist<T> l){swap(l);return (*this);}~mylist(){// clear();// delete[] _pHead;while (!empty()){erase(begin());}}// List Iteratoriterator begin(){return iterator(_pHead->_pnext);}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(_pHead->_pnext);}const_iterator end() const{return const_iterator(_pHead);}// List Capacitysize_t size() const{return _size;}bool empty() const{return _size == 0;}// List AccessT &front(){return *begin();}const T &front() const{return *begin();}T &back(){return *(--end());}const T &back() const{return *(--end());}// List Modifyvoid 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){PNode cur = pos._pNode;PNode pre = cur->_ppre;PNode newnode = new Node(val);newnode->_pnext = cur;pre->_pnext = newnode;cur->_ppre = newnode;newnode->_ppre = pre;_size++;return newnode;}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){PNode cur = pos._pNode;PNode pre = cur->_ppre, next = cur->_pnext;pre->_pnext = cur->_pnext;cur->_pnext->_ppre = pre;delete cur;--_size;return next;}void clear(){PNode cur = _pHead->_pnext;while (cur != _pHead){PNode tmp = cur;cur = cur->_pnext;delete tmp;}_size = 0;// iterator it = begin();// while (it != end())// {//     it = erase(it);// }}void swap(mylist<T> &l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}private:void CreateHead(){_pHead = new Node;_pHead->_pnext = _pHead;_pHead->_ppre = _pHead;_size = 0;}PNode _pHead;size_t _size;};
};