目录
迭代器
介绍
种类
本质
介绍
模拟实现
注意点
代码
迭代器
介绍
在C++中，迭代器（Iterators）是一种用于遍历容器（如数组、vector、list等）中元素的工具
无论容器的具体实现细节如何,访问容器中的元素的方法都是统一的,使用者不需要知道具体实现的细节
- 迭代器的概念类似于指针，但迭代器更为通用，可以适用于各种不同类型的容器(且不同对象的迭代器,种类也不同)
- 迭代器在算法函数中也可以使用,这样可以兼容不同的容器(比如sort,find),就可以使用通用的算法模板
种类
迭代器分为几种不同类型，每种类型对应不同的容器特性和访问方式：
输入迭代器（Input Iterator）：仅支持从容器中读取数据，类似于只读操作。它们一次只能移动一个位置，不允许修改容器的元素。
输出迭代器（Output Iterator）：仅支持向容器中写入数据，类似于只写操作。与输入迭代器类似，一次只能移动一个位置。
前向迭代器（Forward Iterator）：支持读取和写入操作，并且可以多次遍历容器。每次移动一个位置。
双向迭代器（Bidirectional Iterator）：与前向迭代器类似，但可以向前和向后移动，每次一个位置。
随机访问迭代器（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 Iterator
iterator 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 Capacity
size_t size() const
{
return _size;
}
bool empty() const
{
return _size == 0;
}
// List Access
T &front(){
return *begin();
}
const T &front() const{
return *begin();
}
T &back(){
return *(--end());
}
const T &back() const{
return *(--end());
}
// List Modify
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)
{
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;
};
};
