一、list 的介绍
-
list是可以在常数范围内（即O(1)时间复杂度）在任意位置进行插入和删除的序列式容器，并且该容器 可以前后双向迭代。 -
list的底层是 双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。 -
list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能向后迭代，所以更简单高效。 -
与其他的序列式容器相比（
array，vector，deque），list通常在任意位置进行插入、移除元素的执行效率更好。 -
与其他序列式容器相比，
list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置（比如头部或者尾部）迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息。（对于存储类型较小元素的大list来说这可能是一个重要的因素）
二、list 的使用
① 构造函数
| 构造函数constructor | 接口说明 |
|---|---|
| list() | 构造空的 list |
| list (size_type n, const value_type& val = value_type()) | 构造的 list 中包含 n 个值为 val 的元素 |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用 [first, last) 区间中的元素构造 list |
// constructing lists
#include <iostream>
#include <list>
int main ()
{
std::list<int> l1; // 构造空的l1
std::list<int> l2 (4,100); // l2中放4个值为100的元素
std::list<int> l3 (l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3
std::list<int> l4 (l3); // 用l3拷贝构造l4
// 以数组为迭代器区间构造l5
int array[] = {16,2,77,29};
std::list<int> l5 (array, array + sizeof(array) / sizeof(int) );
// 用迭代器方式打印l5中的元素
for(std::list<int>::iterator it = l5.begin(); it != l5.end(); it++)
std::cout << *it << " ";
std::cout<<endl;
// C++11范围for的方式遍历
for(auto& e : l5)
std::cout<< e << " ";
std::cout<<endl;
return 0;
}② 迭代器使用
list 的迭代器是将原生指针进行封装后的自定义类型，因为与 vector 和 string 等在物理结上是连续的，所以可以直接将原生指针作为迭代器，而 list 不行，因为 list 的存储方式是链式结构，是分散的，所以不能直接对原生指针进行 ++ 等操作，所以得对 list 的指针进行封装，下面模拟实现的时候会具体讲。
| 函数声明 | 接口说明 |
|---|---|
| begin() && end() | 返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器 |
| rbegin() && rend() | 返回第一个元素的 reverse_iterator, 即 end 位置，返回最后一个元素下一个位置的 reverse_iterator, 即 begin 位置 |
注意事项：
-
begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动 -
rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
// list迭代器的使用
// 注意：遍历链表只能用迭代器和范围for，因为list不支持[]重载
void PrintList(const list<int>& l)
{
// 注意这里调用的是list的 begin() const，返回list的const_iterator对象
for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
{
cout << *it << " ";
// *it = 10; 编译不通过
}
cout << endl;
}
void TestList2()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
// 使用正向迭代器正向list中的元素
// list<int>::iterator it = l.begin(); // C++98中语法
auto it = l.begin(); // C++11之后推荐写法
while (it != l.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 使用反向迭代器逆向打印list中的元素
// list<int>::reverse_iterator rit = l.rbegin();
auto rit = l.rbegin();
while (rit != l.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
}③ 容量接口
| 函数声明 | 接口说明 |
|---|---|
| empty() | 检测 list 是否为空，是返回 true，否则返回 false |
| size() | 返回 list 中的有效个数 |
④ 元素访问接口
| 函数声明 | 接口说明 |
|---|---|
| front() | 返回 list 的第一个节点中值的引用 |
| back() | 返回 list 的最后一个节点中值的引用 |
⑤ 元素操作接口
| 函数声明 | 接口说明 |
|---|---|
| push_front() | 在 list 首元素前插入值为 val 的元素 |
| pop_front() | 删除 list 中的第一个元素 |
| push_back() | 在 list 尾部插入值为 val 的元素 |
| pop_back() | 删除 list 中的最后一个元素 |
| insert() | 在 list position 位置前插入值为 val 的元素 （迭代器不会失效） （一般配合算法库中的find()一起使用） |
| erase() | 删除 list position 处位置的元素 （迭代器会失效） |
| swap() | 交换两个 list 中的元素 |
| clear() | 清空 list 中的有效元素 （不清理头节点） |
⑥ 链表操作接口
| 函数声明 | 接口说明 |
|---|---|
| splice() | 将 list1 中的元素转移到 list2中 （不是拷贝，而是搬移） |
| remove() | 将 list 中所有 val 节点删掉 |
| unique() | 去掉 list 中的重复的元素 （需要先排序，配合 list 类自己的sort函数一起使用） |
| merge() | 在相同类型且分别有序的情况下，将 list2 中的元素都搬移到 list1 中，且按大小进行排序 （list2变成空的） |
| sort() | 排序 list 中的元素（效率低，不推荐） |
| reverse() | 逆置 list 中的元素 |
这些操作用的比较少，而且不太推荐使用 sort 等函数，因为效率比较低。
list 中还有一些操作，需要用到时大家可参阅 list 的文档说明。
补充问题
为什么 list 类中要重新实现 sort 函数，而不是使用算法库里面的？
理论上来说，算法库中实现的函数模板是通用的，但是因为算法库里面的一些函数是需要接受不同类型的迭代器的，而 list 类的迭代器属于双向迭代器，算法库里面 sort 函数底层使用的是快速排序，而快速排序要求容器迭代器接收的是随机迭代器，迭代器类型不符合，所以使用不了库里面的 sort 函数以及其他一些函数。
Ⅱ. list 的迭代器失效问题
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除后出现野指针问题。
因为 list 的底层结构为带头结点的双向循环链表，因此在 list 中进行插入不会导致 list 的迭代器失效的， 只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
void TestListIterator1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值才行！
l.erase(it);
++it;
}
}
// 改正后的代码：
void TestListIterator()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
it = l.erase(it);
}
}Ⅲ. list 的模拟实现
一、基本框架的实现
① 构造节点
以 stl 3.0 版本为例，我们来模拟它的阉割版哈哈~~
首先，为了做到通用，显然在 C++ 中就得借助 模板 来实现通用！所以我们先将节点构造出来：
namespace liren
{
template <class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _val;
};
} 思考：为什么这里 list_node 要加 <T> ❓❓❓
解答： 因为类模板不支持自动推导类型。结构体模板或类模板在定义时可以不加 <T>，但使用时必须加 <T>。
接下来我们对节点附上构造函数，因为 C++ 中，每次开辟一个对象就会调用其构造函数进行初始化，这就很方便！
- 将数据给给
_val - 将
_next和_prev都置成空
这些任务我们可以写到 struct ListNode 的构造函数中，我们还可以设计成全缺省，给一个匿名对象 T() 。如此一来，如果没有指定初识值，它就会按模板类型去给对应的初始值了。
namespace liren
{
template <class T>
struct list_node
{
list_node(const T& val = T())
:_val(val),
_next(nullptr),
_prev(nullptr)
{}
list_node<T>* _next;
list_node<T>* _prev;
T _val;
};
}② 构造 list 框架
设计好节点之后，我们就可以开始实现 list 类啦！
- 考虑到我们写的节点
list_node<T>名字比较长，所以我们用typedef将其别名设为Node* - 又考虑到可能后面的拷贝构造以及赋值重载也需要构造头节点，所以我们将构造头节点独立为一个函数
CreateHead()。
因为是带头（哨兵位）双向循环链表，我们先要带个头儿。
我们先要把头结点 _head 给设计出来，而 _prev 和 _next 是默认指向头结点的。
namespace liren
{
template <class T>
class list
{
public:
typedef list_node<T> Node; // 重命名为Node
public:
list()
{
CreateHead(); // 调用函数去构造头节点
}
private:
Node* _head; // 头结点指针
};
}// 初始化头结点
void CreateHead()
{
_head = new Node;
_head->_next = _head; // 让前后指针都指向头节点本身
_head->_prev = _head;
}二、list 迭代器的实现
① 为什么需要构造迭代器❓
可以明显发现，list 和之前的 vector/string 不同，list 是链式结构，在物理空间上是不连续的，所以直接对 list 的原生指针进行操作，比如**++**操作，是没办法移到下一个 list 元素的位置的（除非运气非常好，刚刚好下个节点位置就在上一个节点位置的下个地址处）。
而对于 vector/string 的迭代器，都是原生指针，实现起来非常简单， 因为他们在物理空间上是连续的，也支持随机访问。
💡 **问题：**既然
list的原生指针无法满足基本的操作，那我们应该如何做❓❓❓🌡 解答： 得益于
C++有 运算符重载 的功能，我们可以用一个类型去对结点的指针进行封装！
我们可以将 list 的原生指针进行封装，变成一个类，再对这个类进行运算符的重载，就能实现意义上的迭代器了！
② 迭代器的构造
首先，因为 operator++ 以及 operator-- 等函数操作都是返回 list_iterator 类型的，所以可以先将迭代器重命名为 Self，减少长度，以及后面我们需要传多个参数的模板时候，这个重命名就可以方便了很多事情，不需要我们去修改很多地方！
只需要用一个结点的指针就可以构造了：
template <class T>
struct list_iterator
{
typedef list_node<T> Node; // 将节点重命名为Node
typedef list_iterator<T> Self; // 将迭代器重命名为Self
/* 迭代器的构造 */
list_iterator(Node* node = nullptr) // 设置一个nullptr的缺省值
:_node(node)
{}
Node* _node;
};③ 迭代器的拷贝构造、赋值重载、析构
💡 思考： 迭代器需要拷贝构造这些函数❓❓❓
💭 解答： 不用！
list迭代器的拷贝构造和赋值重载不需要自己实现，默认生成的即可！
为什么呢❓❓❓
对于拷贝构造和赋值重载：
- 我们使用迭代器去访问和修改
list或者其他容器的元素，本质就是要得到该处元素的指针，那么我们就没必要去做深拷贝，直接做浅拷贝，将该处的地址浅拷贝给迭代器构造即可。即当前迭代器赋值给另一个迭代器是不需要深拷贝的，浅拷贝就可以。
举个例子：
对于析构函数：
- 迭代器里面虽然有一个节点的指针，但是该节点并不是由迭代器进行管理的，而是由
list进行管理的，list类的生命周期结束后会调用析构函数对节点进行释放的，而迭代器只是负责对该节点进行一些操作，并不需要对节点进行释放，也不允许对节点进行释放。 - 所以对于析构函数，也是使用编译器默认生成的即可，无需去释放节点。
④ operator++ 以及 operator--
对于operator++：
++操作分为 前置++ 和 后置++，我们先实现一下前置++：
🐛 因为 前置++ 返回的是本体（也就是
this指针所指的空间），所以可以传引用返回，提高效率！
/* ++it */
Self& operator++()
{
_node = _node->_next; // 让 _node指向下一个结点
return *this; // 返回++后的值
}那 后置++ 与 前置++ 有什么区别呢❓❓❓
- 后置++ 返回的不是本体，而是一个临时的迭代器对象，所以不能传引用返回！
- 为了区分前置与后置，需要在后置++的参数列表中设置一个占位
int
/* it++ */
Self operator++(int)
{
Self tmp(*this); //拷贝构造一个tmp存储原来的值
_node = _node->_next;
return tmp; //返回一个临时对象
}对于operator--：
--操作分为 前置-- 和 后置--，其余操作与++是一致的，只不过我们是返回 _prev 节点：
/* --it */
Self& operator--()
{
_node = _node->prev;
return *this;
}/* it-- */
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}⑤ operator!= 和 operator==
这两个函数的实现很简单吧！只需要比较两个节点的地址是否相同即可！
bool operator!=(const Self& s) //使用传引用提高效率
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}⑥ operator*
operator* 的功能是 解引用，也就是获得该处的数据。
并且 operator* 还要能支持修改的操作，所以我们得对它的返回类型设为传引用返回&
T& operator*()
{
return _node->_val; //返回结点的数据
}7. operator->
operator-> 的功能是 返回该处数据的地址。
💡 **问题：**为什么要重载 -> 这个操作符呢❓❓❓
🐛 解答： 如果我们要拿到的数据不是一个内置类型的数据，而是一个类的数据，那么情况就不太一样，以下面代码为例：
//比如是一个日期类，假设我们没有实现其流插入，我们自己访问
struct Date
{
int _year;
int _month;
int _day;
Date(int year = 1, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
};
void test_list3()
{
list<Date> L;
L.push_back(Date(2022, 5, 1));
L.push_back(Date(2022, 5, 2));
L.push_back(Date(2022, 5, 3));
list<Date>::iterator it = L.begin();
while (it != L.end()) {
// cout << *it << " "; 假设我们没有实现流插入，我们自己访问
cout << (*it)._year << "/" << (*it)._month << "/" << (*it)._day << endl;
it++;
}
cout << endl;
} 我们可以发现，这种解引用的操作，我们不太习惯，我们更偏向于下面这种写法：
cout << it->_year << "/" << it->_month << "/" << it->_day << endl;所以我们有必要重载一下 -> 的函数，让其可以指向数据。
☕ 代码：其实现方式似乎有些出乎意料，思考下原理是什么❓❓❓
T* operator->()
{
return &(_node->val); //返回_node->val的地址
}
🍡 总结： 所有类型重载 operator-> 时都会省略一个箭头。（后期讲智能指针还会再提）
⑧ 构造const迭代器
我们已经把普通对象的迭代器的基本功能实现了，那还剩下我们的 const 对象的迭代器。
与普通对象的迭代器不同，const 对象迭代器只能读不能写，而通常迭代器进行修改和读取都是通过 operator* 和 operator-> 来实现，所以我们只需要实现这两个函数的 const 版本即可。
//operator*的const版本
T& operator*()
{
return _node->_val; //返回结点的数据
}
const T& operator*() const
{
return _node->_val; //返回结点的数据
}
//operator->的const版本
T* operator->()
{
return &(_node->val); //返回_node->val的地址
}
const T* operator->() const
{
return &(_node->val); //返回_node->val的地址
} 表面上我们已经构造了他们的 const 版本，那我们来试一下 const 版本的迭代器能不能修改数值。
在测试之前，我们也要讲 list 中的成员函数 begin() 重载一个 const 版本：
iterator begin() const
{
return iterator(_head->_next);
}
看得出来，虽然 l.begin() 是 const 对象，但是赋给 it 后， it 仍然不是 const 对象，所以就算在 list_iterator 中重载了**const** 版本的 operator*，it 也不会去调用这个版本，因为它不是 const 的。
所以直接在 list_iterator 里面重载一个 const 类型的 operator* 解决不了问题，我们得重新实现一个 const_list_iterator 出来。但是这是比较传统的方法，因为在迭代器里面，只有 operator* 和 operator-> 需要有 const 版本，而其他函数是不需要的，如果重新实现一个，那么重复的函数就太多了，这就很冗余了！所以我们不采用这种方法，不过我们可以实现一下看看是怎么样的，代码如下：
/* 定义const迭代器 */
template<class T>
struct const_list_iterator {
typedef list_node<T> Node;
typedef const_list_iterator<T> Self;
Node* _node;
const_list_iterator(Node* x)
: _node(x)
{}
const T& operator*() const
{
return _node->_val; // 返回结点的数据
}
const T* operator->() const
{
return &(_node->val);
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)
{
_const_list_iterator<T> tmp(*this);
_node = _node->_next;
return tmp;
}
//....只展示部分函数，其他都是一样的
} 这里我们把 list_iterator 都修改成 const_list_iterator，
并且对于解引用 operator* 和 operator-> 的重载，我们将其改成 const 返回，这样就只能读不能写了。
💬 **代码：**然后我们这里再在 list 中 typedef 一下 const 迭代器
template<class T>
class list {
typedef list_node<T> Node; // 重命名为Node
public:
/* 迭代器 */
typedef list_iterator<T> iterator;
typedef const_list_iterator<T> const_iterator; // 重命名const迭代器
// 👇 const 迭代器的 begin 和 end
const_iterator begin() const {
return const_iterator(_pHead->_next); // 调用 const_list_iterator<T>
}
const_iterator end() const {
return const_iterator(_pHead);
}
iterator begin() {
return iterator(_pHead->_next); // 调用 list_iterator<T>
}
iterator end() {
return iterator(_pHead);
}
...
} 虽然这样子实现 const 版本是可以的，但是确实是冗余部分太多了。
我们去 stl3.0 源码看一下，发现了一个奇妙的方法：
🐛 妙不妙！
这个用法的意思就是在定义 template 模板时候增加两个参数：一个是 Ref（reference引用的意思），一个是 Ptr（pointer）。
这样的话，我们 operator* 的返回值 我们不要用 **T&**了，我们改成 Ref；而 operator-> 的返回值我们改成 Ptr。
template <class T, class Ref, class Ptr>
struct list_iterator
{
typedef _list_node<T> Node; //将节点重命名为Node
typedef list_iterator<T, Ref, Ptr> Self; //将迭代器重命名为Self
/* 迭代器的构造 */
list_iterator(Node* node = nullptr) //设置一个nullptr的缺省值
:_node(node)
{}
Ref operator*()
{
return _node->_val; //返回结点的数据
}
Ptr operator->()
{
return &(_node->val); //返回_node->val的地址
}
//......其他函数还是一样不变，前提是将迭代器重命名为了Self
} 💬 **代码：**之后我们就可以在 list 中 typedef 的时候就可以做到 "分流" ，传 普通版本 或 const 版本 了：
template <class T>
class list
{
public:
typedef _list_node<T> Node;
//迭代器
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
public:
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next); //注意，返回值这里构造的也是const版本的
}
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head); //注意，返回值这里构造的也是const版本的
}
//.....其他的函数暂且不看
private:
Node* _head;
};对于非const版本：
🔑 解读：这里 ls 是一个普通对象，调用的自然是普通的 begin。 begin 返回的是普通迭代器 list_iterator<T, T&, T*>，第二个模板参数是 T&，Ref 就是 T& 了。operator* 的返回值 Ref 是 T& 了，这样就做到了可读可写了。
对于const版本：
💡 解读：比如这里的 print_list 就是一个 const 对象，它调用的就是 const 的 begin。const begin 返回的是 const 迭代器 list_iterator<T, const T&, const T*>，第一个值传的都是 T，第二个值 const T& 传给 Ref。那么 operator* 的返回值 Ref 就是 const T& 了，这样就做到了可读但不可写的。
3、反向迭代器的自主实现版本
🐜 让我们看看源代码中的反向迭代器是怎么实现的！
可以明显看出，反向迭代器与正向迭代器是类似的，并且用了正向迭代器进行了封装，而库里面的反向迭代器其实更复杂，用了适配器模式的方法，这个在下面的适配版本会讲得更细。
这里我们实现一下三个模板参数版本，也就是自主实现版本的反向迭代器，具体的解析到下面适配器版本一起讲。
代码如下：
namespace liren
{
//反向迭代器的自主实现版本
template <class iterator, class Ref, class Ptr>
struct reverse_iterator
{
// Iterator是哪个容器的迭代器，reverse_iterator<Iterator>就可以适配出哪个容器的反向迭代器。复用的体现
typedef reverse_iterator<iterator, Ref, Ptr> Self; //将反向迭代器重命名为Self
reverse_iterator(iterator it)
:_it(it)
{}
Ref operator*()
{
iterator prev(_it);
return *(--prev); // 注意结构上的错位
}
Ptr operator->()
{
return &(this.operator*()); //复用上面的operator*()
}
Self& operator++() //与正向迭代器相反，反向迭代器的++其实是正向迭代器的--，反之也成立
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp = _it;
--_it;
return tmp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self tmp = _it;
++_it;
return tmp;
}
bool operator!=(const Self& s) const
{
return _it != s._it;
}
iterator _it;
};
template <class T>
class list
{
public:
typedef list_node<T> Node;
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
//记得这里第一个参数是要传iterator，而不是T，因为我们是通过iterator来包装反向迭代器的
typedef reverse_iterator<iterator, T&, T*> re_iterator;
typedef reverse_iterator<iterator, const T&, const T*> const_re_iterator;
public:
re_iterator rbegin()
{
return re_iterator(end());
}
const_re_iterator rbegin() const
{
return const_re_iterator(end());
}
re_iterator rend()
{
return re_iterator(begin());
}
const_re_iterator rend() const
{
return const_re_iterator(begin());
}
…………
private:
Node* _head;
};
}总结： Iterator 是哪个容器的迭代器，reverse_iterator<Iterator> 就可以适配出哪个容器的反向迭代器，这是复用的体现。
4、反向迭代器的适配版本
① 什么是适配器
反向迭代器其实就是对正向迭代器的一种封装 —— 适配器模式（配接器模式）
电源适配器又叫外置电源，是小型便携式电子设备及电子电器的供电电压变换设备，常见于手机、液晶显示器和笔记本电脑等小型电子产品上。
电源适配器是进行 "转换" 的，它本质上可以理解为是一个变压器。
标准家庭用电电压为 220V，我们设备用电其实并不需要这么高，而电源适配器可以使较高的交流电压降低到合适于手机电池的直流工作电压。也就是说，电源适配器是用来 "转换" 的。
一样的道理，反向迭代器和正向迭代器非常像！基于这一系列的原因，在实现反向迭代器的时，没有必要像正向迭代器这样去包装并重新实现。
🔍 区别： 反向迭代器和正向迭代器++的方向不一样（唯一区别）。
（即正向迭代器 ++ 是向后走，反向迭代器 ++ 是向前走）
💬 举个例子：
我们可以对其进行封装地 "转换" ，比如我们需要 list 的反向迭代器，我们将 list 的正向迭代器传给 iterator，来实例化 iterator。然后通过包装转换出你需要的 list 的反向迭代器：
template <class iterator>
struct Reverse_iterator
{
typedef Reverse_iterator<iterator> Self; //将反向迭代器重命名为Self
Reverse_iterator(iterator it) //构造函数，接收一个iterator类型
:_it(it)
{}
iterator _it;
}; 如果你 vector 需要反向迭代器，那就把 vector 的正向迭代器传给 iterator，它就可以通过正向迭代器转换出 vector 的反向迭代器。
也就是说，我们实现的反向迭代器并包装的这个类，不是针对某个容器而是针对所有容器的。
任何一个容器只要你实现了正向迭代器，就可以通过其适配出反向迭代器。
它的本质是一种复用，是一种适配与转换。这就是迭代器适配器!
② 反向迭代器的错位访问
在自主实现版本中，我们已经将反向迭代器主体的函数实现了，其中对于 operator*() 这个函数，会不会觉得很奇怪，为什么是返回 *--_prev，看起来有一种 “错位” 的感觉！他返回的是 _prev 的上一个位置，而不是当前位置。
所以我们有必要了解一下对于 list 的反向迭代器，它的 rbegin() 和 rend() 是指向哪个地方！
-
对于正向迭代器的
begin()和end*()位置如下：
-
而对于反向迭代器的
rbegin()和rend()位置如下：
一般情况下，如果我们没去深剖源码，会误以为 rbegin() 是在最后3的那个位置处、rend() 在头节点，其实不是的！
rbegin 和 rend 是和 end 和 begin 是相对称的形式设计的，你的 end 就是我的 rbegin，你的 begin 就是我的 rend！
但是这样子设计的话，就产生了错位的问题，我们解引用的时候会对不上想要的位置，举个例子：
//伪代码
rit = rbegin()
while(rit != rend())
*rit 这时候我们会发现，我们解引用，得到的是头节点，但是我们想要的是最后一个节点的数据啊，那这该怎么办？
💡 这个时候我们就可以在解引用函数 operator*() 里面改造一下，让其返回 *(--prev) ：
Ref operator*()
{
iterator prev = _it;
return *(--prev); //这里可以不加括号，但是为了可读性这里就加了括号
}
③ 通过内嵌类型实现反向迭代器
我们上面的自主实现版本是用了传了三个参数的模板，而 stl3.0 中其实只传了一个参数 iterator 而已，这是怎么做到的呢❓❓❓
它没有传 Ref 和 Ptr，也就意味着不能显式地去传，自己去控制（详细请阅读自主实现版本）。
比如，如果你是普通迭代器的反向迭代器，传的就是 T& 和 T* ：
如果你是 const 迭代器的反向迭代器，传的就是 const T& 和 const T* ：
我们这么做是为了更清楚地表示，降低学习的成本，而库中采用了一种更难的方式去实现，不传 Ref 和 Ptr 这两个模板参数，只用了一个模板参数。这就意味着要去取 pointer 和 reference，因为它们要做 operator* 和 operator-> 的返回值。
而这里只有迭代器 iterator，我们该怎么去取呢❓❓❓
💡 stl 中是这么做的，他在其中定义了一个内嵌类型：
把 Ptr 和 Ref 定义成了 pointer 和 reference，这样我们就可以从内嵌类型中去取这个类型了。
💬 **代码：**不传 Ptr 和 Ref 这两个模板参数去实现反向迭代器
namespace liren
{
//template <class Iterator, class Ref, class Ptr>
template <class Iterator>
class Reverse_iterator
{
typedef Reverse_iterator<iterator, Ref, Ptr> self;
typedef Iterator::Ref reference; // 取内嵌类型
typedef Iterator::Ptr pointer;
public:
reverse_iterator(Iterator it)
:_it(it)
{}
...
}
} 如果你自己试一试你就会发现一个问题：
Iterator 是一个模板参数，你要取模板参数中的内嵌类型 Ref，编译器这里就编不过去了。
如果你对模板参数取 typedef，没有任何问题。但是你要取它的内嵌类型，就有问题了：
因为编译器编译到这一块的时候，模板参数还没有实例化！
既然没有实例化，那编译器也不知道这个
iterator的类型是什么，typedef一下没什么问题。但是你用
::取iterator里面的东西，模板都还没实例化，编译器怎么知道里面到底是什么呢❓❓❓
:walking: 那我们该怎么让编译器知道呢❓❓❓
凡是要取一个模板、类模板或模板参数的内嵌类型（内部类），就可以用 typename （不能用 class 替代，虽然新版编译器允许）：
对于现阶段而言，这种写法是有缺陷的。vector、string 的迭代器怎么适配❓❓❓
这里在取内嵌类型，只有自定义类型才能在里面搞内嵌类型，内嵌类型也是类，typedef 也是内嵌类型。如果是一个原生指针呢❓❓❓
原生指针哪来的内嵌类型❓❓❓
如果仅看这一部分的实现，自然还是三个模板参数更爽，自己控制，但是这种萃取只在 list 中好用，vector 中还要改很多，非常麻烦，但是 STL 是非常复杂的，它还要考虑去兼顾全局，不是说只有迭代器和容器，像 vector、string 这样的容器的迭代器是原生指针，无法取内嵌类型。那么上面的方式就寄了。
比如上面的
typename Iterator::reference operator()中，list的迭代器传给它，要在list的迭代器中找reference能找到，而vector中的iterator类型是T*，要在T中找reference找不到。 所以还是三个模板参数好用，但是
STL的标准库中用了一个模板参数和萃取是有他的原因，它还要兼顾其他的功能等等，当我们这种自己实现用三个模板参数更好一些！
所以就有了迭代器萃取！不过由于比较复杂，我们会在后面才学到！
④ 浅谈迭代器萃取
基于上面内嵌类型的原因，STL 源码中使用了一个叫 "迭代器萃取" 的技术解决的。
原理：再套一层，去萃取迭代器中的 reference 和 pointer（迭代器管理的数据中的 T& 和 T* 或 const T* 和 constT& 等取出来）。相当于把其他容器的迭代器传给 iterator_traits，在其中再套一层，对于链表而言最终还是要取：
对于 vector、string 这样的原生指针，iterator_traits 里有使用了一个技术 —— "模板特化技术"
大概意思是当你这里是原生指针时，这里会直接自己套一层取解决。萃取的本质就是模板的特化。 对于 vector、string 这样子的原生指针，我们只需要为它的 iterator 提供一份特化的版本即可！
总结： list 用一个参数实现还行，但是 vector 和 string 这样的原生指针还是用一个参数去实现会牵扯到更复杂的迭代器萃取。就目前而言，学会实现 3 个模板参数的反向迭代器即可。
代码：
//反向迭代器的适配版本
template<class Iterator>
class Reverse_iterator
{
public:
// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的一个类型，而不是静态成员变量
// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
typedef typename Iterator::Ref Ref;
typedef typename Iterator::Ptr Ptr;
typedef Reverse_iterator<Iterator> Self;
public:
Reverse_iterator(Iterator it)
:_it(it)
{}
Ref operator*()
{
Iterator prev(_it);
return *(--prev); // 注意结构上的错位
}
Ptr operator->()
{
return &(operator*()); //复用上面的operator*()
}
Self& operator++() //与正向迭代器相反，反向迭代器的++其实是正向迭代器的--，反之也成立
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp = _it;
--_it;
return tmp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self tmp = _it;
++_it;
return tmp;
}
bool operator!=(const Self& s) const
{
return _it != s._it;
}
bool operator==(const Self& s) const
{
return _it == s._it;
}
Iterator _it;
};//正向迭代器中需要对两个参数进行重定义
template <class T, class Ref, class Ptr>
class list_iterator
{
typedef list_node<T> Node; //将节点重命名为Node
typedef list_iterator<T, Ref, Ptr> Self; //将迭代器重命名为Self
public:
// Ref 和 Ptr 类型需要重定义下，实现反向迭代器时需要用到
typedef Ref Ref;
typedef Ptr Ptr;
//…………
} （有个奇怪的现象，适配版本的反向迭代器取了 reverse_iterator 的名称后程序会报错，而改成其他的则不会，很奇怪）
💡 解答： 这是一个很细节的问题，也非常容易踩坑而不容易发现！至少我就是这样子的。。。。
若我们将反向迭代器的名称设为 reverse_iterator，且将 typedef 后的重命名也设为 reverse_iterator，会导致在设置 const 版本的反向迭代器的时候，编译器会到上一行或者前面找这个重名的 reverse_iterator，而不会去类外找我们的反向迭代器类，这样子就导致了报错，所以注意在用 typedef 重命名时候不要与下面迭代器的类名重复了！
5、list 的模拟实现
① insert函数
在 pos 位置前插入，我们通过 pos 去找到前驱 prev，之后创建新结点，再进行 "缝合" 操作，比较简单。
代码：
// 在pos位置前插入值为val的节点
void insert(iterator pos, const T& x)
{
Node* newnode = new Node(x); //开辟新节点
Node* prev = pos._node;
newnode->_prev = prev->_prev;
newnode->_next = prev;
newnode->_prev->_next = newnode;
prev->_prev = newnode;
} 有了 insert 函数，push_back 以及 push_front 就能用 insert 复用了！
代码：
//尾插
void push_back(const T& x)
{
//第一种自己实现
/*Node* newnode = new Node(x);
_head->_prev->_next = newnode;
newnode->_prev = _head->_prev;
newnode->_next = _head;
_head->_prev = newnode;*/
//第二种复用insert
insert(end(), x); //在end（pHead）前插入，即尾插
}
//头插
void push_front(const T& x)
{
insert(begin(), x); // 在begin（头结点的下一个结点）前插入，即头插
}② erase函数
删除 pos 位置结点，步骤如下：
- 找到
pos的前驱和后继。 - 释放
pos位置结点。 - 将已删除的
pos结点的前驱和后继 "缝合" 。
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
assert(pos != end()); // 防止头结点被删除
Node* cur = pos._node; // 找到pos位置的结点
Node* cur_prev = cur->_prev; // 找到pos的前驱
Node* cur_next = cur->_next; // 找到pos的后继
// 删除cur
delete cur;
// 缝合： cur_prev <-> cur(删) <-> cur_next
cur_prev->_next = cur_next;
cur_next->_prev = cur_prev;
return iterator(cur_next);
} 由于 erase 函数删掉了一个节点后，这个迭代器肯定失效了！为了让迭代器不失去作用，我们 erase 函数返回下一个节点的迭代器。
既然我们将 erase 函数写出来啦，那就可以顺便实现头删和尾删了！
/* 尾删 */
void pop_back()
{
erase(--end()); // 删除最后一个元素，即尾结点
}
/* 头删 */
void pop_front()
{
erase(begin()); // 删除头结点的下一个结点（即begin位置的结点）
}③ 访问操作函数
注意，list 不支持 [] 访问，因为物理空间不是连续的，不支持随机访问，但是可以访问 list 的头部 front 和尾部 back。
// list的元素访问操作
// 注意：List不支持operator[]
T& front()
{
return _head->_next->_val;
}
const T& front()const
{
return _head->_next->_val;
}
T& back()
{
return _head->_prev->_val;
}
const T& back()const
{
return _head->_prev->_val;
}④ 与容量有关的函数
比如 size()、empty()、resize() 等函数，并不难实现，所以直接上代码：
// size函数
size_t size() const
{
Node* cur = _head->_next;
size_t count = 0;
while (cur != _head)
{
count++;
cur = cur->_next;
}
return count;
}
// empty函数
bool empty() const
{
return _head == _head->_next;
}
// resize函数
void resize(size_t n, const T& val = T())
{
size_t sz = size();
if (n <= sz) //小于list长度
{
while (n <= sz)
{
pop_back();
sz--;
}
}
else //大于list长度
{
while (sz < n)
{
push_back(x);
sz++;
}
}
}⑤ clear函数
我们后面在实现析构和拷贝构造的时候，可能需要用到清理 list 的函数，所以我们就做了 clear 函数负责清理有效元素个数。
我们可以自己实现，但是没必要，因为可以用 erase 进行复用，但是注意，要传一个 iterator 给 erase 函数而不是传节点！
void clear()
{
iterator cur = begin(); // 注意要传迭代器，因为等会erase只接收迭代器
while (cur != end())
{
erase(cur++); // 因为erase完迭代器会失效，所以要重新赋值
}
} 这里顺便将 swap 函数也讲了，这个函数是用来交换两个 list 的指针的，也就是交换了所指的位置！
void swap(liren::list<T>& l)
{
::swap(_head, l._head); // 直接交换两处的指针即可
}6、list 的拷贝构造、赋值重载以及析构函数
① 析构函数
这里析构函数的存在就是为了将节点释放掉，防止内存泄漏。
🏗 那么我们需要一个个重新释放掉❓❓❓
💡 解答： 不需要！因为我们上面已经实现了
clear()函数，可以调用其进行释放！
~list()
{
clear(); // 先将有效元素释放掉
// 然后将头节点也释放掉，并置空
delete _head;
_head = nullptr;
} 这样子我们就把析构函数写完啦！
但是这里就出现了问题，那就是拷贝构造或者赋值的浅拷贝问题引发的析构问题：浅拷贝只是将指针拷贝过去，两个 list 指向的是同一块空间，最后释放的时候，同一块空间被析构了两次，这样子程序就报错了！
所以我们必须自己实现拷贝构造以及赋值重载！
② 拷贝构造
与 vector、string 类似，list 的拷贝构造也有传统写法与现代写法之分！
同样的，深拷贝就是重新开辟一个空间，然后将原空间的数据复制过来。
🐛 传统写法：
//传统写法的拷贝构造
list(const list<T>& l)
{
//创建新的头节点（该函数在上面实现了）
CreateHead();
for (auto e : l)
{
push_back(e);
}
} 🐛 现代写法：
//拷贝构造的现代写法
template <class Iterator>
list(Iterator first, Iterator last)
{
CreateHead();
while (first != last)
{
push_back(*first);
++first;
}
}
list(const list<T>& l)
{
CreateHead();
// 用l中的元素构造临时的temp,然后与当前对象交换
list<T> temp(l.begin(), l.end());
this->swap(temp);
}③ 赋值重载
赋值重载大体与拷贝构造一样，但是不同的是：拷贝构造是在对象定义的时候赋值，而赋值重载是在对象已经定义完后的赋值，所以可理解为赋值重载需要先将对象里面的数据清空，再进行赋值，另外也不需要重新创建头节点，因为是已经存在的。
💬 代码： 传统写法
list<T>& operator=(list<T> L)
{
if (this != &L) //判断一下是否为自己给自己赋值，若是的话则没必要赋值
{
clear();
for (auto e : L)
{
push_back(e);
}
}
return *this;
} 💬 代码： 现代写法
list<T>& operator=(list<T> l) //接收的不是引用，而只是一个值
{
this->swap(l);
return *this;
}7、完整的代码
list.h
#pragma once
#include<iostream>
#include<cassert>
using namespace std;
namespace liren
{
// List的节点类
template <class T>
struct list_node
{
list_node(const T& val = T())
:_val(val),
_next(nullptr),
_prev(nullptr)
{}
T _val;
list_node<T>* _next;
list_node<T>* _prev;
};
/*
List 的迭代器
迭代器有两种实现方式，具体应根据容器底层数据结构实现：
1. 原生态指针，比如：vector
2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：
1. 指针可以解引用，迭代器的类中必须重载operator*()
2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
至于operator--()/operator--(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是forward_list就不需要重载--
4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
*/
template <class T, class Ref, class Ptr>
class list_iterator
{
typedef list_node<T> Node; // 将节点重命名为Node
typedef list_iterator<T, Ref, Ptr> Self; // 将迭代器重命名为Self
public:
// Ref和Ptr类型需要重定义下，实现反向迭代器时取类型需要用到
typedef Ref Ref;
typedef Ptr Ptr;
public:
/* 迭代器的构造 */
list_iterator(Node* node = nullptr) // 设置一个nullptr的缺省值
:_node(node)
{}
Ref operator*()
{
return _node->_val; // 返回结点的数据
}
Ptr operator->()
{
return &(_node->val); // 返回_node->val的地址
}
/* ++it */
Self& operator++()
{
_node = _node->_next; // 让_node指向下一个结点
return *this; // 返回++后的值
}
Self operator++(int)
{
Self tmp(*this); // 拷贝构造一个tmp存储原来的值
_node = _node->_next;
return tmp; // 返回一个临时对象
}
/* --it */
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& s) const // 使用传引用提高效率
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
Node* _node;
};
//反向迭代器的自主实现版本
//template <class iterator, class Ref, class Ptr>
//struct reverse_iterator
//{
// // Iterator是哪个容器的迭代器，reverse_iterator<Iterator>就可以适配出哪个容器的反向迭代器。复用的体现
// typedef reverse_iterator<iterator, Ref, Ptr> Self; //将反向迭代器重命名为Self
// reverse_iterator(iterator it)
// :_it(it)
// {}
// Ref operator*()
// {
// iterator prev(_it);
// return *(--prev); // 注意结构上的错位
// }
// Ptr operator->()
// {
// iterator prev = _it;
// return &(operator*()); //复用上面的operator*()
// }
// Self& operator++() //与正向迭代器相反，反向迭代器的++其实是正向迭代器的--，反之也成立
// {
// --_it;
// return *this;
// }
// Self operator++(int)
// {
// Self tmp = _it;
// --_it;
// return tmp;
// }
// Self& operator--()
// {
// ++_it;
// return *this;
// }
// Self operator--(int)
// {
// Self tmp = _it;
// ++_it;
// return tmp;
// }
// bool operator!=(const Self& s) const
// {
// return _it != s._it;
// }
// iterator _it;
//};
//反向迭代器的适配版本
template<class Iterator>
class Reverse_iterator
{
public:
// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的一个类型，而不是静态成员变量
// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
// 因为静态成员变量也是按照 "类名::静态成员变量名" 的方式访问的
typedef typename Iterator::Ref Ref;
typedef typename Iterator::Ptr Ptr;
typedef Reverse_iterator<Iterator> Self;
public:
Reverse_iterator(Iterator it)
:_it(it)
{}
Ref operator*()
{
Iterator prev(_it);
return *(--prev); // 注意结构上的错位
}
Ptr operator->()
{
return &(operator*()); //复用上面的operator*()
}
Self& operator++() //与正向迭代器相反，反向迭代器的++其实是正向迭代器的--，反之也成立
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp = _it;
--_it;
return tmp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self tmp = _it;
++_it;
return tmp;
}
bool operator!=(const Self& s) const
{
return _it != s._it;
}
bool operator==(const Self& s) const
{
return _it == s._it;
}
Iterator _it;
};
template <class T>
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
//记得这里第一个参数是要传iterator，而不是T，因为我们是通过iterator来包装反向迭代器的
/*typedef reverse_iterator<iterator, T&, T*> re_iterator;
typedef reverse_iterator<iterator, const T&, const T*> const_re_iterator;*/
typedef Reverse_iterator<iterator> reverse_iterator;
typedef Reverse_iterator<const_iterator> const_reverse_iterator;
public:
list()
{
CreateHead();
}
//传统写法的拷贝构造
//list(const list<T>& l)
//{
// //创建新的头节点
// CreateHead();
// for (auto e : l)
// {
// push_back(e);
// }
//}
//拷贝构造的现代写法
template <class Iterator>
list(Iterator first, Iterator last)
{
CreateHead();
while (first != last)
{
push_back(*first);
++first;
}
}
list(const list<T>& l)
{
CreateHead();
// 用l中的元素构造临时的temp,然后与当前对象交换
list<T> temp(l.begin(), l.end());
this->swap(temp);
}
//传统写法的赋值重载
//list<T>& operator=(list<T> L)
//{
// if (this != &L) //判断一下是否为自己给自己赋值，若是的话则没必要赋值
// {
// clear();
// for (auto e : L)
// {
// push_back(e);
// }
// }
// return *this;
//}
//现代写法的赋值重载
list<T>& operator=(list<T> l) //接收的不是引用，而只是一个值
{
this->swap(l);
return *this;
}
~list()
{
clear(); //先将有效元素释放掉
//然后将头节点也释放掉，并置空
delete _head;
_head = nullptr;
}
///////////////////////////////////////////////////////////
// 正向迭代器和反向迭代器
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
////////////////////////////////////////////////////////////
// List的插入和删除
// 在pos位置前插入值为val的节点
void insert(iterator pos, const T& x)
{
Node* newnode = new Node(x); //开辟新节点
Node* prev = pos._node;
newnode->_prev = prev->_prev;
newnode->_next = prev;
newnode->_prev->_next = newnode;
prev->_prev = newnode;
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
assert(pos != end()); // 防止头结点被删除
Node* cur = pos._node; // 找到pos位置的结点
Node* cur_prev = cur->_prev; // 找到pos的前驱
Node* cur_next = cur->_next; // 找到pos的后继
// 删除cur
delete cur;
// 缝合： cur_prev <-> cur(删) <-> cur_next
cur_prev->_next = cur_next;
cur_next->_prev = cur_prev;
return iterator(cur_next);
}
void push_back(const T& x)
{
//第一种自己实现
/*Node* newnode = new Node(x);
_head->_prev->_next = newnode;
newnode->_prev = _head->_prev;
newnode->_next = _head;
_head->_prev = newnode;*/
//第二种复用insert
insert(end(), x); //在end（pHead）前插入，即尾插
}
void push_front(const T& x)
{
insert(begin(), x); // 在begin（头结点的下一个结点）前插入，即头插
}
void pop_back()
{
erase(--end()); // 删除最后一个元素，即尾结点
}
void pop_front()
{
erase(begin()); // 删除头结点的下一个结点（即begin位置的结点）
}
void clear()
{
iterator cur = begin(); //注意要传迭代器，因为等会erase只接收迭代器
while (cur != end())
{
erase(cur++); //因为erase完迭代器会失效，所以要重新赋值，或者cur++
}
}
void swap(liren::list<T>& l)
{
::swap(_head, l._head); //直接交换两处的指针即可
}
//////////////////////////////////////////////////////////////
// List的元素访问操作
// 注意：List不支持operator[]
T& front()
{
return _head->_next->_val;
}
const T& front()const
{
return _head->_next->_val;
}
T& back()
{
return _head->_prev->_val;
}
const T& back()const
{
return _head->_prev->_val;
}
///////////////////////////////////////////////////////////////
// List的容量相关
size_t size() const
{
Node* cur = _head->_next;
size_t count = 0;
while (cur != _head)
{
count++;
cur = cur->_next;
}
return count;
}
bool empty() const
{
return _head == _head->_next;
}
void resize(size_t n, const T& val = T())
{
size_t sz = size();
if (n <= sz)
{
while (n <= sz)
{
pop_back();
sz--;
}
}
else
{
while (sz < n)
{
push_back(val);
sz++;
}
}
}
private:
void CreateHead()
{
_head = new Node; //不传参，这样子node就会调用缺省值进行初始化，比较方便，但前提是要在list_node的构造函数中设置缺省值
_head->_next = _head;
_head->_prev = _head;
}
Node* _head;
};
template<class T>
void PrintList(const liren::list<T>& l)
{
list<int>::const_iterator it = l.begin();
while (it != l.end())
{
//*it = 10;
cout << *it << " ";
++it;
}
cout << endl;
}
void test1()
{
list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
ls.push_back(4);
/*list<int>::const_iterator it = ls.begin();
while (it != ls.end())
{
cout << *it << " ";
it++;
}
cout << endl;*/
PrintList(ls);
}
void test2()
{
list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
ls.push_back(4);
list<int>::reverse_iterator rit = ls.rbegin();
while (rit != ls.rend())
{
cout << *rit << " ";
rit++;
}
cout << endl;
ls.clear();
for (auto e : ls)
{
cout << e << " ";
}
}
}test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include "list.h"
int main()
{
liren::test2();
return 0;
}Ⅳ. list 与 vector的区别
vector 与 list 都是 STL 中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
| vector | list | |
|---|---|---|
| 底层结构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随机访问 | 支持随机访问，访问某个元素效率 O(1) | 不支持随机访问，访问某个元素效率 O(n) |
| 插入与删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为 O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为 O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率小，缓存利用率小 |
| 迭代器 | 原生指针 | 原生指针的封装 |
| 迭代器失效问题 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效；删除元素时，当前迭代器需要重新赋值否则会失效 | insert不会导致迭代器失效；erase只会导致当前迭代器失效，其它迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除的效率时候使用 | 大量插入和删除操作，不关心随机访问时候使用 |