文章目录
1. list 的介绍与使用
1.1 list 的介绍
list 容器底层实现就是一个带虚拟头节点的双向循环链表
1.2 list 的使用
1.2.1 list 的构造
| 构造函数 | 接口说明 |
|---|---|
| list (size_type n, const value_type& val =value_type()) | 构造的 list 中包含 n 个值为 val 的元素 |
| list () | 构造空的 list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造 list |
#include <iostream>
using namespace std;
#include <list>
#include <vector>
int main()
{
list<int> lt1(10, 1); // 构造 10 个 1
list<int> lt2; // 构造空的 list
list<int> lt3(lt1); // 拷贝构造
vector<int> v(11, 2);
list<int> lt4(v.begin(), v.end()); // 迭代器构造
return 0;
}
1.2.2 list iterator 的使用
list 的迭代器通常被设计成一个类，它包含着一个指向当前链表节点的指针
| 函数声明 | 接口说明 |
|---|---|
| begin + end | 返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的 reverse_iterator，即 end 位置，返回最后一个元素下一个位置的 reverse_iterator，即 begin位置 |
auto it = lt1.begin();
while (it != lt1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
auto it1 = lt4.rbegin();
while (it1 != lt4.rend())
{
cout << *it << " ";
++it;
}
cout << endl;
注意：
- 反向迭代器的操作也是 ++ 让迭代器向前移动。
1.2.3 list capacity
| 函数声明 | 接口说明 |
|---|---|
| empty() | 检测 list 是否为空，空返回 true，否则返回 false |
| size() | 返回 list 中有效节点个数 |
C++ 里 布尔类型的底层常用 一字节 存储
- true 通常为 0x01
- false 通常为 0x00
- 但具体实现由编译器决定，标准仅要求 false 和 true 在转换为整数时分别为 0 和 1。
cout << lt1.empty() << endl;
cout << lt2.empty() << endl;
cout << lt1.size() << endl;
1.2.4 list element access
| 函数声明 | 函数接口 |
|---|---|
| front() | 返回 list 的第一个节点的引用 |
| back() | 返回 list 的最后一个节点的引用 |
lt1.push_front(2);
lt1.push_back(3);
cout << lt1.front() << endl;
cout << lt1.back() << endl;
1.2.5 list modifiers
| 函数声明 | 接口说明 |
|---|---|
| push_front | 在 list 首元素前插入值为 val 的元素 |
| pop_front | 删除 list 中第一个元素 |
| push_back | 在 list 尾部插入值为 val 的元素 |
| pop_bakc | 删除 list 中最后一个元素 |
| insert | 在 list 的 pos 位置插入值为 val 的元素 |
| erase | 删除 pos 位置的元素 |
| swap | 交换两个 list |
| clear | 清空 list 中的有效元素 |
int main()
{
list<int> lt;
lt.push_back(1); // 尾插
lt.push_back(2);
lt.push_back(3);
lt.push_front(4); // 头插
lt.push_front(5);
lt.push_front(6);
for (auto& x : lt)
cout << x << " ";
cout << endl;
lt.pop_back(); // 尾删
lt.pop_front(); // 头删
for (auto& x : lt)
cout << x << " ";
cout << endl;
auto pos = find(lt.begin(), lt.end(), 4); // 查找
lt.insert(pos, 7); // 在 pos 前插入
pos = find(lt.begin(), lt.end(), 1); // 查找
lt.erase(pos); // 删除 pos 位置
for (auto& x : lt)
cout << x << " ";
cout << endl;
list<int> lt1 = { 1, 2, 3 }; // C++11 特性，之后再讲
lt.swap(lt1); // 交换两个 list
for (auto& x : lt)
cout << x << " ";
cout << endl;
for (auto& x : lt1)
cout << x << " ";
cout << endl;
lt1.clear(); // 清空有效元素
cout << lt1.size() << endl;
return 0;
}
1.2.6 迭代器失效问题
前面提过，list 的迭代器通常被设计成一个类，包含着一个指向当前节点的指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为 list 的底层结构是 带虚拟头节点的双向循环链表，因此只有在删除时，迭代器才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不受影响。
int main()
{
list<int> lt = { 1,2,3,4,5,6,7 }; // C++11 特性
/* 错误写法
auto it = lt.begin();
while (it != lt.end())
{
// erase() 函数执行之后，it所指向节点已被删除，it 失效，在下一次使用之前必须给it赋值
lt.erase(it);
++it;
}
*/
auto it = lt.begin();
while (it != lt.end())
{
lt.erase(it++); // it = lt.erase(it);
}
return 0;
}
2. list 的模拟实现
list 容器本质是对 带头节点的双向循环链表 的封装，再加上前面说的 list 迭代器单独成一个类，我们很容易就能理解它的大致架构。
本文主要讲解对 list 的封装，要是还不熟悉 双向循环带头链表 的可以去看前面的讲解: 双向循环链表。
- list_node 两个指针域与一个数据域
- list_iterator 用于封装迭代器的操作
- list 用于组织 list_node
2.1 值得注意的点：
迭代器进行拷贝的时候使用编译器默认生成的浅拷贝就行了，因为资源是被链表管理的，而非迭代器，迭代器只是用来模拟指针的行为
因为要适配迭代器的迭代，所以这里的 insert 和 erase 的返回值都是 迭代器类型
一个奇怪的实现 operator->()，迭代器模拟的是指针的行为，结构体的时候才需要使用 ->，我们知道结构体可以使用 (*it)._a ，也可以使用 it->_a，所以需要重载 ->，而 -> 是访问指针类型的，所以返回值为指针，但是它的使用就有点奇怪了
T* operator->() { return &_node->_data; } // 使用时 cout << it->_a << endl; // 实际上是两个 -> ，但是太难看了，所以省略了一个 cout << it.operator->()->_a << endl; // 第一个是运算符重载，第二个是原生指针的解引用
2.2 std::initializer_list
它是 C++11 引入的一个标准库特性，用于简化对象通过花括号初始化列表（如 {1, 2, 3}）进行初始化或赋值的操作。它是 <initializer_list> 头文件中定义的模板类。
用途：
允许容器、自定义类或函数接受花括号列表作为参数，例如：
// 直接构造 list<int> lt0({ 1,2,3,4,5,6 }); // 隐式类型转换 list<int> lt1 = { 1,2,3,4,5,6,7,8 };
特性：
- 元素是只读的（通过 const T* 访问）。
- 底层数据是浅拷贝（仅复制指针，不复制元素本身）。
- 通常用于临时初始化场景，需注意底层数据的生命周期。
其他地方和之前讲解的 vector 的迭代器类似，这里便不做过多赘述。
2.3 list.h
#pragma once
#include <assert.h>
#include <iostream>
using namespace std;
namespace zkp
{
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)
{
}
};
template<class T>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
_node = _node->_next; // 将迭代器指向的 node 指向下一个 node
return *this; // 返回这个迭代器
}
Self& operator--()
{
_node = _node->_prev; // 将迭代器指向的 node 指向上一个 node
return *this;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
template<class T>
struct list_const_iterator
{
typedef list_node<T> Node;
typedef list_const_iterator<T> Self;
Node* _node;
list_const_iterator(Node* node)
:_node(node)
{}
const T& operator*()
{
return _node->_data;
}
Self& operator++()
{
_node = _node->_next; // 将迭代器指向的 node 指向下一个 node
return *this; // 返回这个迭代器
}
Self& operator--()
{
_node = _node->_prev; // 将迭代器指向的 node 指向上一个 node
return *this;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T> iterator;
typedef list_const_iterator<T> const_iterator;
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
list(initializer_list<T> il)
{
empty_init();
for (auto& e : il)
{
push_back(e);
}
}
// lt2(lt1)
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
// lt1 = lt3
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void push_back(const T& x)
{
/*
Node* newnode = new Node(x);
newnode->_next = _head;
newnode->_prev = _head->_prev;
_head->_prev->_next = newnode;
_head->_prev = newnode;
++_size;
*/
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
// prev newnode cur
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
++_size;
return newnode;
}
void pop_back()
{
erase(end());
}
void pop_front()
{
erase(begin());
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
--_size;
return next;
}
size_t size() const
{
return _size;
}
bool empty() const
{
return _size == 0;
}
private:
Node* _head;
size_t _size;
};
struct AA
{
int _a1 = 1;
int _a2 = 1;
};
// 按需实例化
// T* const ptr1
// const T* ptr2
template<class Container>
void print_container(const Container& con)
{
// const iterator -> 迭代器本身不能修改
// const_iterator -> 指向内容不能修改
typename Container::const_iterator it = con.begin();
//auto it = con.begin();
while (it != con.end())
{
//*it += 10;
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : con)
{
cout << e << " ";
}
cout << endl;
}
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
*it += 10;
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
print_container(lt);
list<AA> lta;
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
list<AA>::iterator ita = lta.begin();
while (ita != lta.end())
{
//cout << (*ita)._a1 << ":" << (*ita)._a2 << endl;
// 特殊处理，本来应该是两个->才合理，为了可读性，省略了一个->
cout << ita->_a1 << ":" << ita->_a2 << endl;
cout << ita.operator->()->_a1 << ":" << ita.operator->()->_a2 << endl;
++ita;
}
cout << endl;
}
void test_list2()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
// insert以后迭代器不失效
list<int>::iterator it = lt.begin();
lt.insert(it, 10);
*it += 100;
print_container(lt);
// erase以后迭代器失效
// 删除所有的偶数
it = lt.begin();
while (it != lt.end())
{
if (*it % 2 == 0)
{
it = lt.erase(it);
}
else
{
++it;
}
}
print_container(lt);
}
void test_list3()
{
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
list<int> lt2(lt1);
print_container(lt1);
print_container(lt2);
list<int> lt3;
lt3.push_back(10);
lt3.push_back(20);
lt3.push_back(30);
lt3.push_back(40);
lt1 = lt3;
print_container(lt1);
print_container(lt3);
}
void func(const list<int>& lt)
{
print_container(lt);
}
}
2.4 迭代器模板的优化
我们不难发现，普通迭代器和 const迭代器的代码只有一点点区别，重合度太高了，有没有什么能解决这种情况呢？ 有的，兄弟有的，让我们看一下 库中是怎么实现的。
这里把原来一个模板参数 T 增加到了三个 T, T&, T*
- 普通迭代器：传入<T, T&, T*>
list_iterator<T, T&, T*> it; // operator* 返回 T&，operator-> 返回 T* - const迭代器：传入 <T, const T&, const T*>
list_iterator<T, const T&, const T*> const_it; // operator* 返回 const T&
这样，同一个迭代器模板就可以通过传入不同的模板参数生成普通迭代器和 const 迭代器，大大减少了重复代码
要修改的代码其实也不多，只不过是把原来迭代器参数模板增加到三个，再在 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*()
{
return _node->_data;
}
Ptr operator->()
{
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& s) const
{
return _node == s._node;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
};
2.5 list 的反向迭代器
前面我们说过不管是正向迭代器还是反向迭代器，它向后移动的操作都是 ++，反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。
template<class Iterator>
class ReverseListIterator
{
// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态
成员变量
// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:
typedef typename Iterator::Ref Ref;
typedef typename Iterator::Ptr Ptr;
typedef ReverseListIterator<Iterator> Self;
public:
// 构造
ReverseListIterator(Iterator it) : _it(it) {}
// 具有指针类似行为
Ref operator*()
{
Iterator temp(_it);
--temp;
return *temp;
}
Ptr operator->() { return &(operator*()); }
// 迭代器支持移动
Self& operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self temp(*this);
--_it;
return temp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self temp(*this);
++_it;
return temp;
}
// 迭代器支持比较
bool operator!=(const Self& l)const { return _it != l._it; }
bool operator==(const Self& l)const { return _it != l._it; }
Iterator _it;
};
3. list 与 vector 的对比
其实就是双向循环链表和动态数组的对比
| - | vector | list |
|---|---|---|
| 底层结构 | 动态数组 | 带头双向循环链表 |
| 随机访问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元素效率O(N) |
| 插入和删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对原生态指针(节点指针)进行封装 |
| 迭代器失效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |