广州找人做网站,网页制作网站设计稿,中国建设银行下载安装,nginx wordpress 固定链接文章目录 list基本概念定义结构双向迭代器优点缺点List和vector区别存储结构内存管理迭代器稳定性随机访问效率 list构造函数——创建list容器函数原型示例 list 赋值和交换函数原型 list 大小操作函数原型示例 list 插入和删除函数原型示例 list 数据存取函数原型注意示例 lis… 文章目录 list基本概念定义结构双向迭代器优点缺点List和vector区别存储结构内存管理迭代器稳定性随机访问效率 list构造函数——创建list容器函数原型示例 list 赋值和交换函数原型 list 大小操作函数原型示例 list 插入和删除函数原型示例 list 数据存取函数原型注意示例 list 反转和排序函数原型示例高级排序——在排序规则上再进行一次逻辑规则制定 list基本概念
定义
链表list是一种物理存储单元上非连续的存储结构可以将数据进行链式存储数据元素的逻辑顺序是通过链表中的指针链接实现的。STL中的链表是一个双向循环链表。
结构
链表的组成链表由一系列结点组。
结点的组成一个是存储数据元素的数据域另一个是存储下一个结点地址的指针域
双向迭代器
由于链表的存储方式并不是连续的内存空间因此链表list中的迭代器只支持前移和后移属于双向迭代器
优点
采用动态存储分配不会造成内存浪费和溢出链表执行插入和删除操作十分方便修改指针即可不需要移动大量元素
缺点
链表灵活但是空间(指针域) 和 时间遍历额外耗费较大 链表在每个节点都需要存储额外的指针域会消耗更多的内存空间。此外由于链表是非连续存储的访问特定位置的元素需要从头或尾按顺序遍历链表时间复杂度为O(n)相对于向量的常数时间访问O(1)效率较低。
List和vector区别
存储结构
list是一个双向链表每个节点包含一个值和前后指针 而vector是一个动态数组使用连续的内存块来存储元素。
内存管理
由于list使用动态内存分配可以在任意位置高效地插入和删除元素但同时会产生额外的指针开销 而vector使用连续的内存块尽管插入和删除操作需要移动元素但内存访问位置更加连续可以提供更好的缓存性能。
迭代器稳定性
在list中插入或删除元素不会影响已存在的迭代器的有效性 而在vector中当插入或删除元素时可能会导致迭代器失效需要重新获取。
随机访问效率
由于vector使用连续的内存块可以通过索引随机访问元素并具有较好的性能 而list为了访问指定位置的元素需要从头或从尾按顺序遍历链表效率较低。 在插入和删除频繁的场景下list可能更适合 而在需要快速随机访问元素或者容器规模较大的情况下vector可能更合适。 list构造函数——创建list容器
函数原型
listT lst; //list采用采用模板类实现,对象的默认构造形式list(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。list(n,elem); //构造函数将n个elem拷贝给本身。list(const list lst); //拷贝构造函数。 list构造方式同其他几个STL常用容器一致
示例
#include list
#include iostream
#include listint main() {// 示例1使用默认构造函数创建空的liststd::listint myList1;// 示例2使用迭代器构造函数将数组中的元素拷贝到list中int arr[] {1, 2, 3, 4, 5};std::listint myList2(arr, arr sizeof(arr) / sizeof(int));// 示例3使用元素数量和元素值构造liststd::listint myList3(3, 10); // 包含三个值为10的元素// 示例4使用拷贝构造函数创建一个副本std::listint myList4(myList3);// 输出list中的元素std::cout myList1: ;for (const auto element : myList1) {std::cout element ;}std::cout std::endl;std::cout myList2: ;for (const auto element : myList2) {std::cout element ;}std::cout std::endl;std::cout myList3: ;for (const auto element : myList3) {std::cout element ;}std::cout std::endl;std::cout myList4: ;for (const auto element : myList4) {std::cout element ;}std::cout std::endl;return 0;
}
输出 myList1: myList2: 1 2 3 4 5 myList3: 10 10 10 myList4: 10 10 10
list 赋值和交换
函数原型
assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。assign(n, elem); //将n个elem拷贝赋值给本身。list operator(const list lst); //重载等号操作符swap(lst); //将lst与本身的元素互换。
示例
#include iostream
#include listint main() {std::listint myList1 {1, 2, 3};std::listint myList2 {4, 5, 6};std::cout Before swap: std::endl;std::cout myList1: ;for (const auto element : myList1) {std::cout element ;}std::cout std::endl;std::cout myList2: ;for (const auto element : myList2) {std::cout element ;}std::cout std::endl;// 使用swap函数交换两个list的元素myList1.swap(myList2);std::cout After swap: std::endl;std::cout myList1: ;for (const auto element : myList1) {std::cout element ;}std::cout std::endl;std::cout myList2: ;for (const auto element : myList2) {std::cout element ;}std::cout std::endl;return 0;
}
输出 Before swap: myList1: 1 2 3 myList2: 4 5 6 After swap: myList1: 4 5 6 myList2: 1 2 3
list 大小操作
函数原型 size(); //返回容器中元素的个数 empty(); //判断容器是否为空 resize(num); //重新指定容器的长度为num若容器变长则以默认值0填充新位置。 //如果容器变短则末尾超出容器长度的元素被删除。 resize(num, elem); //重新指定容器的长度为num若容器变长则以elem值填充新位置。 //如果容器变短则末尾超出容器长度的元素被删除。
示例
#include iostream
#include listint main() {std::listint myList {1, 2, 3, 4, 5};// 使用size函数获取容器中元素的个数std::cout Size of myList: myList.size() std::endl;// 使用empty函数判断容器是否为空if (myList.empty()) {std::cout myList is empty. std::endl;} else {std::cout myList is not empty. std::endl;}// 使用resize函数改变容器的长度为7默认填充0myList.resize(7);std::cout myList after resize to size 7 with default value: std::endl;for (const auto element : myList) {std::cout element ;}std::cout std::endl;// 使用resize函数改变容器的长度为10使用值9填充新位置myList.resize(10, 9);std::cout myList after resize to size 10 with value 9: std::endl;for (const auto element : myList) {std::cout element ;}std::cout std::endl;// 使用resize函数将容器的长度改为3myList.resize(3);std::cout myList after resize to size 3: std::endl;for (const auto element : myList) {std::cout element ;}std::cout std::endl;return 0;
}
输出 Size of myList: 5 myList is not empty. myList after resize to size 7 with default value: 1 2 3 4 5 0 0 myList after resize to size 10 with value 9: 1 2 3 4 5 0 0 9 9 9 myList after resize to size 3: 1 2 3
在示例中我们创建了一个list对象myList并初始化它的元素。 然后我们使用size函数输出容器的大小使用empty函数判断容器是否为空。 接着我们使用resize函数将容器的大小分别改变为7、10和3。 当容器变大时新位置会用默认值0或指定的值9进行填充 当容器变小时末尾超出容器长度的元素会被删除。最终我们打印出修改后的容器内容
list 插入和删除
函数原型
push_back(elem);//在容器尾部加入一个元素pop_back();//删除容器中最后一个元素push_front(elem);//在容器开头插入一个元素pop_front();//从容器开头移除第一个元素insert(pos,elem);//在pos位置插elem元素的拷贝返回新数据的位置。insert(pos,n,elem);//在pos位置插入n个elem数据无返回值。insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据无返回值。clear();//移除容器的所有数据erase(beg,end);//删除[beg,end)区间的数据返回下一个数据的位置。erase(pos);//删除pos位置的数据返回下一个数据的位置。remove(elem);//删除容器中所有与elem值匹配的元素。
注意 插入多个数据无返回值删除返回下一个数据位置 beg end 均为迭代器
示例
#include iostream
#include listint main() {std::listint myList {1, 2, 3, 4, 5};std::cout Initial myList: std::endl;for (const auto element : myList) {std::cout element ;}std::cout std::endl;// 在容器尾部加入一个元素myList.push_back(6);// 删除容器中最后一个元素myList.pop_back();// 在容器开头插入一个元素myList.push_front(0);// 从容器开头移除第一个元素myList.pop_front();// 在指定位置插入元素的拷贝auto it myList.begin();std::advance(it, 2);myList.insert(it, 7);// 在指定位置插入多个相同元素it myList.begin();std::advance(it, 3);myList.insert(it, 3, 8);// 在指定位置插入另一个区间的元素std::listint newElements {9, 10};it myList.begin();std::advance(it, 4);myList.insert(it, newElements.begin(), newElements.end());std::cout myList after modifications: std::endl;for (const auto element : myList) {std::cout element ;}std::cout std::endl;// 移除容器的所有数据myList.clear();std::cout myList after clear: std::endl;if (myList.empty()) {std::cout myList is empty. std::endl;} else {std::cout myList is not empty. std::endl;}return 0;
}
list 数据存取
函数原型
front(); //返回第一个元素。back(); //返回最后一个元素。
注意
list容器的迭代器是双向迭代器不支持随机访问没有索引不能跳跃访问 也不可以通过[]或者at方式访问数据
示例
#include list//数据存取
void test01()
{listintL1;L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(40);//cout L1.at(0) endl;//错误 不支持at访问数据//cout L1[0] endl; //错误 不支持[]方式访问数据cout 第一个元素为 L1.front() endl;cout 最后一个元素为 L1.back() endl;//list容器的迭代器是双向迭代器不支持随机访问listint::iterator it L1.begin();//it it 1;//错误不可以跳跃访问即使是1
}int main() {test01();system(pause);return 0;
}
list 反转和排序
函数原型
reverse(); //反转链表sort(); //链表排序 //默认的排序规则 从小到大 升序
示例
#include iostream
#include listint main() {std::listint myList {5, 2, 4, 1, 3};// 反转链表myList.reverse();std::cout Reversed list: ;for (const auto element : myList) {std::cout element ;}std::cout std::endl;// 链表排序myList.sort();std::cout Sorted list: ;for (const auto element : myList) {std::cout element ;}std::cout std::endl;return 0;
}
输出 Reversed list: 3 1 4 2 5 Sorted list: 1 2 3 4 5
高级排序——在排序规则上再进行一次逻辑规则制定
对于自定义数据类型必须要指定排序规则否则编译器不知道如何进行排序高级排序只是在排序规则上再进行一次逻辑规则制定并不复杂
#include iostream
#include vector
#include algorithmstruct Student {std::string name;int age;int score;
};bool compareStudents(const Student student1, const Student student2) {// 先按分数降序排序if (student1.score ! student2.score) {return student1.score student2.score;}// 如果分数相同则按年龄升序排序if (student1.age ! student2.age) {return student1.age student2.age;}// 如果分数和年龄都相同则按姓名的字典序升序排序return student1.name student2.name;
}int main() {// 创建学生对象std::vectorStudent students {{Alice, 20, 90}, {Bob, 18, 85}, {Charlie, 19, 90}};// 使用自定义的排序规则对学生进行排序std::sort(students.begin(), students.end(), compareStudents);// 输出排序结果for (const auto student : students) {std::cout Name: student.name , Age: student.age , Score: student.score std::endl;}return 0;
}
首先我们定义了一个名为Student的结构体包含学生的姓名、年龄和分数。 接下来我们实现了一个名为compareStudents的自定义比较函数。 该函数根据学生的分数、年龄和姓名进行排序。 首先按照分数降序排序如果分数相同则按照年龄升序排序最后按照姓名的字典序升序排序。 在主函数中我们创建了一个存储学生对象的vector并初始化了几个学生对象。 然后我们使用std::sort函数对学生对象进行排序传入自定义的比较函数作为参数。 最后我们遍历排序后的学生对象并输出姓名、年龄和分数。
