做智能网站,一个网站的成本,个人网站可以做资讯吗?,建筑工程网名大全霸气一、介绍 官方给的 list的文档介绍
简单来说就是#xff1a; list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代。list的底层是双向链表结构#xff0c;双向链表中每个元素存储在互不相关的独立节点中#xff0c;在节点中…一、介绍 官方给的 list的文档介绍
简单来说就是 list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素。
这个时候大家可能觉得都是有序列表那么和vector有什么区别和对比吗实际上和我们学习数据结构时对链表和数组的对比很像我来介绍一下 std::list std::list 是一个双向链表支持在常数时间内对序列的任何位置进行插入和删除操作。由于其链表的性质list 不支持快速随机访问即不能通过索引以常数时间访问元素例如 list[5] 是非法的。list 更适用于元素频繁插入和删除的场景尤其是在序列的头部和尾部或者你不需要通过索引来访问元素。迭代器失效问题较少插入和删除操作不会导致除了被操作的元素之外的迭代器失效。在内存中不是连续存储的因此不支持指针算术运算并且可能导致较差的缓存性能。 std::vector std::vector 是一个动态数组可以在末尾快速地添加或移除元素均摊常数时间复杂度而且支持快速随机访问即可以以常数时间访问任意位置的元素。在 vector 的中间或开头插入或删除元素可能会导致较高的性能开销因为这些操作需要移动插入点之后或删除点之后的所有元素。适用于需要经常随机访问元素但对于插入和删除的频率较低的场景。在内存中是连续存储的这意味着可以使用指针算术并且有助于优化缓存使用。当 vector 重新分配更大的内存空间以容纳更多元素时所有的迭代器、引用和指针都可能失效。
那么list到底长什么样子呢上图片是不是就好理解了 二、list的使用 作为STL(标准模板库)中的一个类我们这篇blog的任务就是学习其的使用。
构造函数 构造函数接口说明list()构造空的listlist (size_type n, const value_type val value_type())构造的list中包含n个值为val的元素list (const list x)拷贝构造函数list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造list 上面虽然用了不少代名词我们直接上代码例子分析自然就清楚了分析在代码中。 如果迭代器看不懂可以看这一篇【C】C中的vector-CSDN博客里面详细介绍了 #include iostream
#include list
using namespace std;
int main()
{//listint l1; // 构造空的l1listint l2(4, 100); // l2中放4个值为100的元素listint l3(l2.begin(), l2.end()); // 用l2的[begin(), end()左闭右开的区间构造l3listint l4(l3); // 用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[] { 16,2,77,29 };std::listint l5(array, array sizeof(array) / sizeof(int));// 用迭代器方式打印l5中的元素for (std::listint::iterator it l5.begin(); it ! l5.end(); it)std::cout *it ;std::cout endl;// C11范围for的方式遍历for (auto e : l5)std::cout e ;std::cout endl;return 0;
} 其实我们可以看出来list这个类和之前的使用类的方法是基本一致的不过他需要一个int来确定这个序列容器的类型比如intchar....就是listint可以当成一个整体和vector很像。 list iterator的使用 此处大家可暂时将迭代器理解成一个指针该指针指向list中的某个节点 函数声明 接口说明 begin end 获取第一个数据位置的iterator/const_iterator 获取最后一个数据的下一个位置 的iterator/const_iterator rbegin rend 获取最后一个数据位置的reverse_iterator获取第一个数据前一个位置的 reverse_iterator PS 1. begin 与 end 为正向迭代器对迭代器执行 操作迭代器向后移动 2. rbegin(end) 与 rend(begin) 为反向迭代器对迭代器执行 操作迭代器向前移动 上代码 #include iostream
#include list
using namespace std;void print_list(const listint l)
{// 注意这里调用的是list的 begin() const返回list的const_iterator对象// 保护数据通过将l声明为常量引用我们保证了在print_list函数内部无法修改列表l的内容。// 这意味着无法添加、删除或修改列表中的任何元素。这是一种良好的编程实践// 特别是当函数的目的仅仅是读取数据而不修改数据时。for (listint::const_iterator it l.begin(); it ! l.end(); it){cout *it ;//如果不同const 就通过//*it 10; 编译不通过}cout endl;
}
int main()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素for (listint::iterator it l.begin(); it ! l.end(); it)cout *it ;cout endl;// 使用反向迭代器逆向打印list中的元素for (listint::reverse_iterator it l.rbegin(); it ! l.rend(); it)cout *it ;cout endl;return 0;
}常用的成员方法 list capacity 函数声明 接口说明 empty 检测 list 是否为空是返回 true 否则返回 false size 返回 list 中有效节点的个数 列表元素访问
函数声明 接口说明 empty 检测 list 是否为空是返回 true 否则返回 false size 返回 list 中有效节点的个数 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中的有效元素
上代码看实现 #include iostream
#include list
#include vector
using namespace std;
void PrintList(listint l)
{for (auto e : l)cout e ;cout endl;
}
//
// push_back/pop_back/push_front/pop_front
void TestList1()
{cout TestList1() endl;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()
{cout TestList2() endl;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()
{cout TestList3() endl;// 用数组来构造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);
//使用resize将l2的大小先增加到5个元素所有新添加的元素都将被赋值为99l2.resize(5, 99);PrintList(l2);// 将l2中的元素清空l2.clear();cout l2.size() endl;
}int main()
{TestList1();TestList2();TestList3();return 0;
} 好了目前通过上面这一段精简的代码我们把常用的成员方法基本解决了但是list的成员方法实在太多很多操作都是很特殊不常见的但是如果刚好需要又非常方便所以就是可以在需要的时候查官方文档。 list的迭代器失效 在之前我们学习过vector的迭代器会有失效的情况原因很简单指针失效了那么list会不会有这种情况呢答案是有的前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。所以影响相对vector来说比较小。 理解了吗两段代码来检测一下大家 #include iostream
#include list
using namespace std;void TestListIterator1()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));auto it l.begin();while (it ! l.end()){l.erase(it);it;}
}void TestListIterator2()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));auto it l.begin();while (it ! l.end()){l.erase(it); // it l.erase(it);}
}int main()
{TestListIterator1();TestListIterator2();return 0;
} 是 TestListIterator1 出错 还是 TestListIterator2 出错 如果你一眼就看出了那么恭喜你你掌握了。 其实很简单第一个当调用erase(it)后it被删除使得it失效。尝试在失效的迭代器上进行操作比如递增it是未定义行为。 第二个l.erase(it)这里使用了“后置递增”运算符它创建了it的一个副本然后将副本传递给erase方法。erase删除了当前迭代器指向的元素然后it被递增指向下一个元素。因为it在递增前已经复制给erase所以即使在删除当前元素后递增操作是在一个新的、未被修改的迭代器上进行的这保证了迭代器的有效性。或者可以这样写等价的it l.erase(it);erase函数返回下一个有效的迭代器然后将其赋值给it。这样it始终保持有效且指向当前元素的下一个元素。 三、结语 到此为止我们已经把list的基本使用方法学习结束了list的成员方法十分丰富这篇文章就是介绍了常用的让大家基本会使用目前你也可以用这种双向列表来实现一些复杂的算法我在下面了可以给大家写一个。等我有时间再出一篇模拟实现list的blog理解他的底层实现有缘再见朋友 实现的经典算法 约瑟夫环问题Josephus Problem。这个问题的一个版本可以描述如下N个人围成一圈从第一个人开始报数每报到M时该人被淘汰接着从下一个人开始继续报数直到所有人都被淘汰。任务是按顺序输出被淘汰人的编号。 #include iostream
#include list
using namespace std;void JosephusProblem(int N, int M) {// 初始化人员列表编号从1到Nlistint people;for (int i 1; i N; i) {people.push_back(i);}auto it people.begin(); // 迭代器指向第一个人while (!people.empty()) {// 模拟报数M-1次移动迭代器因为从当前人开始报数for (int count 1; count M; count) {it;// 如果迭代器超过了末尾重新从头开始if (it people.end()) {it people.begin();}}// 报到M移除当前人并输出编号cout *it ;it people.erase(it); // erase返回下一个元素的迭代器// 如果列表不为空但迭代器已经到达末尾需要重新指向开头if (it people.end() !people.empty()) {it people.begin();}}cout endl;
}int main() {int N 7; // 人数int M 3; // 报数淘汰JosephusProblem(N, M);return 0;
}
