目录

一、list介绍

二、list的使用 

1、list的构造

2、list capacity

3、list element access

4、list iterator

5、list modifiers

5.1、insert

6、list Operations

6.1、sort

7、list的迭代器失效

三、list模拟实现

1、push_back

2、iterator

3、const iterator

4、Ptr

5、insert 及其复用

6、erase 及其复用

7、clear

8、构造函数

8.1、默认构造

8.2、迭代器构造

9、拷贝构造函数

10、析构函数

11、operator=

---

一、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的使用 

1、list的构造

2、list capacity

3、list element access

4、list iterator

 此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

注意：

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

5、list modifiers

5.1、insert

使用方法如下：

6、list Operations

6.1、sort

list无法使用算法库里的 sort 函数，因为算法库里的 sort 函数底层实现如下图所示：

 这里使用了减法运算，而list各个节点的地址都是不连续的，于是就发生了错误。除此之外，算法库里的 sort 函数底层使用快排实现，而快排有一个重要的组成部分：三数取中，也不适用于list。

文档里关于 sort 函数的说明，也暗示使用算法库里的 sort 函数时要传随机迭代器：

---

 list中的 sort 用法如下：

 功能没有任何问题，但是list的 sort 函数我们很少使用，因为它的效率非常的低。

我们使用如下代码进行证明：

 可以看到，把相同的数据先拷贝到 vector 中排序，排好了之后再拷贝回来，都要比直接使用 list 排序要快。

7、list的迭代器失效

 前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

三、list模拟实现

我们先来搭一个list的基本框架：

namespace bin
{
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& x = T())
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
 
template<class T>
class list
{
typedef list_node<T> node;
public:
list()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
private:
node* _head;
};
}

 需要注意：在 list 类中定义私有成员变量时，一定要注意成员变量类型为类名 + 模板参数。

1、push_back

void push_back(const T& x)
{
node* tail = _head->_prev;
node* new_node = new node(x);
 
tail->_next = new_node;
new_node->_prev = tail;
new_node->_next = _head;
_head->_prev = new_node;
}

具体底层逻辑可以参照文章《双向链表》 。

2、iterator

 list的底层物理空间是不连续的，所以模拟实现迭代器时，就不能直接让指针 "++" 或 "--" 了，而应该实现迭代器 "++" 或 "--" 的重载：

template<class T>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T> self;
node* _node;
 
__list_iterator(node* n)
:_node(n)
{}
 
T& operator*()
{
return _node->_data;
}
 
self& operator++()
{
_node = _node->_next;
return *this;
}
 
bool operator!=(const self& s)
{
return _node != s._node;
}
};

 因为我们模拟实现的list类中的迭代器是使用原生指针实现的，且原生指针的类型为 _node* ，没办法直接实现，所以又定义了一个 __list_iterator 类进行封装。

 实验运行结果正确：

 红框框起的部分调用了一次拷贝构造，由于我们没有自己实现拷贝构造函数，所以这里是一次浅拷贝，而我们想要的就是浅拷贝。

 这里浅拷贝之所以没有报错，是因为我们封装的迭代器类中没有实现析构函数，因为迭代器仅仅是使用list对象节点，而不是拥有list对象节点，它没有权利释放list的对象。

 我们再来完善一下迭代器的其他功能：

template<class T>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T> self;
node* _node;
 
__list_iterator(node* n)
:_node(n)
{}
 
T& operator*()
{
return _node->_data;
}
 
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;
}
 
bool operator!=(const self& s)
{
return _node != s._node;
}
};

3、const iterator

先来看一下错误的写法：

 直接在list类中定义 const 类型的成员函数。这种写法的错误之处在于，这些 const 类型成员函数所针对的是list类中的成员变量 _head ，虽然 _head 被 const 限制无法更改，但是 _head 所指向的 _data 仍然可以更改，即数据仍然可以被更改，不符合我们的预期。

 我们较为容易想到的写法是直接再另外定义一个类，在这个新类中封装 const 类型的迭代器：

 虽然这种写法可以实现功能且完全满足需求，但是代码太过于冗余，接下来我们来学习一种新的写法：

在迭代器模板中多增加了一个模板参数 Ref ，用于满足不同的调用需求。

4、Ptr

观察如下代码：

 编译器报错，因为我们没有为自定义类型 AA 实现流插入重载，所以需要写成这种形式：

 但是我们在写 C++ 代码时，一般没有写成这种形式的习惯，大多数都是通过 "->" 来实现解引用操作的，所以我们可以改变写法：

 这种写法乍一看非常难以理解，这时因为为了增强可读性的缘故，在这里少写了一个 "->" ：

 大家看一下完整版的写法就一定能够理解：

 同理，为了满足不同的调用需求，应该为list类重载一个 const 类型的成员函数，为了不造成代码冗余，同样只需要为list类模板增加一个模板参数就可以了：

5、insert 及其复用

具体实现如下： 

 list的 insert 不会导致迭代器失效。

可以使用 insert 函数的复用来实现 push_back 与 push_front ：

6、erase 及其复用

具体实现如下：

  list的 erase 会导致迭代器失效。

为了在使用 erase 函数后仍然可以找到该节点的下一个节点，我们使用返回值来返回需要的信息：

 可以使用 erase 函数的复用来实现 pop_back 与 pop_front ：

7、clear

具体实现方法如下：

 也可以使用下面这种写法：

8、构造函数

8.1、默认构造

void empty_init()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
 
list()
{
empty_init();
}

8.2、迭代器构造

void empty_init()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
 
template <class Iterator>
list(Iterator first, Iterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}

 扩展内容：

 const 类型的对象是无法调用 empty_init() 函数的，因为这属于权限放大。那么为什么我们写如下 const 类型对象的实例化不会报错呢？

 这是因为该 const 对象在定义的时候并没有 const 属性，在该对象定义完成后，才被赋予了 const 属性，否则就没有办法对对象进行初始化操作了。

9、拷贝构造函数

传统写法如下：

void empty_init()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
 
list(const list<T>& lt)
{
empty_init();
for ( auto e : lt)
{
push_back(e);
}
}

这里再提供一份现代写法：

void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
}
 
list(const list<T>& lt)
{
empty_init();
 
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}

10、析构函数

实现代码如下：

~list()
{
clear();
delete _head;
_head = nullptr;
}

11、operator=

实现代码如下：

void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
}
 
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}

注意：这里的传参没有使用传引用传参，而是采用了传值传参。这是因为我们本来就期望在传参时发生一次拷贝构造，并把拷贝构造出的临时变量与 this 进行交换，这样不会影响到赋值运算符重载的右值本身。

---

关于list的使用和模拟实现的相关内容就讲到这里，欢迎同学们多多支持，如果有不对的地方欢迎大佬指正，谢谢！