【C++:STL库简介/顺序容器/关联容器】

目录一、STL概述1 什么是STL?由六大部分组成二、顺序容器1.vector容器a.定义b.头文件引入c.语法d.vector迭代器cbegin()e.常用方法添加元素insert vs emplace删除元素访问元素容量相关扩容是整个vector的核心reservereserve vs resize 对比f.Sort排序只能对vector,deque2.deque双端队列a.什么是dequeb.核心特性3.list列表a.简介b.元素访问c.迭代器d.插入/删除e.list特有算法三、关联容器set(关联容器)map(关联容器)什么是 map键类型的限制自定义比较器map vs unordered_map常用操作应用统计数组元素出现次数差分数组区间累加思路文字步骤四、范围for循环一、STL概述1 什么是STL?Standard Template Library 标准模板库提供了一套通用的数据结构和算法模板。由六大部分组成容器各种数据结构如vector,list,deque,set,map等用来存放数据迭代器Iterator用于访问容器中成员的方式本质是元素的位置指针每个容器都有自己的迭代器一般分为两种const和非const也是所谓的“泛型”指针将operator* - --等指针相关的操作予以重载的类模板适配器Adapter在容器的基本之上封装统一的接口函数仿函数Function用于容器的操作算法的方式条件、回传元素等是一种重载operator的类或者类模板C11使用lambda表达式算法Algorithm各类容器的操作函数sort,search,copy等等配置器Allocator用于管理容器的大小, 每个容器都有自己的配置器内存分配器。二、顺序容器能实现按顺序访问的数据结构元素的位置由插入顺序决定容器说明C 标准array固定大小数组C11vector动态数组C98deque双端队列C98list双向链表C98forward_list单向链表C11inplace_vector原地向量固定容量C261.vector容器a.定义Vector是动态数组容器它的数据元素占用的的是连续的存储空间存储空间大小可以动态变化容器会自动扩容支持随机访问O(1在尾部插入和删除元素效率高。注意中间插入/删除效率低O(n)需要移动元素在容器里面存放的时候存对象类类型的话尽量去存对象的指针类型要不然扩容的时候很麻烦和STL打交道经常使用共享型智能指针容器间可以安全共享复制开销可控多个容器共享数据函数间安全传递函数传递shared_ptr时只是临时借用函数结束后会自动减少引用计数但不会销毁对象b.头文件引入#include vector using namespace std;c.语法// 1. 定义空vector vectorint v1; ​ // 2. 定义包含5个元素的vector默认值为0 vectorint v2(5); ​ // 3. 定义包含5个元素每个元素值为10 vectorint v3(5, 10); ​ // 4. 使用列表初始化 vectorint v4 {1, 2, 3, 4, 5}; vectorint ids({ 2,5,8,1,0,4 }); ​ // 5. 拷贝构造,用已有的创建新的 vectorint v5(v4); ​ // 6. 使用迭代器范围构造 vectorint v6(v4.begin(), v4.end()); ​ // 7. 将数组转成容器vector int arr[3]{ 4,3,6 }; vectorint ns(arr, arr 3);告诉你当前容器存储的类型容器可以存储对象和指针但不能存储引用注意里面不能出现抽象类型无类型void但是抽象类型不能定义对象但是它可以定义指针Object*就可以了class Object { public: virtual void func() 0; }; int main() { //std::vectorvoidvect; 错误 //std::vectorObjectoect; 错误 ​ std::vectorvoid*vect; std::vectorObject*oect; int ar[10]; int* par[10];//定义一个指针数组包含 10 个 int* 类型指针 //int rar[10];//无法编译通过,意思是存放10个引用在数组里面引用不是对象不能被存储在数组里面 int(rar)[10]ar;//数组的引用---可以 int*(rpar)[10]par;//指针数组的引用---可以 ​ } //vector 需要开辟空间传入指针就可以确定开辟空间大小 //传入指针类型是可以编译通过的总结在容器里面可以拿指针作为容器处理的类型不能拿引用作为容器处理的类型class Student { private: string name; int age; int sid; public: Student() {}; }; int main() { std::vectorint*ivec;//还可以存储指针类型 std::vectordouble*dvec; std::vectorchar*cvec; ​ std::vectorStudentsvec; std::vectorStudent*svec; }d.vector迭代器vector的迭代器遍历元素(迭代器的本质就是元素指针)它的内部重载了operator*、operator、operator--等操作。vectorint::iterator it ids.begin();//定义了一个迭代器变量并初始化为指向 ids 容器的第一个元素。 while (it ! ids.end()) { //修改当前位置元素内容 *it 10; cout *it ; it;//vector迭代器可以自增自减 }vectorint ids2(ids.begin()3,ids.end()); ids容器: ┌────┬────┬────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ 50 │ 60 │ 70 │ └────┴────┴────┴────┴────┴────┴────┘ ↑ ↑ ids.begin() ids.begin()3 ids.end() (指向40) (指向末尾) ​ ids.begin()3 返回迭代器 ────┐ ids.end() 返回迭代器 ────┼──→ 作为参数传给构造函数 ↓ ┌─────────────────┐ │ vectorint ids2 │ ← 这是新创建的容器 └─────────────────┘ ↓ ┌────┬────┬────┬────┐ │ 40 │ 50 │ 60 │ 70 │ └────┴────┴────┴────┘ //下标访问的方式遍历容器 for (int i 0; i ids2.size(); i) { cout ids2[i] ; } cout endl;rbegin,rend是逆向迭代器cbegin()你可以用它遍历、读取数据但不能修改容器里的元素//定义一个只读迭代器指向容器的第一个元素 vectorint::const_iterator it2 ids.cbegin(); // const 迭代器 //auto it2 ids.cbegin(); it2; cout *it2 endl;e.常用方法添加元素vectorint v; ​ // 尾部插入元素 v.push_back(10); // v: [10] ​ // 在指定位置插入元素迭代器位置前 v.insert(v.begin(), 5); // v: [5, 10] ​ // 插入多个相同元素 v.insert(v.begin(), 3, 1); // v: [1, 1, 1, 5, 10] ​ // emplace 直接构造更高效 v.emplace(v.begin(), 99); // 直接传构造参数 ​ //都可以在指定位置插入元素 ids2.emplace(ids2.begin(),99); ids2.insert(ids2.begin(), 88);insertvsemplace复杂的对象建议使用emplace进行插入emplace是直接传入构造的参数。insert需要先构造对象再进行插入// insert需要先构造对象 string s hello; vs.insert(vs.begin(), s); ​ // emplace直接传构造参数 points.emplace(points.begin(), 1, 2); // Point{1,2}删除元素vectorint v {1, 2, 3, 4, 5}; ​ v.pop_back(); // v: [1,2,3,4] v.erase(v.begin()); // v: [2,3,4] v.erase(v.begin(), v.begin()2); // v: [4]删除区间 [first,last) v.clear(); // v: []清空访问元素vector的访问形式data:直接访问底层存储数组的指针data()的作用返回你连续空间的首地址vectorint v {10, 20, 30, 40, 50}; ​ int* ptr v.data(); // 返回指向底层数组的指针 ​ // 可以像数组一样使用 cout ptr[0] endl; // 10 cout ptr[2] endl; // 30 ​ // 也可以修改 ptr[1] 99; // v 变为 {10, 99, 30, 40, 50}at()vsoperator[]对比特性ar.at(i)ar[i]边界检查检查越界抛异常不检查性能稍慢有检查开销更快无检查安全性安全不安全越界未定义行为返回值引用可读写引用可读写适用场景不确定索引是否有效确定索引一定有效重载下标[]越界会直接断言at越界会抛出异常vectorint v {10, 20, 30, 40}; ​ // 使用下标访问不检查边界 cout v[0]; // 10 ​ // 使用at方法访问检查边界越界抛出异常 cout v.at(1); // 20 ​ // 获取第一个元素 cout v.front(); // 10 ​ // 获取最后一个元素 cout v.back(); // 40容量相关扩容是整个vector的核心reservevectorint v {1, 2, 3}; ​ // 获取元素个数 cout v.size(); // 3 ​ // 获取当前容量 cout v.capacity(); // 通常大于等于size ​ // 判断是否为空 cout v.empty(); // false ​ // 改变大小 v.resize(5); // v: [1, 2, 3, 0, 0] v.resize(2); // v: [1, 2] ​ // 预留空间 v.reserve(100); // 预分配100个元素的空间reservevsresize对比操作reserve(n)resize(n)作用预留内存空间改变元素个数size 变化❌ 不变✅ 改变capacity 变化✅ 可能增加✅ 可能增加是否构造元素❌ 不构造✅ 构造/销毁元素访问新位置❌ 不能访问✅ 可以访问f.Sort排序只能对vector,deque默认是升序排序底层用快速排序实现// 降序排序 sort(v.begin(), v.end(), greaterint());2.deque双端队列a.什么是dequeb.核心特性支持两端高效插入/删除时间复杂度O1#include deque ​ dequeint dq; ​ // 两端插入/删除O(1) dq.push_front(1); dq.push_back(2); dq.pop_front(); dq.pop_back(); ​ // 支持随机访问 cout dq[0]; // O(1) cout dq.at(1); // 带边界检查 ​ // 与 vector 相同的迭代器操作 for (auto it dq.begin(); it ! dq.end(); it) { cout *it ; }deque是在功能上合并了vector和list。优点随机访问含方便支持[]和at()访问可以在两端进行插入删除在内部方便的进行插入和删除操作3.list列表a.简介是序列容器允许在任何位置进行插入/删除操作速度极快O1不支持下标访问只能进行逐个遍历使用双向链表实现迭代器在插入/删除后不失效除非被删除b.元素访问#include list ​ listint l {1, 2, 3, 4, 5}; ​ // 访问首尾 cout l.front(); // 1 cout l.back(); // 5 ​ // 两端插入/删除 l.push_front(0); // {0,1,2,3,4,5} l.push_back(6); // {0,1,2,3,4,5,6} l.pop_front(); l.pop_back();对于list来说每一个节点都是malloc动态开辟的节点一节点之间不连续所以不能下标访问c.迭代器list迭代器迭代的是每个节点里面的数据可以用范围for进行迭代// 迭代器遍历 for (auto it l.begin(); it ! l.end(); it) { cout *it ; } ​ // 范围 for for (int x : l) { cout x ; }d.插入/删除listint l {10, 20, 30, 40}; ​ auto it l.begin(); it; // 指向 20 ​ l.insert(it, 15); // {10,15,20,30,40} l.erase(it); // 删除 20注意 it 已失效 ​ // 直接删除元素 l.remove(30); // 删除所有值为 30 的元素 l.remove_if([](int x) { // 条件删除 return x 20; }); ​ // 去重 l.unique(); // 删除相邻重复元素e.list特有算法方法说明复杂度sort()排序使用归并排序O(n log n)merge()合并两个有序链表O(n)splice()转移节点不拷贝O(1)reverse()反转O(n)unique()去重O(n)直接删除元素remove,remove_if三、关联容器set(关联容器)关联容器通过键来访问元素它的核心特性就是自动去重和自动排序默认升序排列从小到大不支持下标访问底层结构红黑树平衡二叉搜索树查找效率O(log n)插入效率O(log n)头文件set使用multiset不去重对比特性setunordered_set底层结构红黑树链式哈希去重✅ 自动✅ 自动排序✅ 自动排序❌ 不排序查找复杂度O(log n)O(1) 平均插入复杂度O(log n)O(1) 平均内存占用较小较大头文件setunordered_set只需要去重不需要排序 → 用 unordered_set更快无序set链式哈希底层是一个桶数组里面存放指针指向链表链表里面存放的是值unordered_setint s {10, 20, 30, 40, 50};底层结构 ┌─────────────────────────────────────────┐ │ 桶数组 (Bucket Array) │ │ [0] → nullptr │ │ [1] → nullptr │ │ [2] → [10] → [20] → [30] │ ← 链表 │ [3] → nullptr │ │ [4] → [40] → [50] │ ← 链表 │ [5] → nullptr │ │ [6] → nullptr │ │ [7] → nullptr │ └─────────────────────────────────────────┘ ​ 每个桶是一个指针指向链表头节点 链表存储实际的数据map(关联容器)存储键值对key-value pair并根据键自动排序。什么是mapmapstring, int scores; // 键的类型 值的类型 ​ scores[张三] 95; scores[李四] 88; scores[王五] 92;以键值对的形式存储每个键只能出现一次按键进行自动排序。底层结构是红黑树查找复杂度O(log n)键类型的限制必须支持操作符可比较键类型是否需要自定义比较器说明基本类型(int, double, char)❌ 不需要原生支持string❌ 不需要支持字典序比较指针❌ 不需要按地址比较自定义类✅ 需要重载operator或提供比较器pair/tuple❌ 不需要自动按元素逐个比较数组 (array)❌ 不需要自动按元素逐个比较枚举❌ 不需要按整数值比较自定义比较器// 降序排序 struct Descending { bool operator()(const int a, const int b) const { return a b; } }; mapint, string, Descending m; ​ // Lambda 比较器 auto cmp [](const string a, const string b) { return a.size() b.size(); // 按字符串长度排序 }; mapstring, int, decltype(cmp) wordMap(cmp);mapvsunordered_map特性mapunordered_map底层结构红黑树哈希表排序✅ 自动排序键❌ 不排序查找复杂度O(log n)O(1) 平均插入复杂度O(log n)O(1) 平均键的类型要求必须可比较必须可哈希内存占用较小较大头文件mapunordered_map使用场景需要有序键只需要快速查找multimap允许重复键常用操作mapint, int iimap; // int → int 映射 ​ // 插入 iimap[1] 10; // 下标插入 iimap.insert({2, 20}); // insert iimap.emplace(3, 30); // emplace推荐 ​ // 访问 cout iimap[1]; // 10键不存在会插入默认值 cout iimap.at(2); // 20键不存在抛出异常 ​ // 查找 auto it iimap.find(3); if (it ! iimap.end()) { cout it-first → it-second; } ​ // 检查存在 if (iimap.count(4)) { // 返回 0 或 1 cout 键存在; } ​ // 删除 iimap.erase(2); // 删除键为 2 的元素 iimap.clear(); // 清空应用统计数组元素出现次数#include map #include vector #include iostream using namespace std; ​ int main() { vectorint data {1, 2, 3, 2, 1, 3, 3, 4, 5, 2, 1, 1}; mapint, int countMap; // 数字 → 出现次数 // 统计每个数字出现次数 for (int x : data) { countMap[x] 1; // 核心统计逻辑 } // 输出统计结果 cout 数字统计: endl; for (const auto p : countMap) { cout p.first 出现 p.second 次 endl; } // 1 出现 4 次 // 2 出现 3 次 // 3 出现 3 次 // 4 出现 1 次 // 5 出现 1 次 return 0; }练习差分数组区间累加思路核心想法不逐个修改每个位置只记录哪里开始变化和哪里结束变化。想象一下你有一排抽屉想给其中一段抽屉各放 5 个苹果暴力法逐个打开每个抽屉放苹果累差分法在第一个抽屉贴张纸条从这里开始 5在最后一个抽屉后面贴张纸条到这里结束 -5最后从头到尾走一遍就知道每个抽屉该放多少文字步骤第一步理解差分的工作原理如果把每个位置的变化看作水流 - 在起点 i 打开水龙头水流增加 kdiff[i] k - 在终点 j1 关掉水龙头水流减少 kdiff[j1] - k - 从 0 号位置开始走一路上遇到水龙头就调整水流大小 - 当前位置的水流大小 该位置最终的商品数量第二步处理每个区间区间 [0, 3, 5] → 在 0 号位置打开水龙头5 → 在 4 号位置关掉水龙头-5 效果位置 0,1,2,3 有水5位置 4 没水0 ​ 区间 [2, 4, 6] → 在 2 号位置再开一个水龙头6 → 在 5 号位置关掉-6 效果位置 2,3,4 再多 6 ​ 区间 [0, 4, 2] → 在 0 号位置再开一个2 → 在 5 号位置再关一个-2 效果位置 0,1,2,3,4 再多 2第三步记录所有变化差分表位置 07从区间1和区间3来的 5 和 2 位置 4-5区间1结束 位置 26区间2开始 位置 5-8区间2和区间3结束-6 和 -2第四步从左到右累加前缀和从 0 号位置出发手上拿着一个计数器 curr 0 ​ 位置 0遇到 7 → curr 7 → 结果[0] 7 位置 1没有变化 → curr 7 → 结果[1] 7 位置 2遇到 6 → curr 13 → 结果[2] 13 位置 3没有变化 → curr 13 → 结果[3] 13 位置 4遇到 -5 → curr 8 → 结果[4] 8四、范围for循环for(auto:ar){}可以对顺序容器关联容器进行循环迭代不能对容器适配器进行范围for循环迭代范围 for 循环遍历vector类对象时如果使用值传递方式确实会频繁调用拷贝构造函数和析构函数。