C++----STL(list)

介绍

list的数据结果是一个带头双向链表。

使用

有了前面string、vector的基础，后续关于list使用的讲解主要提及与string和vector的不同之处。

使用文档：cplusplus.com/reference/list/list/?kw=list

迭代器问题

insert以后迭代器不失效

#include <iostream>
#include <list>
#include <vector>
using namespace std;int main() {list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(10);lt.push_front(20);//在元素3的位置上插入30auto it = find(lt.begin(), lt.end(), 3);if (it != lt.end()){lt.insert(it, 30);// insert以后，it不失效*it *= 100;}return 0;
}

erase以后迭代器会失效

#define _CRT_SECURE_NO_EARNINGS 1
#include <iostream>
#include <list>
#include <vector>
using namespace std;int main() {list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(10);lt.push_front(20);//在元素3的位置上插入30auto it = find(lt.begin(), lt.end(), 3);if (it != lt.end()){lt.insert(it, 30);// insert以后，it不失效*it *= 100;}it = find(lt.begin(), lt.end(), 2);if (it != lt.end()){lt.erase(it);//erase以后，it失效了//*it *= 100;//error}return 0;
}

容器和迭代器类型

不同的容器在C++标准模板库（STL）中有不同的底层结构和迭代器类型。这些迭代器类型决定了容器支持哪些算法操作：

• 单向迭代器：forward_list、unordered_map、unordered_set 这些容器仅支持向前遍历（即仅支持++操作）。
• 双向迭代器：list、map、set 这些容器支持向前和向后遍历（即支持++和--操作）。
• 随机访问迭代器：vector、string、deque 这些容器支持高效的随机访问（即支持++，--，+，-，以及比较操作）。

我们再通过vector和list的insert、erase来理解一下上面的讲解：

insert:

#include <iostream>
#include <list>
#include <vector>
using namespace std;int main() {list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(10);lt.push_front(20);vector<int> v = { 1,2,3,4,5 };//vector在第5个位置插入数据v.insert(v.begin() + 5, 100);//list在第5个位置插入数据//lt.insert(lt.begin() + 5, 100);//错误做法auto it = lt.begin();for (size_t i = 0; i < 5; i++){++it;}lt.insert(it, 100);return 0;
}

erase:

#include <iostream>
#include <list>
#include <vector>
using namespace std;int main() {list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(10);lt.push_front(20);vector<int> v = { 1,2,3,4,5 };//vector删除第5个元素v.erase(v.begin() + 5);//list删除第5个元素//lt.erase(begin() + 5);//错误做法it = lt.begin();for (size_t i = 0; i < 5; i++) {++it;}lt.erase(it);return 0;
}

排序

sort

如果需要对一组数据sort排序，建议使用vector进行sort排序，而不要使用list，因为在数据量很大的情况下vector排序的效率远高于list。我们通过一个代码来验证一下：

void test_op()
{srand(time(0));const int N = 1000000;vector<int> v;v.reserve(N);list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){auto e = rand();lt2.push_back(e);lt1.push_back(e);}// 拷贝到vector排序，排完以后再拷贝回来int begin1 = clock();// 先拷贝到vectorfor (auto e : lt1){v.push_back(e);}// 排序sort(v.begin(), v.end());// 拷贝回去size_t i = 0;for (auto& e : lt1){e = v[i++];}int end1 = clock();int begin2 = clock();lt2.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}

merge：合并排序

#include <iostream>
#include <list>
#include<algorithm>
using namespace std;void print(list<int> lt) {cout << "lt: ";for (auto e : lt) {cout << e << " ";}cout << endl;
}void test_merge(int a1[], int a2[],int len1,int len2) {sort(a1, a1 + len1);sort(a2, a2 + len2);list<int> lt(10);merge(a1, a1 + len1, a2, a2 + len2, lt.begin());print(lt);
}int main() {int first[] = { 5,10,15,20,25 };int second[] = { 50,40,30,20,10 };int len1 = sizeof(first) / sizeof(first[0]);int len2 = sizeof(second) / sizeof(second[0]);test_merge(first, second, len1, len2);return 0;
}

其他算法

unique:去重

#include <iostream>
#include <list>
#include<algorithm>
using namespace std;int main() {// 创建一个包含重复元素的 listlist<int> myList = { 1, 7, 2, 3, 4, 4, 4, 5, 6, 6 };// 注意：std::unique 需要已排序的容器myList.sort(); // 先排序auto lastUnique = unique(myList.begin(), myList.end());// 擦除重复的元素myList.erase(lastUnique, myList.end());// 打印去重后的 listfor (auto e : myList) {cout << e << ' ';}cout << endl;return 0;
}

remove:删除指定元素

int main() {list<int> mylist = { 9,89,23,67 };mylist.remove(89);for (auto e : mylist){cout << e << " ";}cout << endl;return 0;
}

splice:把一个链表的内容转移到另一个链表上

//splice(iterator pos, list& other)
//将整个源列表other的所有元素移动到目标列表的pos位置之前。源列表将变为空。
void test_splice1(list<int> mylist1,list<int> mylist2) {auto it = mylist1.begin();++it;                         // points to 2//mylist2全部转移到mylist1的第二个位置之前mylist1.splice(it, mylist2);cout << "spliced mulist1: ";for (auto e : mylist1){cout << e << " ";}cout << endl;
}//splice(iterator pos, list& other, iterator first)
//将源列表other中将 first 指向的元素移动到目标列表的pos位置之前。源列表中 first 元素将被移除。
void test_splice2(list<int> mylist1, list<int> mylist2) {auto it = mylist1.begin();++it;                         // points to 2// 部分转移// mylist2的++mylist2.begin()的元素转移到mylist1的第二个位置之前mylist1.splice(it, mylist2, ++mylist2.begin());cout << "spliced mulist1: ";for (auto e : mylist1){cout << e << " ";}cout << endl;
}//splice(iterator pos, list& other, iterator first, iterator last)
//将源列表other中从 first 到 last（不包括 last）之间的所有元素移动到目标列表的pos位置之前。源列表other中这部分元素将被移除
void test_splice3(list<int> mylist1, list<int> mylist2) {auto it = mylist1.begin();++it;                         // points to 2// mylist2的++mylist2.begin()之后的元素转移到mylist1的第二个位置之前mylist1.splice(it, mylist2, ++mylist2.begin(), mylist2.end());cout << "spliced mulist1: ";for (auto e : mylist1){cout << e << " ";}cout << endl;
}
int main() {list<int> mylist1, mylist2;list<int>::iterator it;// set some initial values:for (int i = 1; i <= 4; ++i)mylist1.push_back(i);      // mylist1: 1 2 3 4for (int i = 1; i <= 3; ++i)mylist2.push_back(i * 10);   // mylist2: 10 20 30test_splice1(mylist1,mylist2);test_splice2(mylist1,mylist2);test_splice3(mylist1,mylist2);return 0;
}