C++-list模拟实现
###模拟实现list需要先看源码，了解基本的结构和设计思路
###list底层是双向链表，每一个节点包含数据域和两个指针（一个指向后一个节点，一个指向前一个节点），并且list带有一个哨兵位；
###链表的结构的实现并不困难，这里阻碍实现的是迭代器；像string和vector底层结构是连续的，可以直接++、--、+几、-几来实现随机访问每一个数据，它们的迭代器的实现（迭代器的基本操作）也容易，但是list底层双向指针不能++、--来访问到下一个数据，这个时候要单独封装一个迭代器类模板实现需要的迭代器；
一、list的节点结构
//节点结构
template<class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
list_node(const T& data = T())
:_data(data),
_next(nullptr),
_prev(nullptr)
{}
};这里需要给默认构造函数，插入数据的时候要申请节点，节点要初始化，没给值就用缺省参数，即内置类型会是0、空指针、0.0一类的，自定义类型会调用它们自己的默认构造函数；
二、迭代器结构
//list迭代器
template<class T,class Ref,class Ptr>//用于接收不同类型的参数，创造一个模板多个使用的效果
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
//初始化
list_iterator(Node* node)
:_node(node)
{}
//解引用迭代器获取数据
Ref operator*()const
{
return _node->_data;
}
//返回数据地址，一般用于数据是自定义类型的，使用这个可以访问数据内部的成员变量
Ptr operator->()const
{
return &(_node->_data);
}
//前置
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//后置
Self& operator++(int)
{
Self tmp(*this);//浅拷贝也可
_node = _node->_next;
return tmp;
}
Self& operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
//判等
bool operator==(const Self& lt)const
{
return _node == lt._node;
}
bool operator!=(const Self& lt)const
{
return _node != lt._node;
}
};组成list的基本结构是节点，不连续，要通过重载运算符的方式来使用迭代器；构造时要传一个节点指针，表示这个迭代器指向的节点是哪个；
模板参数多了Ref和Ptr，用于作为返回值类型，这样写原因：要实现两个类模板，这两个类模板中很多内容都是一样的，只是部分函数的返回值不一样；而Ref和Ptr可以接收不同的类型，将Ref和Ptr作为返回值，那么就可以将这两个类模板实现为一个了。
三、list结构
list的成员变量就是一个哨兵位；
迭代器和链表节点的类都设计成struct是因为要在list里面使用它们的成员变量；
private:
typedef list_node<T> Node;
Node* _head;
size_t _size;这是类中私有变量的内容，双向链表的实现需要一个哨兵位（list源码中的实现也是如此），而_size单纯是为了计数方便而设置的。
public：
中的内容就是list的一些接口：
1、迭代器模板参数传参的变化
//用不同的参数去调用相同的模板
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;这个是literator中的解引用调用时有两种，非const和const，而迭代器的类模板就的模板参数就可以接收不同类型的，在list的类模板中传两份过去，在使用时就可以根据需要去调用const或者非const的；
2、初始化
默构造认
list()
{
empty_init();
}
void empty_init(const T& val=T())//若是空链表先要给一个哨兵位并且初始化
{
_head = new Node(val);
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}首先要有节点，那么当链表中没有节点时，就要先给哨兵位，并且让哨兵位的前后指针都指向自己，完成双向的实现；
拷贝构造：
list(list<T>& lt)//拷贝构造
{
empty_init();
for (auto& it : lt)
{
push_back(it);
}
}是空链表就要先给哨兵位，再利用迭代器遍历要被拷贝的链表，范围for自动解引用，那么每次的it都只是要被拷贝的链表lt中的每个节点的值，这样就实现了拷贝构造（每个节点的值都一样）；
赋值重载：
list<T>& operator=(list<T> tmp)//赋值重载
{
swap(tmp);
return *this;
}
void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
std::swap(_size, tmp._size);
}这里使用传统写法，将调用赋值重载时等式右边的链表拷贝一份存在tmp中，那么tmp就是被赋值的链表的一份临时拷贝，这是将tmp和调用赋值重载时等式左边的链表进行交换，这里的交换调用库中的swap，将tmp和赋值对象的成员变量进行交换，那么赋值对象就是tmp了；
n个val去初始化：
//n个 val 构造
list(int n, const T& val = T())
{
empty_init();
for (int i = 0; i < n; i++)
{
push_back(val);
}
}和拷贝构造类似；
一段迭代器构造：
//一段迭代器构造
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
first++;
}
}迭代器所指的容器是随机的，但是数据要是相同类型，其他和拷贝构造类似；
初始化列表去初始化：
list(initializer_list<T> lt)//不能加引用&
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}初始化列表是数组转换的，这里可以把lt就当成数组看；
//initializer_list<int> l = { 1,2,3,4,5 };
list<int> l1 = {1,2,3,4,5};
list<int> l2 = { 6,7,8,9,10 };但是不能加引用，initializer_list和数组实际上不一样，底层是转换过的；
析构：
//析构
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}首先把节点都删了，这里的clear有一个技巧，就是erase，erase是删除所传迭代器指向的节点，并且删除完之后erase会返回这个所传迭代器的下一个节点的迭代器，那么每次删完it后it就会更新为下一个，那么最后就会删完；
删除玩之后要删除哨兵位。
3、迭代器接口
//迭代器
iterator begin()
{
return _head->_next;//隐式类型转换
}
iterator end()
{
return _head;
}
const_iterator cbegin()const
{
return _head->_next;
}
const_iterator cend()const
{
return _head;
}这里的const_iterator的模板参数就是前面后两个参数带有const的那个。
4、容量
// 容量
size_t size()const
{
return _size;
}
bool empty()const
{
return _size == 0;
}5、修改
//修改
iterator insert(iterator pos,const T& val)
{
Node* newnode = new Node(val);//对于类类型的变量，new会自动调用默认构造函数
Node* prev = pos._node->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = pos._node;
pos._node->_prev = newnode;
_size++;
return pos;
}
iterator erase(iterator pos)
{
assert(pos._node != _head);//确保链表里面有节点
Node* next = pos._node->_next;
Node* prev = pos._node->_prev;
prev->_next = next;
next->_prev = prev;
delete pos._node;
_size--;
return next;//返回下一个节点的迭代器，这个位置的节点被释放，返回也不能使用
}
void push_back(const T& val)
{
insert(end(), val);
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_back()
{
assert(_head->_next != _head);
erase(--end());
}
void pop_front()
{
assert(_head->_next != _head);
erase(begin());
}
insert每次插入完之后要返回传过来的那个节点的迭代器，后面的都进行复用insert和erase。
6、元素获取
//元素获取
T& front()
{
return _head->_next->_data;
}
const T& front()const
{
return _head->_next->_data;
}
T& back()
{
return _head->_prev->_data;
}
const T& back()const
{
return _head->_prev->_data;
}原文地址：https://blog.csdn.net/zc331/article/details/142668835
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！