前言核心内容迭代器失效白话详解、unordered无序容器、STL三大容器适配器stack/queue/priority_queue所有知识点配套对应可运行代码适合期末复习、面试背诵。一、迭代器失效最简白话理解1.1 迭代器失效核心定义个人手写总结迭代器本质就是容器元素的书签/指针用来定位元素。迭代器失效两种情况逻辑失效内存地址没变但当前位置的元素被删除/修改原来的元素找不到了物理失效容器扩容数据整体迁移到新内存旧迭代器地址彻底作废判定标准只要迭代器指向的位置不再是当初绑定的元素直接判定失效。1.2 各类容器迭代器失效规则1、连续内存容器vector / string / deque以下操作会让所有旧迭代器全部失效push_back、emplace_back、insert、erase、resize、clear、容器扩容原因连续内存增删元素会导致整体元素移动、内存重分配书签全部错位。2、链式/树状容器list / map / setinsert 插入元素所有迭代器保持有效只改节点指向不移动元素erase 删除元素仅被删除元素的迭代器失效其余迭代器正常使用二、STL 无序关联容器2.1 有序容器与无序容器核心区别map / set / multimap / multiset底层红黑树自动排序增删改查 O(logN)unordered_map / unordered_set底层哈希表bucket桶链表哈希函数元素无序平均增删改查 O(1)2.2 unordered_set 无序去重容器核心特性元素无序、不可重复底层哈希表存储bucket扩容时自动重新哈希所有元素遍历删除元素极易触发迭代器失效需要先记录、后删除对应实战代码#include iostream #include unordered_set #include vector using namespace std; int main() { // 无序存储、自动去重 unordered_setfloat scores({ 21, 33, 45, 22, 99,85 }); cout scores.size() endl; // 新增元素 scores.emplace(90); scores.insert({ 28, 56, 77 }); cout scores.size() endl; // 删除不存在元素无效果 scores.erase(20); cout scores.size() endl; cout scores.count(20) endl; // 遍历删除规避迭代器失效 -- 先记录后删除 auto it scores.begin(); vectorfloat delItems; delItems.reserve(scores.size()); while (it ! scores.end()) { if (*it 60) { delItems.push_back(*it); } else { cout *it ; } it; } cout endl; // 统一删除不及格元素 for (int i 0; i delItems.size(); i) { scores.erase(delItems[i]); } cout scores.size() endl; // 元素查找 auto ret scores.find(99); if (ret ! scores.end()) { cout*ret 已查到endl; } else { cout未查找到 endl; } return 0; }2.3 unordered_multiset 无序可重复容器核心特性元素无序、允许重复重复元素存储在哈希表同一个桶的链表中count() 可以统计相同元素的个数对应实战代码#includeiostream #includeunordered_set using namespace std; int main() { // 元素可以重复存储 unordered_multisetint s({ 5,2,1,3,4,5,8,2,3 }); // 遍历所有元素 auto it s.begin(); while (it ! s.end()) { cout *it ; it; } cout endl; // 统计重复元素个数 cout s.count(3) endl; return 0; }三、STL 容器适配器重点3.1 容器适配器基础概念容器适配器不是独立容器是对已有容器的功能封装屏蔽原有接口实现专属数据结构特性。三大适配器底层默认容器stack 栈默认 deque支持 vector/list/deque特性后进先出 LIFOqueue 队列默认 deque支持 vector/list/deque特性先进先出 FIFOpriority_queue 优先队列默认 vector支持 vector/deque特性自动排序、大顶堆优先弹出3.2 stack 栈适配器1、手写模拟栈适配器底层deque#includeiostream #includedeque using namespace std; // 手动实现栈适配器 templateclass T class StackAdapter { private: dequeT q; int len; public: StackAdapter() { q.resize(20); len 0; } size_t size() { return len; } bool empty() { return len 0; } void push(T item) { q.push_back(item); len; } void pop() { if (!q.empty()) { q.pop_back(); len--; } } T top() { if(!q.empty()) return q.back(); return T(); } }; int main() { StackAdapterint s; s.push(20); s.push(50); s.push(10); size_t len s.size(); for (int i 0; i len; i) { cout s.top() endl; s.pop(); } couts.empty()endl; return 0; }2、STL 原生 stack 使用#include stack #includeiostream using namespace std; int main() { // 显式指定底层容器deque stackint, dequeint s; s.push(21); s.push(22); s.push(23); cout s.top() endl; s.pop(); // 底层调用 pop_back() cout s.top() endl; return 0; }3.3 queue 队列适配器默认底层 deque先进先出 FIFO队尾入队、队首出队。#include queue #includeiostream using namespace std; int main() { queue int q; q.push(21); q.push(22); q.push(23); cout 第一个元素是 q.front() endl; cout 最后一个元素是 q.back() endl; q.pop(); // 底层调用 pop_front() cout q.size() endl; cout 第一个元素是 q.front() endl; cout 最后一个元素是 q.back() endl; return 0; }3.4 priority_queue 优先队列大顶堆核心底层笔记默认底层 vector内部默认less比较大顶堆排序。关键特点优先队列不会修改底层vector无序数据只是通过堆算法筛选最值top()拿到的最大值不一定是vector第一个元素。每次 push/pop 自动重新建堆排序。1、基础使用代码#include queue #includeiostream using namespace std; int main() { priority_queueint, dequeint q; q.push(51); q.push(100); q.push(88); q.push(21); cout 第一个处理的元素: q.top() endl; q.push(99); q.pop(); cout 第一个处理的元素: q.top() endl; return 0; }2、实战自定义任务优先级队列需求任务 level 值越小优先级越高取出前3个最高优先级任务#includeiostream #includequeue #includefunctional #includestring using namespace std; class Task { int tid; string name; int level; public: Task(int tid, string name, int level) : tid(tid), name(name), level(level) {} friend ostream operator(ostream cout, const Task t) { cout id: t.tid , name: t.name , level: t.level; return cout; } bool operator(const Task t) const { return levelt.level; } bool operator(const Task t) const { return level t.level; } }; int main() { // 小顶堆level越小优先级越高 priority_queueTask,vectorTask,greaterTask q; q.push(Task(1, task1, 1)); q.push(Task(2, task2, 8)); q.push(Task(3, task3, 3)); q.push(Task(4, task4, 2)); // 取出优先级最高前3个任务 for (int i 0; i 3; i) { cout q.top() endl; q.pop(); } return 0; }四、核心总结迭代器失效连续容器增删扩容全失效链表、树结构容器仅删除迭代器失效无序容器unordered_set 去重无序unordered_multiset 可重复无序底层哈希表 O(1)容器适配器无独立内存基于普通容器封装专属功能stack后进先出queue先进先出priority_queue默认大顶堆不修改底层容器数据仅动态筛选最值自定义优先队列重载大小比较运算符配合 greater/less 仿函数实现自定义优先级