网站布局的三种基本方法,wordpress utc时间设置,开发区全力做好网站建设,简单公司网站前言 本篇博客讲解cSTL中的list #x1f493; 个人主页#xff1a;普通young man-CSDN博客 ⏩ 文章专栏#xff1a;C_普通young man的博客-CSDN博客 ⏩ 本人giee: 普通小青年 (pu-tong-young-man) - Gitee.com 若有问题 评论区见#x1f4dd; #x1f389;欢迎大家点赞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/?kwlist 这里可以看出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 listT tmp) {for (auto it : tmp){cout it ;}cout endl;
}
void test1() {//listint a1{ 1,2,3,4,5,6 };listint a1(10, 1);listint a2(a1.begin(),a1.end());listint 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 listT 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() {listint 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 listT 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]);listint a1(arr,arrn);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 {// 定义链表节点结构templateclass Tstruct list_node {T _data; // 节点中存储的数据list_nodeT* _next; // 指向下一个节点的指针list_nodeT* _prev; // 指向前一个节点的指针// 构造函数可选地初始化数据list_node(const T data T()): _data(data), _next(nullptr), _prev(nullptr) {}};// 迭代器结构templateclass T, class Ref, class Ptrstruct list_iterator {typedef list_nodeT Node; // 节点类型的别名typedef list_iteratorT, 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 Tclass list {public:typedef list_nodeT Node; // 节点类型的别名typedef list_iteratorT, T, T* iterator; // 非常量迭代器的别名typedef list_iteratorT, 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 listT ls) {empty_init();for (auto it : ls)push_back(it);}// 从初始化列表构造list(initializer_listT ls) {empty_init();for (auto it : ls)push_back(it);}// 析构函数~list() {clear();delete _head;_head nullptr;}// 交换函数void swap(listT ls) {std::swap(_head, ls._head);std::swap(_size, ls._size);}// 赋值运算符使用交换惯用法listT operator(listT 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 Containervoid Print_t(const Container tmp) {for (auto ch tmp.begin(); ch ! tmp.end(); ch) {std::cout *ch ;}cout endl;}// 展示使用的函数void func(const listint lt) {Print_t(lt);}// 测试函数void test1() {listint lt0({1, 2, 3, 4, 5, 6});listint lt1 {1, 2, 3, 4, 5, 6, 7, 8};const listint lt3 {1, 2, 3, 4, 5, 6, 7, 8};func(lt0);Print_t(lt1);}
}
解析
以下是您提供的代码的详细解析
1. 基础结构定义
list_node 结构体
这是链表的基本组成单元它包含了一个数据成员 _data 和两个指针成员 _next 和 _prev 分别指向链表中的下一个和前一个节点。
templateclass T
struct list_node {T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T data T()): _data(data), _next(nullptr), _prev(nullptr) {}
};
2. 迭代器定义 list_iterator 结构体
这是一个双向迭代器它允许你从前向后或从后向前遍历链表。迭代器持有指向当前节点的指针 _node。
templateclass 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 listT ls) {empty_init();for (auto it : ls)push_back(it);
};list(initializer_listT 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(listT ls) {// ... implementation details ...
};listT operator(listT 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但在实际的链表实现中可能不需要因为没有使用断言的地方。可以考虑添加更多的安全检查例如在删除元素时检查迭代器的有效性。
