C++STL之list的利用详解

一、简介

1、底层：list为双向链表，即struct中包含一个数据和两个指针，分别指向前一个节点和后一个节点，在堆上分配空间，每插入一个元数都会分配空间，每删除一个元素都会释放空间
2、性能
① 访问：随机访问性能很差，只能快速访问头尾节点
② 插入：很快，一般是常数开销
③ 删除：很快，一般是常数开销
3、适用场景：list 拥有一段不连续的内存空间，假如必要高效的插入和删除，而不关心随机访问，则应利用 list
二、list的基本操作

1、初始化

1. #include<iostream>
2. #include<map>
3. #include<string>
4. #include<list>
5. using namespace std;
6. int main()
7. {
8.     std::list<int> my_list; // 构造空链表
9.     my_list.push_back(1); // 尾部插入数据1
10.     my_list.push_back(2); // 尾部插入数据2
11.     my_list.push_back(3); // 尾部插入数据3
13.     std::list<int> my_list1(3, 5); // 构造3个5的链表
15.     std::list<int> my_list2(my_list1.begin(), my_list1.end()); // 拷贝构造
16. }

复制代码

2、插入数据

① push_front() 头部插入元素

push_front()函数用于将一个新的元素插入到链表的开头位置, 时间复杂度为O(1)。在双向链表中插入元素到开头位置的操作只涉及指针的重新链接，不必要移动其他元素

1. my_list.push_front(0); // 头插数据0

复制代码

② push_back() 尾部插入元素

push_back()函数用于将一个新的元素插入到链表尾部, 时间复杂度为O(1)

1. my_list.push_back(4);

复制代码

③ insert() 插入元素

insert()函数在 position 位置中插入值为val的元素。
插入单个数据。第一个参数为迭代器，即插入的位置，第二个参数是插入的数据。

1. // 尾部插入元素5
2. my_list.insert(my_list.end(), 5);

复制代码

插入多个类似数据。第一个参数为迭代器，即插入的位置，第二个参数是插入的数据个数，第三个参数是插入的数据。

1. // 在尾部插入2个6
2. my_list.insert(my_list.end(), 2, 6);

复制代码

插入多个数据。第一个参数为迭代器，即插入的位置，第二个参数是迭代器，必要插入元素初始位置，第三个参数是迭代器，必要插入元素的竣事位置

1. /* 在my_list尾部插入3个5 */
2. std::list<int> my_list1(3, 5); // 构造3个5的链表
3. my_list.insert(my_list.end(), my_list1.begin(), my_list1.end());

复制代码

3、删除数据

① pop_front() 头删元素

pop_front()函数用于删除链表中的第一个元素，时间复杂度为O(1)

1. my_list.pop_front();

复制代码

② pop_back() 尾删元素

1. my_list.pop_back();

复制代码

③ erase()删除数据

erase()函数用于删除链表中数据, 返回值是当前删除元素位置的下一个迭代器。
删除单个元素，参数为迭代器。

1. list<int>::iterator pos = my_list.begin(); // 第一个元素为0
2. if (pos != my_list.end())
3. {
4.     auto it = my_list.erase(pos);
5.     std::cout << "next: " << *it << std::endl; // 当前第一个元素为1
6. }

复制代码

删除多个元素，两个参数均为迭代器，分别为初始位置和竣事位置。

1. my_list.erase(my_list.begin(), my_list.end());

复制代码

④ clear() 删除全部数据

1. my_list.clear();

复制代码

⑤ remove() 删除元素

从list中删除元素，remove(val) 删除全部为val的元素
4、修改数据

① assign() 替换/赋值

assign(n,val); 
将当前列表中全部元素替换为n个T范例的val

1. my_list.assign(6, 1);

复制代码

assign(l2.begin(),l2.end());
将12列表中的从l2.begin()到l2.end()之间的数值赋值给当前列表l1

1. my_list.assign(my_list1.begin(), my_list1.end());

复制代码

② swap() 交换

交换两个链表数据，两种用法均可。

1. my_list.swap(my_list1);

复制代码

1. swap(my_list, my_list1);

复制代码

③ reverse() 反转

反转链表中数据。

1. my_list.reverse();

复制代码

④ merge() 合并

l1.merge(l2); 默认升序
l1.merge(l2，greater<int>()); 升序排序
l1.merge(l2，less<int>()); 降序排序
合并两个链表。调用竣事后l2变为空，l1中元素包含原来l1 和 l2中的元素，而且排好序，升序

1. my_list.merge(my_list1);

复制代码

⑤ resize() 

调用resize(n)将list的长度改为只容纳n个元素，超出的元素将被删除。假如n比list原来的长度长，那么默认超出的部分元素置为0。

1. my_list.resize(2); // 大小修改为2个元素，多的元素删除

复制代码

也可以用resize(n, m)的方式将超出的部分赋值为m。

1. my_list.resize(10, 0); // 大小修改为10个元素，多的赋值为0

复制代码

5、查找数据

① front() 获取头部元素

1. my_list.front();

复制代码

② back() 获取尾部元素

1. my_list.back();

复制代码

③ 迭代器

1. for (auto const& v : my_list)
2. {
3.     std::cout << "v:" << v << std::endl;
4. }

复制代码

6、其他用法

① sort() 排序

sort函数用于排序，默认升序

1. my_list.sort();

复制代码

② size() 获取大小

1. int size = my_list.size();

复制代码

③ unique() 去重

去重就是对该链表对象举行遍历，将元素值类似的多个元素举行删除，只保留唯一一个值节点

1. my_list.unique();

复制代码

ok，今天分享就到这里了。
假如以为分享对你有所帮助的话，记得点赞

哦！
主页另有其他相关文章，接待一起学习，一起进步~

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告