行业知识
【C++】unordered 系列关联式容器
文章目录
- 1. unordered 系列关联式容器
- 2. unordered_map
- 2.1 unordered_map 的文档介绍
- 2.2 unordered_map 的接口说明
- 3. unordered_set
- 4. 在线 OJ
1. unordered 系列关联式容器
在 C++ 98 中，STL 提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 l o g 2 N log_2 N log2N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是：进行很少的比较次数就能将元素找到，因此在 C++ 11 中，STL 又提供了 4 个 unordered 系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对 unordered_map 和 unordered_set 进行介绍。
2. unordered_map
2.1 unordered_map 的文档介绍
unordered_map
- unordered_map 是存储 键值对的关联式容器，其允许通过 keys 快速的索引到与其对应的 value。
- 在 unordered_map 中，键值通常用于唯一的标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
- 在内部，unordered_map 没有对 按照任何特定的顺序排序，为了能在常数范围内找到 key 所对应的 value，unordered_map 将相同哈希值的键值对放在相同的桶中。
- unordered_map 容器通过 key 访问单个元素要比 map 快，但它通常在遍历元素子集的范围迭代方面效率较低。
- unordered_map 实现了直接访问操作符（operator[]），它允许使用 key 作为参数直接访问 value。
- 它的迭代器至少是前向迭代器。
2.2 unordered_map 的接口说明
-
unordered_map 的构造
函数声明 功能介绍 unordered_map 构造不同格式的 unordered_map 对象 -
unordered_map 的容量
函数声明 功能介绍 bool empty() const 检测 unordered_map 是否为空 size_t size() const 获取 unordered_map 的有效元素个数 -
unordered_map 的迭代器
函数声明 功能介绍 begin 返回 unordered_map 第一个元素的迭代器 end 返回 unordered_map 最后一个元素下一个位置的迭代器 cbegin 返回 unordered_map 第一个元素的 const 迭代器 cend 返回 unordered_map 最后一个元素下一个位置的 const 迭代器 -
unordered_map 的元素访问
函数声明 功能介绍 operator[] 返回 key 对应的 value，没有返回一个默认值 注意：该函数中实际调用哈希桶的插入操作，用参数 key 与 V() 构造一个默认值往底层哈希桶中插入，如果 key 不再哈希桶中，插入成功，返回 V()；插入失败，说明 key 已经在哈希桶中，将 key 对应的 value 返回。
-
unorder_map 的查询
函数声明 功能介绍 iterator find(const K& key) 返回 key 在哈希桶中的位置 size_t count(const K& key) 返回哈希桶中关键码为 key 的键值对的个数 注意：unordered_map 中 key 是不能重复的，因为 count 函数的返回值最大为 1。
-
unordered_map 的修改操作
函数声明 功能介绍 insert 向容器中插入键值对 erase 删除容器中的键值对 void clear() 清空容器中有效元素个数 void swap(unordered_map&) 交换两个容器中的元素 -
unordered_map 的桶操作
函数声明 功能介绍 size_t bucket_count() const 返回哈希桶中桶的总个数 size_t bucket_size(size_t n) const 返回 n 号桶中有效元素的总个数 size_t bucket(const K& key) 返回元素 key 所在的桶号
3. unordered_set
参见 unordered_set 在线文档说明。
4. 在线 OJ
-
在长度 2N 的数组中找出重复 N 次的元素
class Solution{public: int repeatedNTimes(vector& nums) { int n = nums.size() / 2; // 用 unordered_map 统计每个元素出现的次数 unordered_map hash; for (auto& e : nums) { ++hash[e]; }// 找出出现次数为 n 的元素个数 for (auto& e : hash) { if (e.second == n) { return e.first; } } return 0; }}; -
两个数组的交集
class Solution{public: vector intersection(vector& nums1, vector& nums2) { // 使用 unordered_set 去重 unordered_set us1; for (auto& e : nums1) { us1.insert(e); } unordered_set us2; for (auto& e : nums2) { us2.insert(e); }// 遍历 us1，在 us2 中寻找 us1 的每个元素，如果找到，即为交集 vector ret; for (auto& e : us1) { if (us2.find(e) != us2.end()) { ret.push_back(e); } } return ret; }}; -
两个数组的交集 Ⅱ
class Solution{public: vector intersect(vector& nums1, vector& nums2) { // 使用 unordered_map 统计次数 unordered_map um1; for (auto& e : nums1) { ++um1[e]; } unordered_map um2; for (auto& e : nums2) { ++um2[e]; }// 遍历 um1，在 um2 中查找 um1 的各个元素，并找到该元素出现次数的较小值 vector ret; for (auto& e : um1) { auto it = um2.find(e.first); if (it != um2.end()) { // 找较小值 int less = e.second; if (e.second > (*it).second) { less = (*it).second; } // 插入 for (int i = 0; i -
存在重复元素
class Solution{public: bool containsDuplicate(vector& nums) { unordered_map um; // 我们把 nums 各元素插入到 unordered_map 中 for (auto& e : nums) { // 如果在插入之前发现该元素已经存在于 unordered_map 中，说明该元素是重复的 if (um.find(e) != um.end()) { return true; } ++um[e]; } return false; }}; -
两句话中的不常见单词
class Solution{public: vector uncommonFromSentences(string s1, string s2) { // 分析题意，发现要找的单词就是在两个句子中只出现一次的单词 string str = s1 + " " + s2 + " "; unordered_map um; // 分割字符串入哈希表 int begin = 0, end = 0; while (begin
END
