模拟实现list / list迭代器
前言：学习C++的STL，我们不仅仅要求自己能够熟练地使用各种接口，我们还必须要求自己了解一下其底层的实现方法，这样可以帮助我们写出比较高效的代码程序！
⭐在本篇文章中，list的迭代器是重点，它不像string和vector的迭代器一样可以使用原生指针，至于为啥，您可以继续往下看看！
首先是关于list的基本概念：
⭐1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。 ⭐2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。 ⭐3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。 ⭐4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。 ⭐5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问,比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
模拟实现list
首先创建节点和list类，以及使用命名空间来防止冲突。
namespace my_list
{
//节点
template<class T>
struct ListNode
{
ListNode* _next;
ListNode* _prev;
T _data;
//new node创建节点的时候，要默认构造初始化
ListNode(const T& x)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};
//创建list类
template<class T>
class list
{
typedef ListNode<T> Node;
public:
private:
Node* _head;
size_t _size;
};
}构造函数
1.无参构造
因为list的一个带头双向循环链表，因此，构造的时候，第一个节点不带值，做头节点，其指针指向自己。在new node初始化的时候，因为T是泛型，如果T是string类等等，需要调用T的默认构造去初始化，T初始化后再传入节点的构造函数，进行节点的初始化。
list()
{
_head = new Node(T());
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}因为后续的接口实现，多处用到list的空初始化，因此，可以按照实现一个函数，专门用来空初始化list对象。
void empty_initialize()
{
_head = new Node(T());
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_initialize();
}2.迭代器区间构造
//迭代器区间构造
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
//创建哨兵位头节点
empty_initialize();
while (first != last)
{
push_back(*first);
++first;
}
}3.拷贝构造
传统写法：
先初始化lt2，然后lt1有多少节点，lt2也尾插多少，数据也得一样。这里需要注意两点：
第一点：for循环中，最好使用引用，因为T是泛型，如果T是string类，是vector类，那么在赋值给e的时候，就会不断地进行拷贝。
第二点：auto前加const，是基于实现了const迭代器的情况，如果没有实现，就不能加const。
//lt2(lt1)
list(const list<T>& lt)
{
//先初始化,搞一个哨兵位的头节点
empty_initialize();
for (const auto& e : lt)
{
push_back(e);
}
}现代版本的写法：
现代写法的思路就是找打工人，然后跟打工人交换。因为默认无论如何，即使是空的链表，也会有一个哨兵位的头节点。如果没有这个哨兵位的头节点，在交换之后，tmp会导致野指针问题，在析构的时候会报错！
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
} list(const list<T>& lt)
{
//得有一个哨兵位
empty_initialize();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}4.赋值
传统写法：
list<T>& operator=(const list<T>& lt)
{
//防止自己给自己赋值
if (this != <)
{
//先清掉原有的节点
clear();
for (auto& e : lt)
{
push_back(e);
}
}
return *this;
}现代写法：
赋值不同于拷贝，因为this本来就有自己的哨兵位，因此不需要调用empty_initialize();函数。传参并不是引用传参，原有有两个：第一个是最重要的，如果用了引用，就会修改传进来的参数的值。第二个是：lt是局部变量，出来作用域后会析构带走。而传统写法不会对传进来的参数的值进行修改，选择引用是比较好的，可以省掉一次拷贝构造。
//lt1 = lt2;
list<T>& operator=(const list<T> lt)
{
swap(lt);
return *this;
}5.析构函数
先将除头节点外的节点全部删掉，最后再单独释放头节点。clear()的实现在后面~
~list()
{
clear();
delete _head;
_head = nullptr;
}新增节点：
1.push_back(const T& x);
尾插很简单，就是修改一下指针而已。
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;
++_size;
}2.insert(iterator pos,const T&x);
iterator insert(iterator pos, const T& x)
{
Node* newnode = new Node(x);
Node* cur = pos._pnode;
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return iterator(newnode);
}3.push_front(const T& x);
复用insert就好，push_back()其实也可以服用insert。代码里面的begin()和end()是基于迭代器而实现的接口，迭代器的实现，在文章下面点。
void push_front(const T& x)
{
insert(begin(), x);
} 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;
insert(end(), x);
}删除节点：
1.erase(iterator pos);
前面说过，此处可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
解决的方法，便是更新pos，返回pos的下一个位置的即可。
iterator erase(iterator pos)
{
assert(pos != end());
Node* prev = pos._pnode->_prev;
Node* next = pos._pnode->_next;
prev->_next = next;
next->_prev = prev;
--_size;
delete pos._pnode;
return iterator(next);
}2.头删跟尾删。
服用erase();即可。尾删的时候，因为end()是最后一个数据的下一个位置，因此需要end()减减一下，则需要在迭代器的类域里面实现operator--()的接口。
//头删
void pop_front()
{
erase(begin());
}
//尾删
void pop_back()
{
erase(--end());
}3、清空节点
使用迭代器进行删除，erase函数会返回删除的节点的下一个节点！这里需要注意的是，while循环的条件it!=end()，不能改写为it<end()。因为，链表节点的地址不是连续的，不能这样判断。
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);//erase会返回下一个节点
}
}list迭代器：
迭代器，它是内嵌类型的，即是在某个类里面的。并且它是行为是像指针一样的！在上层中，每种迭代器的使用方法几乎一样，但是其底层实现的方法压根不一样！
如果我们像实现string类和vector类（官方库中不是使用原生指针）一样，直接使用原生指针，是不可以写出我们需要的迭代器的！
而指针重要的两个行为如下：
1.解引用 2.支持++或--
vector或string类的迭代器是可以使用原生指针，因为它们是一段连续的物理空间，不管是解引用还是++/--，都能够保证获取到指定位置的数据或到达指定的位置（因为指针的++，加的是一个对象的大小，T是多大，就+多大，指针就往前走多少步）。
但是对于链表，它的节点的地址是不连续的！此时原生指针（Node*）不能满足迭代器的行为！此时，类的封装的重要性就体现出来了！类的封装+运算符重载闪亮登场！
此时的迭代器，不再是内置类型，而是一个自定义类型，我们一步步往下讲。
初步写法：
我们初步的写法，便是先将++，解引用和判断相等的功能实现。所谓的解引用，就是返回当前节点的值，而++，链表的++，本质就是到下一个节点，那便是next！
注意这里没有写出拷贝构造，意味着当我们使用赋值的时候，是浅拷贝，这也是我们所需要的，因为需要迭代器的对象跟调用迭代器的对象指向同一个节点！这也是不写析构函数的原因，否则会对同一块空间进行两次析构！
template<class T>
struct __list_iterator
{
typedef ListNode<T> node;
node* _pnode;
__list_iterator(node* p)
:_pnode(p)
{}
//解引用
T& operator*()
{
return _pnode->_data;
}
//++
__list_iterator<T>& operator++()
{
_pnode = _pnode->_next;
return *this;
}
//--
__list_iterator<T>& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
//！=
bool poerator!=(const __list_iterator<T>& it)
{
return _pnode != it._pnode;
}
};此时，就可以在list类里面写出迭代器的两个函数：begin和end。需要注意的是，begin的位置，是头节点的下一个位置，因为这是带头链表。end的位置，是最后一个节点的下一个位置，那就是头节点了。
typedef __list_iterator<T> iterator;
iterator begin()
{
return iterator(_head->_next);//使用匿名对象
}
iterator end()
{
//iterator it(_head);
//return it;
return iterator(_head);
}const 迭代器
const迭代器，只读不写。那么，const迭代器该如何去实现呢？对于const迭代器的写法，会有以下误写！
第一种错写：直接在使用的迭代器前加个const，如下：
这个是我们自己写的，基于普通迭代器，然后使用的时候，加const
这样写是不行的！因为const迭代器中的const是用于保护指向的对象不被修改，迭代器本身可以被修改。因此，上面这种情况，会让迭代器本身，即it不能被修改，如果不能被修改，那么还怎么去访问数据？即迭代器it不能++往后走了！
第二种错写：在普通迭代器的类里面，加上成员函数的const版本：
这种错误，是建立在第一种错误之上的！如果我们这样子实现const迭代器后，在使用两种迭代器的时候，const迭代器的使用依然是这样子使用：
const list<int>::iterator it = lt.begin();
我承认，此时，const迭代器对象去解引用的时候，确实是会调用const版本的operator*()，而普通迭代器对象解引用的时候，也是去调用普通版本的operator*()。但是，重点是const版本迭代器不能++，即不能往后走！又回到了第一种错误身上！我们的const迭代器，是只读不写，如果不能让const迭代器++往后走，如何去读？难道实现一个const版本的operator++()吗？那么请operator++()这个函数接口，可以去实现const吗？显然是不行的！
正确的写法：
我们可以单独实现一个const版本的迭代器的类，只需要把operator*()变成const版本，然后其它的不变即可，接着begin()和end()也实现一个const版本即可！这样的话就能明确我们写的迭代器是const版本还是普通版本，然后去调用相应的接口函数。
但是捏，这种想法有个很明显的不好——代码冗余！解决办法就是传多个模板参数！
然后在list类里面，分别重命名两种迭代器，这种做法的本质就是复用代码，实际上是两种类！比如T的类型是int，当使用const_iterator,那么T和Ref就会推演成int和const int&，如果是普通迭代器，那么就会推演成int和int&。
template<class T,class Ref>
struct __list_iterator
{
typedef ListNode<T> node;
typedef __list_iterator<T, Ref> Self;
node* _pnode;
__list_iterator(node* p)
:_pnode(p)
{}
Ref operator*()
{
return _pnode->_data;
}
T* operator->()
{
return &_pnode->_data;
}
//++it 前置++
Self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
//it++ 后置++
Self operator++(int)
{
Self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
bool operator!=(const Self& it) const
{
return _pnode != it._pnode;
}
bool operator==(const Self& it) const
{
return _pnode == it._pnode;
}
//--it 前置--
Self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
//--it 后置--
Self operator--()
{
Self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
};那么，此时begin()和end()当然也要重载一份const版本的出来！
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}上面代码完善了以下所需的接口。其中的operator->()需要额外说明一下：
调用这个函数，返回的是数据的地址，比如数据是一个日期的数据，那就是返回Date*，但当我们去调用这个函数并且取其数据的时候，按道理来说，因为会有两个箭头：
第一个箭头，表示的是这个数据的的指针，第二个箭头是原生指针，表示的是解引用后的这个数据本身。
it->->year,it->->month,it->->day
但实际上我们在写的时候却不是这样，我们只需要写一个箭头即可，因为编译器为了可读性，做了特殊的处理，省略掉了一个箭头。
如果一个const迭代器对象使用operator->()并且试图对数据进行修改，我们发现确实被修改了，原因是T* operator->()是普通迭代器的版本，因此，我们需要再额外加一个模板参数，去分成const版本和普通版本！
此时，就完成了我们模拟实现list中，迭代器的最终版
template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef ListNode<T> node;
typedef __list_iterator<T, Ref,Ptr> Self;
node* _pnode;
__list_iterator(node* p)
:_pnode(p)
{}
Ref operator*()
{
return _pnode->_data;
}
Ptr operator->()
{
return &_pnode->_data;
}
//++it 前置++
Self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
//it++ 后置++
Self operator++(int)
{
Self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
bool operator!=(const Self& it) const
{
return _pnode != it._pnode;
}
bool operator==(const Self& it) const
{
return _pnode == it._pnode;
}
//--it 前置--
Self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
//--it 后置--
Self operator--()
{
Self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
};总结反思
list和vector的对比：
list和vector，说白了，就是链表跟顺序表这两兄弟的对比，这对活宝很幽默，对方的缺点是自身的优点，对方的优点是自身的缺点，有时候我们会突然区分不清他们的优缺点，因此来总结一下下！
vector的优点：
①下标的随机访问 ②尾插尾删比list的效率高 ③CPU高速缓冲命中率高。 这三点都是结构的优点！
vector的缺点：
①随机插入或删除数据效率低O(N) ②扩容有消耗，还存在一部分的空间浪费，因此扩两倍或1.5倍是比较合适的，扩容多了会浪费，少了还得再次扩容。
list的优点：
①按需申请释放，无需扩容 ②任意位置插入删除，时间复杂度是O(1)
list的缺点：
①不支持下标随机访问 ②CPU高速缓冲命中率低
使用情况：
如果大量数据需要在中间（反正不是头和尾）插入删除的时候，就用list，如果是大量在头和尾插入或删除就用vector。
迭代器失效总结
vector的迭代器失效是在insert和erase，即插入和删除数据都有可能导致迭代器失效，因为位置发生了变化。
list的迭代器失效是在erase，即删除节点的时候会导致迭代器失效，因为迭代器指向的节点被删除了。
解决的方法是更新迭代器，即返回迭代器的位置。
而对于string类。string的迭代器也会失效，跟vector类似，但是一般不会去关注string迭代器失效问题。因为vector和list的insert和erase接口，参数给的是迭代器，而string常用的给的是下标，迭代器支持的用得很少。
vector | list | |
|---|---|---|
底 层 结 构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
随 机 访 问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某 效率O(N) |
插 入 和 删 除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂 度为O(N)，插入时有可能需要增容，增容：开辟新空 间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率 需要搬移元素，时间复杂 O(1) |
空 间 利 用 率 | 底层为连续空间，不容易造成内存碎片，空间利用率 高，缓存利用率高 | 底层节点动态开辟，小节 造成内存碎片，空间利用 缓存利用率低 |
迭 代 器 | 原生态指针 | 对原生态指针(节点指针)进 |
迭 代 器 失 效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入 元素有可能会导致重新扩容，致使原来迭代器失效，删 除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器 删除元素时，只会导致当 器失效，其他迭代器不受 |
使 用 场 景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不 机访问 |
相关文章
- 大数据必学Java基础（五十四）：List接口深入了解
- list分组成map这样做更简单！
- Java 中初始化 List 集合的 8 种方式
- java list 转json 字符串_Java之JSON字符串与List集合之间相互转换
- 【C++】STL 模拟实现之 list
- 数据库查询出的数据list 集合，转为json 的形式存到redis
- 【C++】list迭代器的深度剖析及模拟实现（感受类封装，类和对象的思想）
- ORA-01470: In-list iteration does not support mixed operators ORACLE 报错 故障修复 远程处理
- Python list根据下标删除元素详解编程语言
- 《Drools7.0.0.Final规则引擎教程》相同对象and List使用详解编程语言
- LIST-PROCESSING用法 ABAP任意时刻进行List输出_SAP详解编程语言
- 利用Redis构建新的List存储方式（redis存储list）
- Redis 轻松存储列表数据：使用 Redis 保存 List 的方法（redis保存list）
- Redis如何实现列表的复制？（redis复制list）
- Redis如何清空List：技巧分享（redis清空list）
- 性能优化提升Redis List性能的简单方法（redis的list）
- 以List形式存储至Redis中（往redis里存list）
- 清除redis中的列表数据（清空redis list）
- 警惕Redis List被空出（redis里list为空）
- Python中字典(dict)和列表(list)的排序方法实例