目录
1. list的成员变量
2. list的成员函数
2.1 list的迭代器
2.2 list的初始化与销毁
2.2.1 构造函数与拷贝构造
2.2.2 赋值重载与析构函数
2.3 list的容量操作
2.3.1 size()与empty()
2.3.2 clear()与resize()
2.4 list的访问操作
2.5 list的修改操作
3. 源码
💓 博客主页：C-SDN花园GGbond
⏩ 文章专栏：玩转c++
为了让我们更加深入理解list，接下来我们将模拟实现一个·简易版的list。而为了和STL库中的list以示区分，我们将使用命名空间namespaceHTD对其封装。
1. list的成员变量
list的底层其实就是我们之前在数据结构学习的双向循环链表，它由一个节点指针_head以及记录有效节点个数的_size
下面是list的成员变量以及主体架构：
namespace HTD
{template<class T>struct list_node//节点{list_node<T>* _prev;list_node<T>* _next;T _data;list_node(const T& x = T()):_prev(nullptr),_next(nullptr),_data(x){;}};template<class T>class list{public:typedef _list_node<T> Node;//...成员函数private:Node* _head;size_t _size;};
}
2. list的成员函数
在知道list的成员变量之后，接下来我们将探究list的成员函数，而常见成员函数的用法我们早在之前就已经介绍过了 ，下面我们将来具体实现一下：
2.1 list的迭代器
首先我们来模拟实现一下迭代器iterator，而在list中迭代器iterator与vector，string中的迭代器都不同，因为list每个节点在物理空间都不连续，所以我们不可能直接使用原生指针，而是要对原生指针进行封装形成一个list_iterator类。然后再这个类中进行运算符重载++，--，*，->，==，!=等操作符。
而我们知道迭代器又分为iterator与const_iterator两种，常规情况下我们这两个类都要实现。但他们功能就显得过于冗余了，所以我们可以采用增加模版参数的方法简化。第一个模版参数T代表节点类型，第二个模版参数T&引用，第三个模版参数T*指针类型。 (因为在实现iterator中只有实现*，->时普通迭代器和const迭代器返回值不同，普通迭代器返回T&和T*const迭代器返回const T&和const T*)
template<class T,class Ref,class Ptr >//Ref为T& Ptr为T*
struct list_iterator
{typedef list_iterator< T,Ref,Ptr> Self;typedef list_node<T> Node;Node* _node;list_iterator(Node* node)//list中begin 和end要用:_node(node)//注意没有分号{}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)//后置--{Self tmp(*this);_node = _node->_prev;return tmp;}Ref operator*() {return _node->_data;}Ptr operator->()//省略一个-> 用于T像结构体类型{return &(_node->_data);}bool operator==(const Self& it){return _node == it._node;}bool operator!= (const Self & it){return _node != it._node;}
};为了像STL中一样我们在list类中对不同迭代器类型进行typedef简化。
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator< T, const T&, const T*> const_iterator;
接下来我们来实现begin()与end()，其中begin()指向的是列表的起始位置即第一个有效节点，而end()指向有效长度最后的下一位即头节点的位置，这些我们直接通过相应节点构造迭代器即可。
iterator begin()
{return iterator(_head->_next);
}
iterator end()
{return iterator(_head);
}
实现完普通迭代器之后，我们可以顺便重载一个const_iterator的版本。
const_iterator begin()const
{return const_iterator(_head->_next);
}
const_iterator end()const
{return const_iterator(_head);
}
2.2 list的初始化与销毁
2.2.1 构造函数与拷贝构造
void empty_init()//拷贝构造调用push_back要有头节点
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}
list()
{empty_init();这里我们用empty_init()是因为在实现后面push_back()时要有根节点单独使用 empty_init()方便在push_back()中调用生成根节点
接下来我们来实现迭代器初始化，而因为我们可以通过其他容器的迭代器对其初始化，所以要通过模版来实现。
template<class Iterator>
list(Iterator first, Iterator last)
{empty_initialize();while (first != last){push_back(*first);++first;}
}
最后我们来实现n个val初始化，这个构造我们可以直接复用resize()函数。
list(size_t n, const T& val = T())
{empty_initialize();resize(n, val);
}
list(int n, const T& val = T())
{empty_initialize();resize(n, val);
}
至于为什么要同时重载int与size_t两种不同类型，那是为了防止在传两个int类型的参数时被编译器交给模版InputIterator识别，然后报错。
拷贝构造也十分简单，直接拷贝就行。
拷贝构造也十分简单，直接拷贝就行。
list(const list<T>& lt)//拷贝构造lt2(lt1)lt2不能空节点
{empty_init();for (auto& e : lt){push_back(e);}
}2.2.2 赋值重载与析构函数
list<T>& operator=(list<T>& lt)
{if(this != <){swap(lt);}return *this;
}~list()
{clear();//先清空其他节点delete _head;//释放头节点_head = nullptr;
}
2.3 list的容量操作
2.3.1 size()与empty()
首先size()直接返回有效元素的个数，empty()判断有效元素个数是否为0。
size_t size()const
{return _size;
}
bool empty()const
{return _size == 0;
}
2.3.2 clear()与resize()
首先clear()要清理掉除头节点外的所有节点，我们可以直接复用earse删除即可。
void clear()
{iterator it = begin();while (it != end()){it = erase(it);}
}
当使用 resize(n) 时，如果 n 大于当前列表的大小，那么会在列表末尾添加足够数量的默认值元素，使列表大小达到 n 。如果 n 小于当前列表的大小，那么会从列表末尾删除一些元素，使列表大小变为 n 。
void resize(size_t n, const T& val = T())
{if (n < _size){while (_size != n){pop_back();//尾删}}else{while (_size != n){push_back(val);//尾插}}
}
2.4 list的访问操作
因为列表并不支持重载operator[]，我们只能实现front()与back()函数。可读可写与可读不可写。并且使用引用返回，减少不必要的拷贝。
// 可读可写
T& front()
{return *(begin());
}
T& back()
{return *(--end());
}
// 可读不可写
const T& front()const
{return *(begin());
}
const T& back()const
{return *(--end());
}
2.5 list的修改操作
2.5.1 常见的修改操作
首先我们将实现两个常用的修改函数：push_back()与pop_back()。这两个函数也都可以复用insert()与·earse()
void push_back(const T& x)
{insert(end(), x);
}
void pop_back()
{erase(--end());
}
然后我们同理可以实现push_front()与pop_front()。
void push_front(const T&x)
{insert(begin(), x);
}
void pop_front()
{erase(begin());
}
随后我们来实现数组的交换swap()函数，我们知道list的交换其实就是指针_head，与有效个数_size的交换
void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}
3. 源码
#pragma once
#include<iostream>
using namespace std;
#include<assert.h>
namespace HTD
{template<class T>struct list_node//使用struct可以让list中使用prev和next{T _data;list_node<T>* _prev;list_node<T>* _next;list_node(const T& x = T())//list中insert中要new Node(x);:_prev(nullptr), _next(nullptr), _data(x){}};template<class T,class Ref,class Ptr >//Ref为T& Ptr为T*struct list_iterator{typedef list_iterator< T,Ref,Ptr> Self;typedef list_node<T> Node;Node* _node;list_iterator(Node* node)//list中begin 和end要用:_node(node)//注意没有分号{}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){Self tmp(*this);_node = _node->_prev;return tmp;}Ref operator*() {return _node->_data;}Ptr operator->()//省略一个-> 用于T像结构体类型{return &(_node->_data);}bool operator==(const Self& it){return _node == it._node;}bool operator!= (const Self & it){return _node != it._node;}};template<class T>class list{public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;void empty_init()//拷贝构造调用push_back要有头节点{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}list(const list<T>& lt)//拷贝构造lt2(lt1)lt2不能空节点{empty_init();for (auto& e : lt){push_back(e);}}list<T>& operator=(list<T>& lt){if(this != <){swap(lt);}return *this;}void swap(list<T> lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}void clear()//不释放根节点{iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}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 = tail;_size++;*/insert(end(), x);}void pop_back(){erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}iterator begin(){return _head->_next;}const_iterator begin()const{return _head->_next;}iterator end(){return _head;}const_iterator end()const{return _head;}size_t size()const{return _size;}list(initializer_list<T> lt){empty_init();for (auto& e : lt){push_back(e);}}private:typedef list_node<T> Node;Node* _head;size_t _size;};
}
