赞
踩
C++ STL中,哈希表对应的容器是 unordered_map
(since C++ 11)。根据 C++ 11 标准的推荐,用 unordered_map
代替 hash_map
。
先来回顾一下数据结构中哈希表相关的知识。
哈希表是根据关键码值(key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度,这个映射函数叫做散列函数。
哈希表的一个重要问题就是如何解决映射冲突的问题。常用的有两种:开放地址法 和 链地址法。
STL中,map
对应的数据结构是 红黑树。红黑树是一种近似于平衡的二叉查找树,里面的数据是有序的。在红黑树上做查找操作的时间复杂度为 O(logN)。而 unordered_map
对应 哈希表,哈希表的特点就是查找效率高,时间复杂度为常数级别 O(1), 而额外空间复杂度则要高出许多。所以对于需要高效率查询的情况,使用 unordered_map
容器。而如果对内存大小比较敏感或者数据存储要求有序的话,则可以用 map
容器。
unordered_map 是一种关联容器,用于存储由关键值 (Key Value,以下称为Key 值) 和映射值 (Mapped Value,以下称为映射值) 组成的元素,并且允许根据其 Key 值快速检索各个元素。
在 unordered_map 容器中,Key 值通常用来唯一标识元素,映射值是与该 Key 值关联内容的对象。Key 值与映射值的类型可能不同。
在 unordered_map 内部,元素没有按照其 Key 值与映射值的任何顺序进行排序 ,而是根据它们的 Hash 值组织成桶,允许它们通过其 Key 值直接快速访问单个元素(通常具有常数等级的平均时间复杂度)。
unordered_map 容器与 map 容器相比,通过 Key 值访问各个元素的速度更快,然而通过其元素子集进行范围迭代的效率通常较低。
unordered_map 实现了直接访问操作符 (operator[]),它允许使用 Key 值作为输入参数,直接访问映射值。
容器中的迭代器至少是前向迭代器。
关联性
关联容器中的元素的参考地址指的是其 Key 值,而不是他们在容器中的绝对地址;
无序性
无序容器使用 Hash 表来组织元素,这些 Hash 表允许无序容器通过 Key 值快速访问元素;
映射
每个元素将一个 Key 值与映射值关联起来,Key 值用于标识其主要内容是映射值的元素;
唯一关键值
容器中不存在同时拥有相同 Key 值的两个元素;
分配器感知
map 容器使用分配器对象动态处理其存储需求。
bucket
size_type bucket ( const key_type& k ) const;
定位元素所在的桶,返回 Key 值为输入参数 k 的元素的所在桶号。
桶是容器内部 Hash 表中的一个槽,槽中的元素根据 Key 值分配元素。桶号的编号从 0 到 (bucket_count - 1)。 桶中单个元素可以通过 unordered_map::begin 和 unordered_map::end 返回的范围迭代器进行访问。
count
size_type count ( const key_type& k ) const;
搜索容器中 Key 值为输入参数 k 的元素,并返回找到元素的数量。由于 unordered_map 容器不允许存在重复的 Key 值,这说明如果容器中存在具有该 Key 值的元素,则该函数返回 1,否则返回 0。
clear
清除 map 中所有元素;
erase
删除 map 中指定位置的元素;
insert
在 map 指定位置添加 pair 类型的元素;
find
获取 map 中元素的迭代器;
begin, end
map 的正向迭代器的起始位置与终点位置
摘选自 Leetcode 问题 Two Sum:给出一个整数数组,返回两个数的下标值,令其和等于一个指定的目标值。
- #include <unordered_map>
- class Solution {
- public:
- vector<int> twoSum(vector<int> &numbers, int target)
- {
- //Key is the number and value is its index in the vector.
- unordered_map<int, int> hash;
- vector<int> result;
- for (int i = 0; i < numbers.size(); i++) {
- int numberToFind = target - numbers[i];
-
- //if numberToFind is found in map, return them
- if (hash.find(numberToFind) != hash.end()) {
- result.push_back(hash[numberToFind]);
- result.push_back(i);
- return result;
- }
-
- //number was not found. Put it in the map.
- hash[numbers[i]] = i;
- }
- return result;
- }
- };
参考“大专栏”
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。