博主主页：Yan. yan.
C语言专栏
数据结构专栏
力扣牛客经典题目专栏
C++专栏
list_16">一、 list的介绍和使用
list_17">1.1、list的介绍
- list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list 的底层是双向链表结构，双向链表中的每个元素存储在互不相关的独立节点中，在节点中通过指针指向的前一个元素和后一个元素。
list_20">1.2、list的使用
list的文本介绍
list在实际中非常重要，在实际中我们熟悉常用的接口就可以，下面列出了需要我们重点掌握的接口。
list_23">1.2.1、list的构造
| 构造函数 | 接口说明 |
|---|---|
| list() | 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 |
void TestList1()
{
list<int> l1; // 构造空的l1
list<int> l2(4, 100); // l2中放4个值为100的元素
list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3
list<int> l4(l3); // 用l3拷贝构造l4
// 以数组为迭代器区间构造l5
int array[] = { 16,2,77,29 };
list<int> l5(array, array + sizeof(array) / sizeof(int));
// 列表格式初始化C++11
list<int> l6{ 1,2,3,4,5 };
// 用迭代器方式打印l5中的元素
list<int>::iterator it = l5.begin();
while (it != l5.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// C++11范围for的方式遍历
for (auto& e : l5)
cout << e << " ";
cout << endl;
}
list_iterator_64">1.2.2、list iterator的使用
| 函数声明 | 接口说明 |
|---|---|
| begin() + end() | 返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器 |
| rebegin() + rend() | 返回第一个元素的 reverse_iterator，即 end 位置，返回最后一个一个元素下一个位置的 reverse_iterator，即 begin 位置 |
注意： begin 与 end 为正向迭代器，对迭代器执行 ++ 操作，迭代器向后移动。rbegin 与 rend 为反向迭代器，对迭代器执行 ++ 操作，迭代器向前移动。由于 list 的底层物理空间并不连续，所以 list 的迭代器不再是原生指针，并且 list 的迭代器没有对 + 和 - 进行重载，只重载了 ++ 和 – ，因为空间不连续，重载 + 会比较复杂。即 l.begin() + 5 是不被允许的。
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;
}
list_capacity_113">1.2.3、list capacity（容量相关）
| 函数声明 | 接口说明 |
|---|---|
| empty | 检测 list 是否为空，是返回 true，否则返回 false |
| size | 返回 list 中有效节点个数 |
list_element_access_119">1.2.4、list element access（元素访问）
| 函数声明 | 接口说明 |
|---|---|
| front | 返回 list 的第一个节点中值的引用 |
| back | 返回 list 的最后一个节点中值的引用 |
list_modifiers_125">1.2.5、list modifiers（链表修改）
| 函数声明 | 接口说明 |
|---|---|
| push_front | 在 list 的第一个节点前插入值为 val 的节点 |
| pop_front | 删除 list 中第一个节点 |
| push_back | 在 list 尾部插入一个值为 val 的节点 |
| pop_back | 删除 list 中最后一个节点 |
| insert | 在 list 的 position 位置中插入一个值为 val 的节点 |
| erase | 删除 list position 位置的节点 |
| swap | 交换两个 list 的节点 |
| clear | 清空 list 中的有效元素 |
list_operation_136">1.2.6、list operation（对链表的一些操作）
| 函数声明 | 接口说明 |
|---|---|
| reverse | 对链表进行逆置 |
| sort | 对链表中的元素进行排序（稳定排序） |
| merge | 对两个有序的链表进行归并，得到一个有序的链表 |
| unique | 对链表中的元素去重 |
| remove | 删除具有特定值的节点 |
| splice | 将 A 链表中的节点转移到 B 链表 |
list_146">二、list的模拟实现
list_147">2.1、list的节点
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _val;
ListNode(const T& val = T())
{
_next = nullptr;
_prev = nullptr;
_val = val;
}
};
list_166">2.2、list的成员变量
class list
{
typedef ListNode<T> Node;
public:
//一些成员函数
private:
Node* _head;
}
list_179">2.3、list的迭代器
list 的迭代器不能再使用原生指针，如果 list 的迭代器使用原生指针的话，那对迭代器解引用得到的是一个节点，而我们希望对迭代器解引用可以得到节点里面存储的元素，并且 list 在底层的物理空间并不连续，如果使用原生指针作为 list 的迭代器，那对迭代器执行 ++ 操作，并不会让迭代器指向下一个节点。因此我们需要对 list 的迭代器进行封装，然后将一些运算符进行重载，以实现迭代器本该有的效果。
2.3.1、普通迭代器
template<class T>
struct _list_iterator
{
typedef ListNode<T> Node;
Node* _node;
_list_iterator(Node* val)
{
_node = val;
}
T& operator* ()
{
return _node->_val;
}
T* operator-> ()//迭代器通过->应该指向节点中的元素，因此返回的是一个T类型的地址
{
return &(_node->_val);
}
bool operator!= (const _list_iterator<T>& right)
{
return _node != right._node;
}
_list_iterator<T> operator++()
{
_node = _node->_next;
return *this;
}
_list_iterator<T> operator++(int)
{
_list_iterator<T> tmp(this->_node);
_node = _node->_next;
return tmp;
}
};
这里的类名不能直接叫 iterator，因为每种容器的迭代器底层实现可能都有所不同，即可能会为每一种容器都单独实现一个迭代器类，如果都直接使用 iterator，会导致命名冲突。其次，迭代器类不需要我们自己写析构函数、拷贝构造函数、赋值运算符重载函数，直接使用默认生成的就可以，言外之意就是这里使用浅拷贝即可，因为迭代器只是一种工具，它不需要对资源进行释放清理，资源释放清理工作是在容器类中实现的，浅拷贝的问题就出在会对同一块空间释放两次，而迭代器无需对空间进行释放，所以浅拷贝是满足我们需求的。
2.3.2、const迭代器
上面我们实现了普通迭代器，那 const 迭代器该如何实现呢？直接在容器类里面写上一句 typedef const _list_iterator const_iterator 可以嘛？答案是不可以，const 迭代器本质是限制迭代器指向的内容不能修改，而 const 迭代器自身可以修改，它可以指向其他节点。前面这种写法，const 限制的就是迭代器本身，会让迭代器无法实现 ++ 等操作。那如何控制迭代指向的内容不能修改呢？可以通过控制 operator* 的返回值来实现。但是仅仅只有返回值类型不同，是无法构成函数重载的。那要怎样才能在一个类里面实现两个 operator* 让他俩一个返回普通的 T&，一个返回 const T& 呢？一般人可能想着那就再单独写一个 _list_const_iterator 的类，这样也行，就是会比较冗余，我们可以通过在普通迭代器的基础上，再传递一个模板参数，让编译器来帮们生成呀。除此之外， operator->也需要实现 const 版本，因此还需要第三个模板参数。
template<class T,class Ref, class Ptr>
struct _list_iterator
{
typedef ListNode<T> Node;
typedef _list_iterator<T, Ref, Ptr> self;
Node* _node;
_list_iterator(Node* val)
{
_node = val;
}
Ref operator* ()
{
return _node->_val;
}
Ptr operator-> ()
{
return &(_node->_val);
}
bool operator!= (const self& right) const
{
return _node != right._node;
}
bool operator== (const self& right) const
{
return _node == right._node;
}
self operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp(this->_node);
_node = _node->_next;
return tmp;
}
self operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
};
//operator->的使用场景
struct A
{
A(int a = 0, int b = 0)
{
_a = a;
_b = b;
}
int _a;
int _b;
};
void Textlist3()
{
wcy::list<A> l;
l.push_back(A(1, 2));
l.push_back(A(3, 4));
l.push_back(A(5, 6));
l.push_back(A(7, 8));
wcy::list<A>::iterator it = l.begin();
while (it != l.end())
{
cout << it->_a << ',' << it->_b << " ";
cout << endl;
it++;
}
}
list_333">2.4、list的成员函数
2.4.1、构造函数
list()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _next;
}
2.4.2、拷贝构造函数
list(const list& ll)
//list(const list<T>& ll)
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
for (auto& e : ll)
{
push_back(e);
}
}
2.4.3、赋值运算符重载
void swap(list<T> l2)
{
std::swap(_head, l2._head);
}
list& operator=(const list ll)
//list<T>& operator=(const list<T> ll)
{
//现代写法
swap(ll);
return *this;
}
2.4.4、push_back
void push_back(const T& val)
{
//先找尾
Node* tail = _head;
while (tail->_next != _head)
{
tail = tail->_next;
}
//插入元素
Node* newnode = new Node(val);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
2.4.5、迭代器相关
iterator begin()
{
return _head->_next;//单参数的构造函数支持隐式类型转换
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;//单参数的构造函数支持隐式类型转换
}
const_iterator end() const
{
return _head;
}
2.4.6、 insert
iterator insert(iterator pos, const T& val)
{
//找到 pos 位置的前一个位置
Node* cur = pos._node;
Node* prev = cur->_prev;
//插入元素
Node* newnode = new Node(val);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return newnode;
}
2.4.7、erase
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;
cur = nullptr;
return next;
}
2.4.8、 push_front
void pop_back()
{
erase(--end());
}
2.4.10、pop_front
void pop_front()
{
erase(begin());
}
2.4.11、 size
size_t size()
{
size_t sz = 0;
iterator it = begin();
while (it != end())
{
it++;
sz++;
}
return sz;
}
2.4.12、clear
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
2.4.13、析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
clear 和 析构函数的主要区别在于是否释放头节点。
