虚拟主机网站源码,专业技能培训机构,cms网站搭建,学平面设计要多少钱文章目录 前言#xff1a;一.list的介绍及使用1. list的介绍2. list的使用2.1 list的构造2.2 list iterator的使用2.3 list capacity2.4 list element access2.5 list modifiers2.6 list的迭代器失效 二.list的模拟实现1. list的节点2. list的成员变量3.list迭代器相关问题3.1… 文章目录 前言一.list的介绍及使用1. list的介绍2. list的使用2.1 list的构造2.2 list iterator的使用2.3 list capacity2.4 list element access2.5 list modifiers2.6 list的迭代器失效 二.list的模拟实现1. list的节点2. list的成员变量3.list迭代器相关问题3.1 普通迭代器3.2 const迭代器 4. list的成员函数4.1 list的空初始化4.2 push_back4.3 构造函数4.4 insert4.4 erase4.5 push_front4.6 pop_front4.7 pop_back4.8 clear4.8 析构函数4.9 swap4.10 赋值运算符重载 最后想说 前言 C中的List容器是标准模板库STL中的一种序列容器它实现了双向链表的功能。与数组如vector和单向链表相比List容器提供了更加灵活的元素插入和删除操作特别是在容器中间位置进行这些操作时。
一.list的介绍及使用
1. list的介绍
双向链表结构 list容器使用双向链表来存储元素每个元素节点都包含数据部分和两个指针分别指向前一个元素和后一个元素。这种结构使得在链表的任何位置进行插入和删除操作都非常高效时间复杂度为O(1)。动态大小 list容器的大小可以在运行时动态改变即可以在程序运行过程中添加或移除元素。不支持随机访问 与vector和array等连续内存的容器不同list不支持随机访问迭代器不能直接通过索引获取元素而需要通过迭代器遍历。迭代器稳定性 在list中插入或删除元素不会导致其他迭代器失效除了指向被删除元素的迭代器。这是因为它通过调整相邻节点的指针来维护链表结构而不需要移动元素或重新分配内存。
2. list的使用
list的使用参考文档list的文档介绍
2.1 list的构造
构造函数接口说明list (size_type n, const value_type val value_type() )构造的list中包含n个值为val的元素list()构造空的listlist (const list x)拷贝构造函数list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造list
代码演示
#includelist
int main()
{listint l1;//构造空的l1;listint l2(4,100);//l2中存放4个值为100的元素listint l3(l2.begin(),l2.end());//用l2的[begin,end左开右闭区间构造l3;listint l4(l3);//用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[] { 16,2,77,29 };listint l5(array, array sizeof(array) / sizeof(int));// 列表格式初始化C11listint l6{ 1,2,3,4,5 };// 用迭代器方式打印l5中的元素listint::iterator it l5.begin();while (it ! l5.end()){cout *it ;it;}cout endl;// C11范围for的方式遍历for (auto e : l5)cout e ;cout endl;return 0;
}2.2 list iterator的使用
此处大家可暂时将迭代器理解成一个指针该指针指向list中的某个节点。
函数声明接口说明begin返回第一个元素的迭代器end返回最后一个元素下一个位置的迭代器rbegin返回一个指向容器中最后一个元素的反向迭代器即容器的反向起始rend返回一个反向迭代器该迭代器指向列表容器中第一个元素之前的理论元素该元素被认为是其反向结束。
注意
begin与end为正向迭代器对迭代器执行操作迭代器向后移动rbegin(end)与rend(begin)为反向迭代器对迭代器执行操作迭代器向前移动
代码演示
int main()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素// listint::iterator it l.begin(); // C98中语法auto it l.begin(); // C11之后推荐写法while (it ! l.end()){cout *it ;it;}cout endl;// 使用反向迭代器逆向打印list中的元素// listint::reverse_iterator rit l.rbegin();auto rit l.rbegin();while (rit ! l.rend()){cout *rit ;rit;}cout endl;return 0;
}2.3 list capacity
函数声明接口说明front检测list是否为空是返回true否则返回falsesize返回list中有效节点的个数
2.4 list element access
函数声明接口说明front返回list的第一个节点中值的引用back返回list的最后一个节点中值的引用
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中的有效元素
代码演示
#includeiostream
#includevector
using namespace std;void PrintList(const listint l)
{// 注意这里调用的是list的 begin() const返回list的const_iterator对象for (listint::const_iterator it l.begin(); it ! l.end(); it){cout *it ;}cout endl;
}// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList1()
{int array[] { 1, 2, 3 };listint L(array, array sizeof(array) / sizeof(array[0]));// 在list的尾部插入4头部插入0L.push_back(4);L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);
}// insert /erase
void TestList2()
{int array1[] { 1, 2, 3 };listint L(array1, array1 sizeof(array1) / sizeof(array1[0]));// 获取链表中第二个节点auto pos L.begin();cout *pos endl;// 在pos前插入值为4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)区间中的元素vectorint v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 删除pos位置上的元素L.erase(pos);PrintList(L);// 删除list中[begin, end)区间中的元素即删除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}// resize/swap/clear
void TestList3()
{// 用数组来构造listint array1[] { 1, 2, 3 };listint l1(array1, array1 sizeof(array1) / sizeof(array1[0]));PrintList(l1);// 交换l1和l2中的元素listint l2;l1.swap(l2);PrintList(l1);PrintList(l2);// 将l2中的元素清空l2.clear();cout l2.size() endl;
}int main()
{TestList1();TestList2();TestList3();return 0;
}运行结果
2.6 list的迭代器失效 前面已经说过了此处可以将迭代器理解为类似于指针的东西迭代器失效即迭代器指向的节点失效了即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list进行插入操作时不会导致迭代器失效只有删除时才会失效并且失效的是被删除节点的迭代器其他迭代器不会受到影响。
二.list的模拟实现
1. list的节点
templateclass T
struct list_node
{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T()):_data(x), _next(nullptr), _prev(nullptr){}
};2. list的成员变量
templateclass T
class list
{typedef list_nodeT Node;
public://成员函数
private:Node* _head; //哨兵位的头节点
};没有用访问限定符限制的成员class默认是私有的struct默认是公有的如果一个类既有公有也有私有就用class全部为公有一般用struct。这不是规定只是个惯例。
3.list迭代器相关问题
简单分析 emsp 这里不能像以前一样给一个结点的指针作为迭代器如果it是typedef的节点的指针it解引用得到的是节点不是里面的数据但是我们期望it解引用是里面的数据it我们期望走到下一个节点去而list中走不到下一个数据因为数组的空间是连续的可以走到下一个数据。但是链表达不到这样的目的。所以原身指针已经无法满足这样的行为怎么办呢这时候我们的类就登场了 用类封装一下节点的指针然后重载运算符模拟指针。 例如
reference operator*()const
{return (*node).data;
}
self opertor()
{node (link_type)((*node).next);return *this;
}3.1 普通迭代器
templateclass T
struct list_iterator
{typedef list_nodeT Node;typedef list_iteratorT Self;Node* _node;list_iterator(Node* node):_node(node){}T operator*() //用引用返回可以读数据也可以修改数据{return _node-_data;}T* 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){return _node ! s._node;}
};3.2 const迭代器
const迭代器在定义的时候不能直接定义成typedef const list_iteratorT const_iterator,const迭代器的本质是限制迭代器指向的内容不能被修改而前面的这种写法限制了迭代器本身不能被修改所以迭代器就不能进行操作。那该怎能办呢答案是我们可以实现一个单独的类
templateclass T
struct list_const_iterator
{typedef list_nodeT Node;typedef list_const_iteratorT Self;Node* _node;list_const_iterator(Node* node):_node(node){}const T operator*(){return _node-_data; //返回这个数据的别名但是是const别名所以不能被修改}const T* operator-(){return _node-_data; //我是你的指针const指针}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){return _node ! s._node;}
};普通法迭代器与const迭代器的区别就是普通迭代器可读可写const迭代器只能读 上面是我们自己实现的普通迭代器和const迭代器用两个类并且这两个类高度相似下来就让我们一起看一看库里面是怎么实现的吧 我们可以看到库里面是写了两个模板让编译器去生成对应的类。其本质上也是写了两个类只不过是让编译器去生成对应的类。
迭代器不需要我们自己写析构函数、拷贝构造函数、赋值运算符重载函数因为这里要的是浅拷贝例如我把一个迭代器赋值给另外一个迭代器就是期望两个迭代器指向同一个节点这里用浅拷贝即可拷贝给你我们两个迭代器就指向同一个节点。
4. list的成员函数
4.1 list的空初始化
void empty_init() //空初始化
{_head new Node();_head-_next _head;_head-_prev _head;
}4.2 push_back
//普通版本
void push_back(const T x)
{Node* new_node new Node(x);Node* tail _head-_prev;tail-_next new_node;new_node-_prev tail;new_node-_next _head;_head-_prev new_node;
}
//复用insert版本insert(end(),x);4.3 构造函数
list_node(const T x T()):_data(x), _next(nullptr), _prev(nullptr)
{}4.4 insert
iterator insert(iterator position; const T val)
{Node* cur pos._node;Node* newnode new Node(val);Node* prev cur-_prev;//prev newnode curprev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;return iterator(newnode);
}4.4 erase
iterator erase(iterator pos)
{assert(pos ! end());Node* del pos._node;Node* prev del-_prev;Node* next del-_next;prev-_next next;next-_prev prev;delete del;return iterator(next);
}4.5 push_front
void push_front(const T x)
{insert(begin(), x);
}4.6 pop_front
void pop_front()
{erase(begin());
}4.7 pop_back
void pop_back()
{erase(--end());
}4.8 clear
void clear()
{auto it begin();while (it ! end()){it erase(it);}
}4.8 析构函数
~list()
{clear();delete _head;_head nullptr;
}4.9 swap
void swap(listT tmp)
{std::swap(_head, tmp._head);//交换哨兵位的头节点
}4.10 赋值运算符重载
//现代写法
//lt2lt3
//listT operator(listT lt)
list operator(list lt) //不加模板参数
{swap(lt);//交换就是交换哨兵位的头节点return *this;
}//lt3传给lt去调用拷贝构造所以lt就和lt3有一样大的空间一样大的值lt2很想要也就是/this想要lt2之前的数据不想要了交换给lt,此时lt2就和lt3有一样大的空间一样大的值
//lt出了作用域就被销毁了构造函数和赋值运算符重载函数的形参和返回值类型可以只写类名 list不需要写模板参数这种写法在类里面可以不加只能在类里面可以这样写类外面是不行的一般情况下加上好一点。 最后想说
本章我们STL的List就介绍到这里下期我将介绍关于stack和queue的有关知识如果这篇文章对你有帮助记得点赞评论收藏 最后别忘了关注作者作者将带领你探索更多关于C方面的问题。
