list的底层结构就是 带头双向循环链表
构造函数
// 默认构造 list<int> lt; cout << "lt->"; for (auto it : lt) { cout << it << " "; } cout << endl; // 用n个val来进行初始化 list<int> lt1(10); cout << "lt1->"; for (auto it : lt1) { cout << it << " "; } cout << endl; list<int> lt2(10, 1); cout << "lt2->"; for (auto it : lt2) { cout << it << " "; } cout << endl; // 迭代器区间进行初始化 list<int> lt3(lt2.begin(), lt2.end()); cout << "lt3->"; for (auto it : lt3) { cout << it << " "; } cout << endl; // 拷贝构造 list<int>lt4 = lt3; cout << "lt4->"; for (auto it : lt4) { cout << it << " "; } cout << endl;
运行结果:
lt-> lt1->0 0 0 0 0 0 0 0 0 0 lt2->1 1 1 1 1 1 1 1 1 1 lt3->1 1 1 1 1 1 1 1 1 1 lt4->1 1 1 1 1 1 1 1 1 1
insert && 迭代器
看来list并没有 重载 + 运算符
但是重载了++
list<int> lt2(10, 1); cout << "lt2->"; for (auto it : lt2) { cout << it << " "; } cout << endl; cout << "插入->"; lt2.insert(lt2.begin()++, 10); for (auto it : lt2) { cout << it << " "; } cout << endl;
运行结果:
lt2->1 1 1 1 1 1 1 1 1 1 插入->10 1 1 1 1 1 1 1 1 1 1
如果, 我们想要在 第五个位置进行插入该怎么办?
list<int> lt2(10, 1); cout << "lt2->"; for (auto it : lt2) { cout << it << " "; } cout << endl; // 先找到下标为5的迭代器 auto it = lt2.begin(); for (int i = 0; i < 5; i++) { ++it; } list<int>::iterator c = lt2.insert(it, 50); cout << "插入->"; for (auto it : lt2) { cout << it << " "; } cout << endl; cout << "insert返回值的解引用->" << * c << endl;
运行结果:
lt2->1 1 1 1 1 1 1 1 1 1 插入->1 1 1 1 1 50 1 1 1 1 1 insert返回值的解引用->50
list迭代器遍历时，while循环的判断条件只能是!=，不能是<
list<int> lt2(10, 1); cout << "lt2->"; for (auto it : lt2) { cout << it << " "; } cout << endl; // 迭代器遍历 list<int>::iterator it = lt2.begin(); cout << "迭代器遍历->"; while (it != lt2.end()) { cout << *it << " "; ++it; } cout << endl;
运行结果:
lt2->1 1 1 1 1 1 1 1 1 1 迭代器遍历->1 1 1 1 1 1 1 1 1 1
push_back && pop_back && push_front && pop_front
list<int> lt2(5, 1); cout << "lt2->"; for (auto it : lt2) { cout << it << " "; } cout << endl; lt2.pop_back(); lt2.pop_back(); lt2.pop_back(); lt2.pop_back(); cout << "尾删->"; for (auto it : lt2) { cout << it << " "; } cout << endl; lt2.push_back(13); lt2.push_back(30); lt2.push_back(45); lt2.push_back(6); lt2.push_back(60); lt2.push_back(5); lt2.push_back(7); cout << "尾插->"; for (auto it : lt2) { cout << it << " "; } cout << endl; lt2.pop_front(); lt2.pop_front(); lt2.pop_front(); lt2.pop_front(); lt2.pop_front(); cout << "头删->"; for (auto it : lt2) { cout << it << " "; } cout << endl; lt2.push_front(25); lt2.push_front(55); lt2.push_front(9); lt2.push_front(6); lt2.push_front(20); cout << "头插->"; for (auto it : lt2) { cout << it << " "; } cout << endl;
运行结果:
lt2->1 1 1 1 1 尾删->1 尾插->1 13 30 45 6 60 5 7 头删->60 5 7 头插->20 6 9 55 25 60 5 7
erase
// 删除lt2中的所有奇数 auto it = lt2.begin(); while (it != lt2.end()) { if ((*it) % 2 == 1) { // erase返回删除后的下一个节点的地址 -- 更新了it it = lt2.erase(it); } else { // 不是奇数, 那就++ it++; } } cout << "删除所有奇数->"; for (auto it : lt2) { cout << it << " "; } cout << endl;
运行结果:
lt2->1 1 1 1 1 1 13 30 45 6 删除所有奇数->30 6
但是我们需要注意: erase的形参是不能再使用的, 切记!切记!
sort && find && reverse
当我们调用 算法库中的sort:
🗨️这是怎么一回事?
其实, 迭代器可以按照性质(有底层结构决定)来进行划分:
单向迭代器 – – 可以进行 ++
比如: forward_list/ unordered_map/ unordered_set
双向迭代器 – – 可以进行 ++/ –
比如: list/ map/ set
随机迭代器 – – 可以进行+/ - / ++/ –
比如: vector/ deque/ string
但是std::sort的迭代器使用的是 随机迭代器类型 ⇒ 故 list不能使用算法库中的sort算法
但list类中自带sort算法👇👇👇
//sort(lt2.begin(), lt2.end()); lt2.sort(); cout << "升序->"; for (auto e : lt2) { cout << e << " "; } cout << endl; lt2.sort(greater<int>()); cout << "降序->"; for (auto e : lt2) { cout << e << " "; } cout << endl;
运行结果:
升序->1 5 6 7 13 30 45 60 降序->60 45 30 13 7 6 5 1
温馨提示:
list自带的排序很慢的, 小数据量(<10万)的可以用用, 但大数据量还不如 将数据拷贝到vector中, vector排好序之后, 再将结果拷贝回去快 ⇒ 使用好 对应的容器, 对效率来说很重要的
find函数list并没有, 但是可以用算法库中的
list函数自带reverse函数, 但其实还不如用库里的
