Map & Unordered_map

Map使用红黑树组织数据，Unordered_map使用哈希表组织数据。

对于Map而言：

存储数据占用内存比哈希表更小，构造速度更快，但查找数据的速度更慢。构造函数只需要比较函数(less)。

查找对象的时间：$O(log{(n)})$

对于unordered_map而言：

占用内存比Map大，构造速度慢，但查找速度快。构造函数需要hash函数，等于函数(equal)。

查找对象的时间：近似为$O(1)$

map简介

map是STL的一个关联容器，它提供一对一的hash。

第一个可以称为关键字(key)，每个关键字只能在map中出现一次； 第二个可能称为该关键字的值(value)；

map以模板(泛型)方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。

Map主要用于资料 一对一映射(one-to-one) 的情況，map內部的实现自建一棵红黑树，这棵树具有对数据自动排序的功能。在map内部，所有的数据都是有序的。

对象初始化和成员函数

注意

使用map需要包含map类所在的头文件：

#include <map> //注意，STL头文件没有扩展名.h

对象初始化

map<键类型, 值类型> 标识符

键值对插入

插入键值对的方法有三种：

// 初始化
map<int, string> mapStudent;
// 第一种 用insert函數插入pair
mapStudent.insert(pair<int, string>(000, "student_zero"));
// 第二种 用insert函数插入value_type数据
mapStudent.insert(map<int, string>::value_type(001, "student_one"));
// 第三种 用"array"方式插入
mapStudent[002] = "student_two";

以上三种用法，虽然都可以实现数据的插入，但是它们是有区别的！

第一种和第二种在效果上是完成一样的，用insert函数插入数据，在数据的插入上涉及到集合的唯一性这个概念，即当map中有当前关键字时，insert操作是不能再插入数据的，但是用数组方式可以覆盖以前该关键字对应的值。

成员函数

begin()返回指向map头部的迭代器

clear()删除所有元素

count()返回指定元素出现的次数

empty()如果map为空则返回true

end()返回指向map末尾的迭代器

equal_range()返回特殊条目的迭代器对

erase()删除一个元素

find()查找一个元素

get_allocator()返回map的配置器

insert()插入元素

key_comp()返回比较元素key的函数

lower_bound()返回键值>=给定元素的第一个位置

max_size()返回可以容纳的最大元素个数

rbegin()返回一个指向map尾部的逆向迭代器

rend()返回一个指向map头部的逆向迭代器

size()返回map中元素的个数

swap()交换两个map

upper_bound()返回键值>给定元素的第一个位置

value_comp()返回比较元素value的函数

unordered_map简介

unordered_map基于hash table（哈希表）。功能与map相似。

哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。

其基本原理是：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。

但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。

总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。

对象初始化和成员函数

注意

使用unordered_map需要包含unordered_map类所在的头文件：

#include <unordered_map>

对象初始化

unordered_map<键类型, 值类型> 标识符;

成员函数

成员函数与map相似。

实战（49. Group Anagrams）

这一题的关键在于字母异位词排序后得到的字符串相同，可以用map记录每种字母异位词排序后的字符串的出现情况，并记录其存放在结果数组中的索引位置。

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string, int> count; // map记录每个字符串排序后字符串和在结果数组的索引
        vector<vector<string>> ans; // 结果数组
        int cur_index = 0; // 当前结果数组的长度
        for (int i = 0; i < strs.size(); i++) {
            string temp = strs[i];
            sort(temp.begin(), temp.end());
            if (count.count(temp)) { // map里有同款的字母异位词
                ans[count[temp]].push_back(strs[i]);
            } else { // map里没有当前同款的字母异位词
                count[temp] = cur_index;
                ans.push_back({strs[i]});
                cur_index++;
            }
        }
        return ans;
    }
};