国外移动端网站模板,寻加工厂合作订单,wordpress默认登录,银行网站建设中C 标准模板库#xff08;STL#xff09;中的关联式容器以其强大的功能和高效性成为开发者解决复杂数据组织问题的重要工具。其中#xff0c;set 和 map 是最常用的两类关联容器。本篇博客将从基本特性、底层实现、用法详解、高级案例以及性能优化等多个角度#xff0c;详细…C 标准模板库STL中的关联式容器以其强大的功能和高效性成为开发者解决复杂数据组织问题的重要工具。其中set 和 map 是最常用的两类关联容器。本篇博客将从基本特性、底层实现、用法详解、高级案例以及性能优化等多个角度详细解读它们的设计与使用。 目录 1. 什么是关联式容器
关联式容器的核心特性
2. set 容器详解
2.1 基本概念与特性
2.2 底层实现红黑树
红黑树的特性
红黑树的操作
2.3 构造函数
2.4 常用操作与复杂度分析
插入操作
查找操作
删除操作
遍历
2.5 特殊操作与技巧
(1) 自定义排序规则
(2) 范围删除
(3) 应用求两个数组的交集
2.6 multiset 的区别与应用 1. 什么是关联式容器
关联式容器是一类根据关键字组织和管理数据的容器。与序列式容器如 vector 和 list相比关联式容器的主要区别如下
特性关联式容器set/map序列式容器vector/list数据存储顺序按关键字排序按插入顺序数据访问复杂度O(logN)O(\log N)O(logN)O(1)O(1)O(1) 或 O(N)O(N)O(N)是否支持随机访问否是是否支持按索引访问否是
关联式容器分为有序和无序两类
有序容器如 set 和 map基于平衡二叉树红黑树实现数据按排序规则组织。无序容器如 unordered_set 和 unordered_map基于哈希表实现提供更高效的查找速度但不保证元素顺序。
关联式容器的核心特性
键值对关联式容器通过关键字对元素进行组织set 中的关键字即为数据本身而 map 则以键值对形式存储数据。自动排序有序容器会自动对数据进行排序升序或自定义规则。高效操作插入、删除、查找的平均时间复杂度为 O(logN)O(\log N)O(logN)红黑树实现。 2. set 容器详解
2.1 基本概念与特性
set 是一种集合数据结构用于存储唯一且自动排序的元素。它的主要特点如下
数据唯一性同一元素不能重复插入。自动排序默认按升序排序可通过自定义比较器更改排序规则。迭代器类型set 支持双向迭代器不支持随机访问。底层实现使用红黑树作为存储结构。
2.2 底层实现红黑树
红黑树的特性
红黑树是一种平衡二叉搜索树满足以下性质
每个节点是红色或黑色。根节点是黑色。每个叶子节点nullptr 或 NIL 节点是黑色。如果一个节点是红色则其子节点必须是黑色即红色节点不能相邻。从任意节点到其每个叶子节点的路径都包含相同数量的黑色节点。
红黑树的操作
插入通过旋转和重新着色确保平衡性和红黑性质。删除比插入更复杂同样通过旋转和着色维护树的性质。查找沿树遍历时间复杂度为 O(logN)O(\log N)O(logN)。
在 set 和 map 中红黑树用来高效实现元素的有序存储和快速查找。 2.3 构造函数
set 提供以下几种构造方式
默认构造创建一个空集合。 setint s;初始化列表构造直接用 {} 初始化集合。 setint s {3, 1, 4, 1, 5, 9}; // 重复元素自动去重迭代器区间构造从其他容器的元素构造集合。 vectorint v {1, 2, 3, 4};
setint s(v.begin(), v.end());自定义比较规则 setint, greaterint s {3, 1, 4}; // 按降序排序2.4 常用操作与复杂度分析
操作函数复杂度说明插入insert(value)O(logN)O(\log N)O(logN)插入元素若已存在则插入失败删除erase(value)O(logN)O(\log N)O(logN)删除指定元素查找find(value)O(logN)O(\log N)O(logN)返回迭代器指向目标元素统计count(value)O(logN)O(\log N)O(logN)判断元素是否存在结果为 0 或 1遍历begin(), end()O(N)O(N)O(N)正向迭代访问所有元素下界/上界lower_bound()/upper_bound()O(logN)O(\log N)O(logN)返回 / 某值的第一个元素的迭代器
插入操作
setint s;
auto res s.insert(10); // 插入 10
if (res.second) {cout 插入成功 endl;
} else {cout 插入失败 endl;
}查找操作
if (s.find(20) ! s.end()) {cout 找到元素 20 endl;
}删除操作
s.erase(10); // 删除值为 10 的元素遍历
for (int x : s) {cout x ; // 正向遍历
}
for (auto it s.rbegin(); it ! s.rend(); it) {cout *it ; // 反向遍历
}2.5 特殊操作与技巧
(1) 自定义排序规则
set 默认按升序排序使用仿函数或 std::greater 可修改排序规则
setint, greaterint s {3, 1, 4};(2) 范围删除
删除值在 [low, high) 范围内的所有元素
s.erase(s.lower_bound(10), s.upper_bound(50));(3) 应用求两个数组的交集
vectorint intersection(const vectorint nums1, const vectorint nums2) {setint s1(nums1.begin(), nums1.end());setint s2(nums2.begin(), nums2.end());vectorint result;for (int x : s1) {if (s2.count(x)) result.push_back(x);}return result;
}2.6 multiset 的区别与应用
multiset 与 set 的区别在于
multiset 允许存储重复元素。插入、删除和查找操作的接口与 set 相同但返回的结果会包含重复项。
multisetint ms {1, 2, 2, 3};
ms.insert(2); // 再次插入 23. map 容器详解
3.1 基本概念与特性
map 是一个关联式容器用于存储键值对key-value。与 set 相比map 不仅存储键key还存储与每个键关联的值value。map 的主要特点包括
键唯一性每个键在 map 中都是唯一的。自动排序默认按照键的升序排序也可以通过自定义比较器来更改排序规则。底层实现基于红黑树实现操作复杂度为 O(logN)O(\log N)O(logN)。支持随机访问与 set 不同map 中存储的键值对支持通过键快速查找对应的值。
mapint, string m;
m[1] apple; // 插入键值对 (1, apple)
m[2] banana; // 插入键值对 (2, banana)
m[3] cherry; // 插入键值对 (3, cherry)内部存储结构
map 使用红黑树存储数据保证了所有元素按键值自动排序。在 map 中每个节点存储一个 pairconst Key, T其中 const Key 表示键T 表示值。红黑树的特点确保了查找、插入和删除操作的时间复杂度都为 O(logN)O(\log N)O(logN)。 3.2 构造与初始化
map 提供了多种构造方法以适应不同的使用场景 默认构造创建一个空 map。 mapint, string m;初始化列表构造通过初始化列表直接创建 map。 mapint, string m {{1, apple}, {2, banana}, {3, cherry}};范围构造从另一个容器如 set、vector 等构造 map。 vectorpairint, string v {{1, apple}, {2, banana}};
mapint, string m(v.begin(), v.end());自定义比较器通过传入自定义比较器指定键的排序方式。 mapint, string, greaterint m; // 降序排序
m[2] banana;
m[1] apple;3.3 常用操作与复杂度分析
操作函数复杂度说明插入insert(pair)O(logN)O(\log N)O(logN)插入一个键值对若已存在则插入失败插入或修改operator[]O(logN)O(\log N)O(logN)插入新元素或修改已有元素的值查找find(key)O(logN)O(\log N)O(logN)查找指定键返回键值对的迭代器统计count(key)O(logN)O(\log N)O(logN)查找指定键是否存在map 中为 0 或 1删除erase(key)O(logN)O(\log N)O(logN)删除指定键及其对应的值遍历begin(), end()O(N)O(N)O(N)正向遍历所有元素下界/上界lower_bound(key)/upper_bound(key)O(logN)O(\log N)O(logN)查找大于等于某值或大于某值的第一个元素
插入与查找操作 插入可以通过 insert 方法插入新的键值对也可以通过 operator[] 插入或修改键值对。 mapint, string m;
m.insert({1, apple});
m[2] banana; // 插入或修改查找find 方法返回一个迭代器指向指定键的键值对若未找到则返回 end()。 auto it m.find(1);
if (it ! m.end()) {cout Found: it-second endl; // 输出 apple
}删除操作
删除某个键值对
m.erase(1); // 删除键为 1 的元素3.4 遍历与修改
map 提供了多种遍历方法 范围 for for (const auto [key, value] : m) {cout key : value endl;
}传统迭代器 for (auto it m.begin(); it ! m.end(); it) {cout it-first : it-second endl;
}修改值
可以通过迭代器直接修改值operator[] 也支持修改已有键的值
m[2] grape; // 修改键为 2 的值为 grape
auto it m.find(2);
if (it ! m.end()) {it-second orange; // 通过迭代器修改值
}3.5 特殊操作与进阶技巧
(1) 下界与上界
通过 lower_bound() 和 upper_bound() 方法可以获取某个键的下界和上界常用于区间查找。
lower_bound(key)返回第一个大于等于 key 的元素。upper_bound(key)返回第一个大于 key 的元素。
mapint, string m {{1, apple}, {2, banana}, {3, cherry}};
auto lb m.lower_bound(2); // 返回键为 2 或大于 2 的第一个元素
cout lb-second endl; // 输出 banana(2) 自定义排序规则
如同 setmap 也可以通过自定义比较器来实现不同的排序规则。
mapint, string, greaterint m {{1, apple}, {3, cherry}, {2, banana}};
for (const auto [key, value] : m) {cout key : value endl;
} // 输出3: cherry 2: banana 1: apple(3) 范围删除
删除某个键值范围内的元素常用于清除一段区间
mapint, string m {{1, apple}, {2, banana}, {3, cherry}};
m.erase(m.lower_bound(2), m.upper_bound(3)); // 删除键为 2 和 3 的元素3.6 multimap 的区别与应用
multimap 是 map 的扩展允许相同的键有多个值即支持键的冗余。与 map 的区别在于multimap 在插入重复键时不会丢失数据而 map 会自动覆盖原有键。
multimapint, string mm;
mm.insert({1, apple});
mm.insert({1, banana});
mm.insert({2, cherry});for (const auto [key, value] : mm) {cout key : value endl; // 输出1: apple 1: banana 2: cherry
}multimap 在某些场景下非常有用例如存储学生成绩时可能有多个学生取得相同的分数。 4. 高级案例综合利用 set 和 map
4.1 查找两个数组的交集
vectorint intersection(const vectorint nums1, const vectorint nums2) {setint s1(nums1.begin(), nums1.end());setint s2(nums2.begin(), nums2.end());vectorint result;for (int x : s1) {if (s2.count(x)) result.push_back(x);}return result;
}4.2 构建词频统计表
mapstring, int wordCount(const vectorstring words) {mapstring, int wordMap;for (const string word : words) {wordMap[word];}return wordMap;
}4.3 高效查找链表中的环
bool hasCycle(ListNode* head) {setListNode* visited;while (head ! nullptr) {if (visited.find(head) ! visited.end()) {return true; // 找到环}visited.insert(head);head head-next;}return false;
}5. 性能优化与注意事项
5.1 使用 unordered_map 和 unordered_set
在很多查找密集型的应用中unordered_map 和 unordered_set 基于哈希表实现提供常数时间复杂度 O(1)O(1)O(1) 的查找和插入操作。它们的性能优势适用于不需要保持元素顺序的场景。
5.2 避免不必要的拷贝
当插入大量数据时可以使用 emplace() 来避免不必要的对象拷贝。emplace() 可以直接构造元素而无需创建临时对象。
mapint, string m;
m.emplace(1, apple); // 不会发生拷贝5.3 避免频繁修改键
map 不支持修改键修改键会导致数据结构破坏。因此避免频繁修改键而应使用新的键值对进行插入和删除。 6. 总结
通过本文的详细解析我们全面了解了 C 中 set 和 map 容器的使用、底层实现以及高效操作技巧。掌握这些基本知识后开发者可以灵活使用 set 和 map 来处理各种复杂的关联数据问题从而提高程序的效率和可读性。
在实际开发中选择合适的容器如 map 与 unordered_mapset 与 unordered_set可以帮助我们应对不同的数据处理需求避免性能瓶颈。希望通过本文的学习你能够深入掌握这些强大的容器提升 C 编程技能。
