C++ | list

 前言

本篇博客讲解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()	返回 std::list 的最后一个节点中值的引用。

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，但在实际的链表实现中可能不需要，因为没有使用断言的地方。
• 可以考虑添加更多的安全检查，例如在删除元素时检查迭代器的有效性。