前言
本篇博客讲解c++STL中的list
💓 个人主页：普通young man-CSDN博客
⏩ 文章专栏：C++_普通young man的博客-CSDN博客
⏩ 本人giee: 普通小青年 (pu-tong-young-man) - Gitee.com
若有问题 评论区见📝
🎉欢迎大家点赞👍收藏⭐文章
本篇文章主要讲解list的用法和list的代码实现，这个list的用法和vector string的接口用法都差不多，所以我不会讲解太多，如果大家有疑问就去看我以前的博客
目录
list的介绍及使用
1，介绍
2，使用
list的构造
list iterator的使用
list capacity
list element access
Modifiers:
list模拟实现
解析
1. 基础结构定义
list_node 结构体
2. 迭代器定义
list_iterator 结构体
3. 链表类定义
list 类
4. list 类的成员函数解析
构造与析构
插入与删除
迭代器操作
其他操作
5. 辅助函数
Print_t 函数
总结
注意事项
list的介绍及使用
1，介绍
list - C++ Reference (cplusplus.com)
https://legacy.cplusplus.com/reference/list/list/?kw=list
这里可以看出list是一个双向带环的链表
2，使用
list的接口和我们之前的vector和string的用法差不多，以下我展示一些常见的接口
list的构造
| 构造函数(list::list - C++ Reference (cplusplus.com)) | 描述 |
|---|---|
list() | 构造一个空的 std::list。 |
list(size_type n, const value_type& val = value_type()) | 构造一个包含 n 个值为 val 的元素的 std::list。如果 val 没有显式给出，则使用默认构造的值。 |
list(const list& x) | 拷贝构造函数，复制另一个 std::list 实例的内容。 |
list(InputIterator first, InputIterator last) | 从输入迭代器范围 [first, last) 构造一个新的 std::list，其中 first 和 last 分别是输入序列的开始和结束迭代器。 |
演示代码
template <class T>
void Print(const list<T>& tmp) {for (auto it : tmp){cout << it << " ";}cout << endl;
}
void test1() {//list<int> a1{ 1,2,3,4,5,6 };list<int> a1(10, 1);list<int> a2(a1.begin(),a1.end());list<int> a3(10, 2);a1 = a2;Print(a1);Print(a2);Print(a3);}list iterator的使用
| 函数声明 | 描述 |
|---|---|
begin() | 返回指向列表中第一个元素的双向迭代器。 |
end() | 返回指向列表中最后一个元素之后位置的双向迭代器。 |
rbegin() | 返回指向列表中最后一个元素的反向迭代器，即正向的 end() 位置。 |
rend() | 返回指向列表中第一个元素之前位置的反向迭代器，即正向的 begin() 位置。 |
演示代码
template <class T>
void Print(const list<T>& tmp) {//auto ch = tmp.begin();auto ch = tmp.begin();while (ch != tmp.end()){cout << *ch << " ";ch++;}for (auto it : tmp){cout << it << " ";}cout << endl;
}list capacity
| 函数声明 | 描述 |
|---|---|
empty() | 检测 std::list 是否为空。如果列表为空，则返回 true；否则返回 false。 |
size() | 返回 std::list 中有效节点的个数。 |
演示代码
void test4() {list<int> a1;a1.push_back(1);a1.push_back(2);a1.push_back(3);if (a1.empty()){cout << "no empty" << endl;}else{cout << "yes emptyz" << endl;}cout << a1.size() << endl;}list element access
| 函数声明 | 描述 |
|---|---|
front() | 返回 std::list 的第一个节点中值的引用。 |
back() | 返回 |
Modifiers:
| 函数声明 | 描述 |
|---|---|
push_front(val) | 在 std::list 的首元素前插入值为 val 的新元素。 |
pop_front() | 删除 std::list 中的第一个元素。 |
push_back(val) | 在 std::list 的尾部插入值为 val 的新元素。 |
pop_back() | 删除 std::list 中的最后一个元素。 |
insert(position, val) | 在 std::list 的指定位置 position 插入值为 val 的新元素。 |
erase(position) | 删除 std::list 中位于 position 的元素。 |
swap(list) | 交换当前 std::list 与另一个 std::list 中的所有元素。 |
clear() | 清空 std::list 中的所有有效元素。 |
这些接口以前都使用过，所以这里就不使用了
list的迭代器失效
vector里面insert和erase都会出现迭代器失效的问题，在list里面insert是不会出现迭代器失效的问题，为什么？因为他们不是在一个内存中操作，反之list的erase会出现迭代器失效的问题，因为当释放一个节点的时候指向那个节点的指针变成了野指针。
这里我们先看一下他的返回值是iterator
这边直接报错了
这个迭代器失效我们该如何去解决?
话可以实现一个删除所有的偶数
template <class T>
void Print(const list<T>& tmp) {//auto ch = tmp.begin();auto ch = tmp.begin();while (ch != tmp.end()){cout << *ch << " ";ch++;}cout << endl;for (auto it : tmp){cout << it << " ";}cout << endl;
}void test5() {int arr[] = { 1,2,3,4,5,6,7 };int n = sizeof(arr) / sizeof(arr[0]);list<int> a1(arr,arr+n);auto it = a1.begin();while (it != a1.end()){if (*it % 2 == 0) {a1.erase(it++);//将这个位置传过去之后}else{it++;}}Print(a1);
}list模拟实现
只实现一些常用接口
#pragma once
#include <cassert> // 包含断言头文件
#include <iostream> // 包含输入输出流头文件
#include <initializer_list> // 包含用于初始化列表的头文件using namespace std;namespace yang {// 定义链表节点结构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, 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++(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) const {return _node == s._node;}// 不等于运算符bool operator!=(const Self& s) const {return _node != s._node;}};// 链表类定义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; // 常量迭代器的别名// 初始化为空链表void empty_init() {_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}// 默认构造函数list() {empty_init();}// 复制构造函数list(const list<T>& ls) {empty_init();for (auto& it : ls)push_back(it);}// 从初始化列表构造list(initializer_list<T> ls) {empty_init();for (auto& it : ls)push_back(it);}// 析构函数~list() {clear();delete _head;_head = nullptr;}// 交换函数void swap(list<T>& ls) {std::swap(_head, ls._head);std::swap(_size, ls._size);}// 赋值运算符，使用交换惯用法list<T>& operator=(list<T> ls) {swap(ls);return *this;}// 清除所有元素void clear() {auto it = begin();while (it != end()) {it = erase(it);}}// 在链表尾部添加元素void push_back(const T& val) {insert(end(), val);}// 在链表头部添加元素void push_front(const T& val) {insert(begin(), val);}// 在指定位置之前插入值iterator insert(iterator pos, const T& val) {Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);cur->_prev = newnode;newnode->_next = cur;prev->_next = newnode;newnode->_prev = prev;++_size;return iterator(newnode); // 返回指向新插入元素的迭代器}// 移除第一个元素void pop_front() {erase(begin());}// 移除最后一个元素void pop_back() {erase(--end());}// 移除指定位置的元素iterator erase(iterator pos) {Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;next->_prev = prev;prev->_next = next;delete pos._node;--_size;return iterator(next); // 返回指向下一个元素的迭代器}// 返回指向链表开始处的迭代器iterator begin() {return iterator(_head->_next);}// 返回指向链表结束处的迭代器iterator end() {return iterator(_head);}// 返回指向链表开始处的常量迭代器const_iterator begin() const {return const_iterator(_head->_next);}// 返回指向链表结束处的常量迭代器const_iterator end() const {return const_iterator(_head);}// 返回链表的大小size_t size() const {return _size;}// 判断链表是否为空bool empty() const {return _size == 0;}private:Node* _head; // 指向头节点的指针size_t _size; // 链表中的元素数量};// 打印容器内元素的函数template <class Container>void Print_t(const Container& tmp) {for (auto ch = tmp.begin(); ch != tmp.end(); ++ch) {std::cout << *ch << " ";}cout << endl;}// 展示使用的函数void func(const list<int>& lt) {Print_t(lt);}// 测试函数void test1() {list<int> lt0({1, 2, 3, 4, 5, 6});list<int> lt1 = {1, 2, 3, 4, 5, 6, 7, 8};const list<int>& lt3 = {1, 2, 3, 4, 5, 6, 7, 8};func(lt0);Print_t(lt1);}
}解析
以下是您提供的代码的详细解析：
1. 基础结构定义
list_node 结构体
这是链表的基本组成单元，它包含了一个数据成员 _data 和两个指针成员 _next 和 _prev 分别指向链表中的下一个和前一个节点。
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) {}
};2. 迭代器定义
list_iterator 结构体
这是一个双向迭代器，它允许你从前向后或从后向前遍历链表。迭代器持有指向当前节点的指针 _node。
template<class T, class Ref, class Ptr>
struct list_iterator {// ... iterator implementation ...
};3. 链表类定义
list 类
这是一个模板类，实现了双向链表的基本功能，包括插入、删除、迭代等操作。
template <class T>
class list {// ... list implementation ...
};4. list 类的成员函数解析
构造与析构
- 默认构造函数：创建一个空链表。
- 复制构造函数：通过拷贝另一个
list对象来创建一个新的list。 - 从初始化列表构造：通过给定的初始化列表来创建一个新的
list。 - 析构函数：释放链表中的内存资源。
list() {empty_init();
};list(const list<T>& ls) {empty_init();for (auto& it : ls)push_back(it);
};list(initializer_list<T> ls) {empty_init();for (auto& it : ls)push_back(it);
};~list() {clear();delete _head;_head = nullptr;
};插入与删除
push_back：在链表尾部插入一个新元素。push_front：在链表头部插入一个新元素。insert：在给定迭代器的位置插入一个新元素。pop_front：移除链表的第一个元素。pop_back：移除链表的最后一个元素。erase：移除指定迭代器位置的元素。
void push_back(const T& val) {insert(end(), val);
};void push_front(const T& val) {insert(begin(), val);
};iterator insert(iterator pos, const T& val) {// ... implementation details ...
};void pop_front() {erase(begin());
};void pop_back() {erase(--end());
};iterator erase(iterator pos) {// ... implementation details ...
};迭代器操作
begin：返回指向链表开始位置的迭代器。end：返回指向链表结束位置的迭代器（实际上是最后一个节点之后的位置）。
iterator begin() {return _head->_next;
};iterator end() {return _head;
};const_iterator begin() const {return _head->_next;
};const_iterator end() const {return _head;
};其他操作
clear：移除链表中的所有元素。size：返回链表中的元素个数。empty：判断链表是否为空。swap：交换两个链表的内容。operator=：赋值操作符，使用交换惯用法实现。
void clear() {auto it = begin();while (it != end()) {it = erase(it);}
};size_t size() const {return _size;
};bool empty() const {return _size == 0;
};void swap(list<T>& ls) {// ... implementation details ...
};list<T>& operator=(list<T> ls) {swap(ls);return *this;
};5. 辅助函数
Print_t 函数
这是一个通用的打印函数，可以用来打印任何实现了迭代器接口的容器。
template <class Container>
void Print_t(const Container& tmp) {// ... implementation details ...
}总结
该实现提供了一个简单的双向链表，支持基本的操作，如插入、删除、遍历等。它还包含了一些辅助函数，比如 Print_t 用于打印链表内容，以及一个测试函数 test1 来展示如何使用这些功能。
注意事项
- 代码中有一些注释掉的部分，例如
push_back的原始实现，这些部分可以根据需要恢复。 - 代码中没有实现
find方法，如果需要查找特定元素，可以考虑实现该方法。 - 代码中使用了
assert.h，但在实际的链表实现中可能不需要，因为没有使用断言的地方。 - 可以考虑添加更多的安全检查，例如在删除元素时检查迭代器的有效性。
