list
list 和前面学习的 string 和 vector 稍有差别，list 存储空间是不连续的，不支持随机访问。list是一个双向带头循环链表，成员变量只有一个结点（Node）类型的指针 。在 C 语言部分，结点是个结构体，而在 C++ 中已经升级成为了类，可以实现自己的各种默认成员函数。这无疑成为了我们实现的难点。因为 list也是个类，其成员函数是 Node 类的指针，而且我们还要用模板来实现
定义结点类（list_node）
这里注意用 struct 定义结点(Node)类，因为 list 类要频繁使用 Node 类，友元太麻烦，下方迭代器类也是用 struct 定义，方便 list 频繁使用。我们定义的时候，随便把构造函数写一下，用 T() 空类型作缺省值，T 如果是内置类型 int，就会用 0 初始化。类名不用 Node，因为库里别的容器也会用到结点类，且实现方式不一样，这里区分一下
库里定义的
自己实现的：
为什么封装迭代器为类 ？
在 sting 和 vector 里面，迭代器可以实现成原生指针，解引用变得到了 val 值。而现在 list的存储空间不连续，迭代器++是到下一个结点位置，我们中间解引用得到的是一个结点，而我们现在需要的是解引用能到得结点里面的 val 值。对此我们不得不将迭代器封装成为一个类，通过重载 operator++ 和 operator* ，来实现迭代器的功能。
迭代器的成员变量只有一个就是 Node 类型的指针， 由于我们迭代器类需要结点类型的指针，于是我们 typedef 重命名一下 list_node 为 Node
库里面模板多参数的由来 ？
首先迭代器的类名不能直接是 iterator，别的容器也有迭代器，这里定义成 _list_iterator 。我们一开始是这么定义普通对象的 iterator ，那么思考我们如何定义 const 迭代器？
typedef _list_iterator iterator;
假如我们向下面这样定义 const 迭代器，第一眼看好像没什么问题，但仔细一想，迭代器的成员变量是一个 Node 指针，这么定义是结点不能移动指向下一个位置，反而结点指向的内容可以被修改。我们需要的是 operator* 解引用后，结点的 val 不能被修改，但是结点可以依然可以移动，指向下一个位置
typedef const _list_iterator const_iterator;
倘若我们像下面这样多定义一个 const 迭代器类，然后除了返回值不一样，其它照抄 _list_iterator 类来写的话，又会造成代码冗余
template
struct _list_const_iterator
{
……
}
typedef const _list_const_iterator const_iterator;
对此我们多加一个模板参数，T& ，对于普通对象用实例化为普通迭代器，const 对象就实例化为 const 迭代器，这样就解决了 operator* 函数返回值的问题，而库里面又重载了 operator-> 函数，返回值是 T*，有分普通和 const 对象，因此我们再增加一个模板参数 T*。在这里注意一下，operator-> 返回的是指针，假设我们有 list 迭代器 it，且 T 类型为一个结构体。当我们要用迭代器访问结构体内的成员，我们就要这样写，it->->(结构体内的成员)，第一个箭头调用 operator->，第二个指向结构体内的成员。但是编译器要求可读性，会优化为 it->(结构体内的成员)
typedef _list_iterator<T,T&> iterator;
typedef _list_iterator<T,const T&> const_iterator;
//普通迭代器
typedef _list_iterator<T,T&,T*> iterator;
//const迭代器
typedef _list_iterator<T,const T&,const T*> const_iterator
为什么普通迭代器不能隐式类型转换成const迭代器？
首先确保自己知道了 list 的大致实现原理。那么当我们自己实现一个 iterator 时，如果不加以注意，可能会发生如下情况：我们明明没有对权限进行放大，为什么编译器还会报错呢？
这是因为在泛型编程中，如果我们没有专门定义一个拷贝构造函数，那么默认的会以自己的类型为基准去考虑参数类型。不要用 int 可以隐式转化成 const int 的思维去考虑类模板。虽然 iterator和const_iterator 在底层调用的都是同一个类模板，但是在实例化的时候，编译器会认为这是两个不同的类型！所以这里原因很清楚了，当我们定义一个const_iterator时，其默认拷贝构造的参数也是const_iterator。
所以这里原因很清楚了，当我们定义一个 const_iterator 时，其默认拷贝构造的参数也是 const_iterator。因此，编译器才会报错说 iterator<int, int&, int*> 无法转化为 iterator<int, const int&, const int*> 。
解决方式也很简单，我们只需要在list_iterator 类中定义一个构造函数即可，参数为普通对象的迭代器类型，这样无论被拷贝对象时const迭代器还是普通迭代器都能调用这个函数，而且迭代器我们只需要完成浅拷贝，因为我们就是要指向同一块空间！！！
看看库里的：
迭代器位置指向及其返回值和整体代码
稍微注意一下，begin() 指向的是 _head 的下一个结点，而 end() 指向的是 _head 结点。增删查改中，由于 erase 函数删除结点会导致迭代器失效，因此需要更新返回新的迭代器，新的迭代器指向删除结点的下一个。 insert 函数的话也和 erase 函数保持一致返回迭代器，不过返回的是新插入的结点文章来源：https://www.toymoban.com/news/detail-598322.html
文章来源地址https://www.toymoban.com/news/detail-598322.html
#pragma once
#include <iostream>
#include <assert.h>
namespace Me
{
//定义结点
template<class T>
struct list_node
{
//定义为公有，让迭代器访问
list_node<T>* _prev;
list_node<T>* _next;
T _val;
//升级成为了类有自己的构造函数
list_node(const T& val = T())
: _prev(nullptr)
,_next(nullptr)
, _val(val)
{}
};
//封装迭代器,定义为公有，让list访问
template<class T,class Ref,class Ptr>
struct _list_iterator
{
typedef list_node<T> Node;
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
typedef _list_iterator<T, Ref, Ptr> self;
Node* _node;
//升级成为了类有自己的构造函数
_list_iterator(Node* node=nullptr)
:_node(node)
{}
_list_iterator(const iterator&x)
:_node(x._node)
{}
Ref operator*() const
{
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)
{
//这里不用单独写拷贝构造，浅拷贝就行，按需求来分析
_list_iterator<T> tmp(*this);
_node = _node->_prev;
return tmp;
}
Ptr operator->()
{
return &_node->_val;
}
bool operator!=(const self& it) const
{
return _node != it._node;
}
bool operator==(const self& it) const
{
return _node == it._node;
}
};
//定义链表
template<class T>
class list//定义链表
{
typedef list_node<T> Node;
public:
//普通迭代器
typedef _list_iterator<T,T&,T*> iterator;
//const迭代器
typedef _list_iterator<T,const T&,const T*> const_iterator;
//typedef const _list_iterator<T> const_iterator;
// 这样设计const迭代器是不行的，因为const迭代器期望指向内容不能修改
// 这样设计是迭代器本身不能修改
iterator begin()
{
//return _head->_next;
return iterator(_head->_next);
}
iterator end()
{
//左闭又开 _head不存储有效数据
//return iterator(_head);
return _head;
}
const_iterator begin() const
{
//return _head->_next;
return const_iterator(_head->_next);
}
const_iterator end() const
{
//左闭又开 _head不存储有效数据
//return iterator(_head);
return _head;
}
//哨兵卫头结点初始化
void empty_init()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
list()
{
empty_init();
}
list(list<T>& lt)
{
empty_init();
//迭代拷贝
for (auto& e : lt)
{
push_back(e);
}
}
void swap(list<T> lt)
{
std::swap(_head, lt._head);
}
//拷贝构造后交换
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
//清理部分
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
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);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
//assert(_head != _head->_next);
//Node* tail = _head->_prev;
//Node* tailP = tail->_prev;
//tailP->_next = _head;
//_head->_prev = tailP;
//delete tail;
erase(--end());
}
iterator insert(iterator pos, const T& x)
{
//调用结点的拷贝构造函数
Node* newnode = new Node(x);
//找插入的前一个结点
Node* prev = pos._node->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = pos._node;
pos._node->_prev = newnode;
return newnode;
}
iterator erase(iterator pos)
{
assert(pos._node != _head);
assert(_head != _head->_next);
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
pos._node = nullptr;
return next;
}
size_t size()
{
size_t sz = 0;
for (auto& e : *this)
{
sz++;
}
return sz;
}
void print()
{
iterator it = begin();
while (it != end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
private:
Node* _head;//带哨兵我的头节点
};
}
到了这里，关于【C++】list 模拟笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
