客户网站 备案,网站和搜索引擎,响应式网站模板 食品,编程跟做网站目录
引言
forward_list与list
标准库中的list
一、list的常用接口
1.list的迭代器
2.list的初始化
3.list的容量操作
4.list的访问操作
5.list的修改操作
6.list的其他操作
二、list与vector的对比
结束语 引言
本篇博客要介绍的是STL中的list。
求点赞收藏评论…目录
引言
forward_list与list
标准库中的list
一、list的常用接口
1.list的迭代器
2.list的初始化
3.list的容量操作
4.list的访问操作
5.list的修改操作
6.list的其他操作
二、list与vector的对比
结束语 引言
本篇博客要介绍的是STL中的list。
求点赞收藏评论关注十分感谢
forward_list与list
首先我们先简单了解一下forward_list与list
forward_list与list都是C标准模板库STL中的容器它们提供了不同的链表实现适用于不同的场景。 forward_list 定义与结构 1.forward_list是C11引入的一种容器它提供了一种单向链表的数据结构。 2.它只维护一个指向下一个节点的指针因此内存使用相对高效。 特点 1.只能在单向遍历即只能从前往后遍历不能反向遍历。 2.在已知位置的情况下插入和删除操作非常高效时间复杂度为O(1)。 3.不支持通过索引访问元素只能使用迭代器进行访问。 适用场景 1.适用于需要频繁进行前向遍历和插入、删除操作的场景。 2.当内存使用要求较高且不需要双向遍历时forward_list是更好的选择。 list 定义与结构 1.list是C标准库中基于带头双向循环链表实现的容器。 2.它支持双向迭代器可以从前往后和从后往前遍历。 特点 1.在任何位置进行插入和删除操作的时间复杂度都是近似O(1)。 2.支持双向遍历迭代器使用更灵活。 3.与forward_list相比内存占用稍多因为每个节点需要维护两个指针一个指向前一个节点一个指向下一个节点。 适用场景 1.适用于需要双向遍历和更灵活操作的场景。 2.当需要在列表中间频繁插入或删除元素时list是更好的选择。 具体内容可以看看这两篇文章
数据结构——单链表
数据结构——双向链表
本文的重点是list。
标准库中的list
一、list的常用接口
list接口 1.list的迭代器
list的迭代器访问元素与我们之前学习的其他容器的迭代器访问一样。
int main()
{listint li { 1, 2, 3, 4, 5 };listint::iterator it li.begin();cout 顺序遍历;while (it ! li.end()){cout *it ;it;}cout endl;cout 逆序遍历;listint::reverse_iterator rit li.rbegin();while (rit ! li.rend()){cout *rit ;rit;}return 0;
}由于list的迭代器是双向迭代器支持和--操作因此可以在list中向前和向后遍历。
2.list的初始化 list的初始化与我们之前学习的其他容器的初始化一样我们直接看个简单的使用示例
int main()
{// 默认构造函数listint numbers1;cout 默认构造: ;for (const auto num : numbers1) {cout num ;}cout endl;// n个val构造listint numbers2(5, 5);cout n个val构造: ;for (const auto num : numbers2) {cout num ;}cout endl;int arr[] { 1, 2, 3, 4, 5 };// 通过vector的迭代器初始化listint numbers3(arr, arr sizeof(arr) / sizeof(arr[0]));cout 迭代器区间构造: ;for (const auto num : numbers3) {cout num ;}cout endl;listint numbers4 { 6, 7, 8, 9, 10 };// 拷贝构造listint numbers5(numbers4);cout 拷贝构造: ;for (const auto num : numbers5) {cout num ;}cout endl;numbers1 numbers2;// 赋值重载cout 赋值重载: ;for (const auto num : numbers1) {cout num ;}cout endl;return 0;
}
输出结果为 3.list的容量操作
函数名称功能size返回列表中元素的数量max_size返回列表可容纳的最大元素数量empty检查列表是否为空是则返回 true否则返回 falseresize重新设置列表中元素的数量超过原来数量则用默认值填充clear清空列表中的所有元素
这些函数也是很容易理解的我们还是直接看代码示例
int main()
{listint li { 1,2,3,4,5 };cout Size of list: li.size() endl;cout Max size of list: li.max_size() endl;if (li.empty()){cout empty endl;}else{cout not empty endl;}li.clear();if (li.empty()){cout empty endl;}else{cout not empty endl;}return 0;
}
输出结果为 与deque这一容器一样list也没有reserve这一接口。
int main()
{listint li { 1,2,3 };li.resize(5);for (auto num : li){cout num ;}cout endl;li.resize(2);for (auto num : li){cout num ;}return 0;
}
输出结果为 4.list的访问操作
函数名称功能back返回列表最后一个元素front返回列表第一个元素
由于list 是一个双向链表不支持高效的随机访问。在链表中访问某个元素需要从头节点开始顺序遍历直到找到目标元素。因此为 list 提供下标运算符或 at 方法并不合适。
访问操作的使用示例如下
int main()
{listint li { 1,2,3 };cout li.front() endl;cout li.back() endl;return 0;
}
输出结果为 5.list的修改操作
常用的修改操作有如下几个
函数名称功能push_back在列表尾部添加元素push_front在列表头部添加元素pop_back删除列表最后一个元素pop_front删除列表第一个元素insert在指定位置插入元素erase删除指定位置或区间的元素swap交换两个列表assign使用指定列表替换原列表
这些接口我们也是十分熟悉了我们直接看代码示例 尾删和尾插 int main()
{listint li;li.push_back(1);li.push_back(2);li.push_back(3);li.push_back(4);for (auto num : li) {cout num ;}cout endl;li.pop_back();for (auto num : li){cout num ;}cout endl;return 0;
} 输出结果为 头删和头插 int main()
{listint li;li.push_front(1);li.push_front(2);li.push_front(3);li.push_front(4);for (auto num : li){cout num ;}cout endl;li.pop_front();for (auto num : li){cout num ;}cout endl;return 0;
} 输出结果为 assign和swap int main()
{listint li1 { 1,1,1,1,1 };li1.assign(3, 3);for (auto num : li1){cout num ;}cout endl;listint li2 { 2,2,2,2,2 };li1.swap(li2);for (auto num : li1){cout num ;}cout endl;for (auto num : li2){cout num ;}return 0;
} 输出结果为 insert int main()
{listint li { 1,2,3,4,5 };listint::iterator it li.begin();it li.insert(it, 6);it li.insert(it, 7);for (auto num : li){cout num ;}return 0;
} 输出结果为 erase int main()
{listint li { 1,2,3,4,5 };listint::iterator it li.begin();it li.erase(it);for (auto num : li){cout num ;}return 0;
} 输出结果为 6.list的其他操作
接下来我们来学习list的其他操作
函数名称功能描述splice将元素从一个列表转移到另一个列表remove移除具有特定值的元素remove_if移除满足条件的元素unique移除重复的值sort对容器中的元素进行排序merge合并已排序的列表reverse反转元素的顺序 splice splice 是 list 提供的一个成员函数用于将一个列表list中的元素移动到另一个列表中而不需要进行元素复制或移动操作。 使用示例 int main()
{listint li1 { 1,2,3 };listint li2 { 4,5,6 };listint li3 { 7,8,9 };listint li4 { 0 };// 将 li2 的所有元素拼接到 li1 的末尾// li1 现在包含 {1, 2, 3, 4, 5, 6}// li2 现在为空 {}li1.splice(li1.end(), li2);for (auto num : li1){cout num ;}cout endl;// 获取 li3 的迭代器指向第一个元素7auto begin1 li3.begin();// 将迭代器向前移动一位指向第二个元素8begin1;// 将 li3 的第一个元素7移动到 li4 的末尾// li4 现在包含 {0, 7}// li3 现在包含 {8, 9}li4.splice(li4.end(), li3, li3.begin(), begin1);for (auto num : li4){cout num ;}return 0;
} 输出结果为 remove 用于从容器中移除所有等于指定值的元素。 与成员函数 erase 不同成员函数 erase 按元素的位置擦除元素使用迭代器此函数 按元素的值删除元素。 int main()
{listint li { 1,2,3,3,4,5 };li.remove(3);for (auto num : li){cout num ;}cout endl;return 0;
} 输出结果为 remove_if 用于从容器中移除满足特定条件的元素。 bool fun(int num)
{return num 3;
}int main()
{listint li { 1,2,3,3,4,5 };li.remove_if(fun);for (auto num : li){cout num ;}cout endl;return 0;
} 输出结果为 unique 用于移除容器中连续重复的元素。 int main()
{listint li { 1,2,3,3,4,5 };li.unique();for (auto num : li){cout num ;}return 0;
} 输出结果为 sort 用于对容器中的元素进行排序。 int main()
{listint li { 9,1,5,3,2,4,8,0,7,6 };li.sort();for (auto num : li){cout num ;}return 0;
} 输出结果为 merge 用于将两个已排序的范围合并成一个有序范围。 要求输入的两个范围必须是有序的通常是升序。它会将两个范围中的元素按顺序合并到目标范围中。目标范围必须有足够的空间来存储合并后的结果。 int main()
{listint li1 { 1,3,2,5,7 };listint li2 { 2,3,4,6,8 };li1.sort();li2.sort();li1.merge(li2);for (auto num : li1){cout num ;}return 0;
} 输出结果为 reverse
用于反转容器中元素的顺序。
int main()
{listint li { 9,1,5,3,2,4,8,0,7,6 };li.reverse();for (auto num : li){cout num ;}return 0;
}
输出结果为 二、list与vector的对比
vectorlist底层结构动态顺序表一段连续空间带头结点的双向循环链表随机访问支持随机访问访问某个元素效率O(1)不支持随机访问访问某个元素效率O(N)插入和删除任意位置插入和删除效率低需要搬移元素时间复杂度为O(N)插入时有可能需要增容增容:开辟新空间拷贝元素释放旧空间导致效率更低任意位置插入和删除效率高不需要搬移元素时间复杂度为0(1)空间利用率底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高底层节点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低迭代器原生态指针对原生态指针(节点指针)进行封装迭代器失效在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效插入元素不会导致选代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响使用场景需要高效存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随机访问
结束语
求点赞收藏评论关注
感谢各位大佬的支持
