9.22/2025

在做力扣第一题的时候反复拷打豆包，给出了0ms的打法

今天就好好学习下：

哈希表unordered_map

借鉴：https://blog.csdn.net/weixin_45031801/article/details/142033774

【unordered_map】  是 STL 中的容器之一，不同于普通容器，它的查找速度极快，常用来存储各种经常被检索的数据。除此之外，还可以借助其特殊的性质，解决部分难题。

在以往的 【STL 容器】学习中，我们接触到的都是 序列式容器，比如 string、vector、list、deque 等，序列式容器的特点就是 底层为线性序列的数据结构，就比如 list，其中的节点是 线性存储 的，一个节点存储一个元素，其中存储的元素都可序，但未必有序

【关联式容器】 则比较特殊，其中存储的是 键值对，这就意味着可以按照 键值大小 key 以某种特定的规则放置于适当的位置，关联式容器没有首尾的概念，因此没有头插尾插等相关操作，unordered_map 就属于 关联式容器

键值对

【键值对】是 一种用来表示具有一一对应关系的结构，该结构中一般只包含两个成员变量：key 和 value，前者表示 键值，后者表示 实值 。关联式容器的实现离不开【键值对】

哈希结构的关联式容器

• unordered_set
• unordered_multiset
• unordered_map
• unordered_multimap

树型结构与哈希结构的关联式容器功能都是一模一样的，不过 哈希结构查找比树型结构快得多 -> O(1)

注：

• STL 中选择的树型结构为 红黑树 RB-Tree
• 树型结构中的元素 中序遍历 后有序，而哈希结构中的元素无序

unordered_map 是存储 <key, value> 键值对 的关联式容器，其允许通过keys快速的索引到与其对应的value。

//SGI 版 STL 中的实现
template <class T1, class T2>
struct pair {
  typedef T1 first_type;
  typedef T2 second_type;
 
  T1 first;	
  T2 second;	
  pair() : first(T1()), second(T2()) {}
  pair(const T1& a, const T2& b) : first(a), second(b) {}
 
#ifdef __STL_MEMBER_TEMPLATES
  template <class U1, class U2>
  pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}
#endif
};

• pair 中的 first 表示 键值，second 则表示 实值，在给 【关联式容器】 中插入数据时，可以构建 pair 对象 

比如下面就构建了一个 键值 key 为 string，实值 value 为 int 的匿名 键值对 pair 对象   

pair<string, int>(“hehe”, 123);

可以将此匿名对象传入 关联式容器 中，当然这样写未免过于麻烦了，于是库中设计了一个函数模板 make_pair，可以根据传入的参数，去调用 pair 构建对象并返回
make_pair(“hehe”, 123); //构建出的匿名对象与上面的一致，该函数实际会被编译器优化为 内联函数，因此不会造成过多消耗，可以放心使用 

unordered_map实现了直接访问操作符(operator[ ])，它允许使用key作为参数直接访问value。
它的迭代器是单向迭代器。

（1）构造一个某个类型的容器

unordered_map<string, int> um1; // 构造一个key为string类型，value为int类型的空容器
（2）拷贝构造某个类型的容器

unordered_map<string, int> um1({ {“apple”, 1}, {“lemon”, 2}});
unordered_map<string, int> um2(um1); // 拷贝构造同类型容器um1的复制品
（3）使用迭代器区间进行初始化构造

构造一个 unordered_map 对象，其中包含 【first ，last )中的每一个元素副本。
unordered_map um1({ {“apple”, 1}, {“lemon”, 2}});
unordered_map um3(um1.begin(), um1.end()); // 使用迭代器拷贝构造um1容器某段区间的复制品

unordered_map 的成员函数主要分为：迭代器，容量操作，修改操作。

每个元素只有在它不等同于容器中已经存在的任何其他元素时才会被插入，也就是说unordered_ map 中的每个元素是唯一的。

unordered_map um({ {"apple", 1.0}, {"lemon", 2.0} });
// 构造匿名对象插入新元素
um.insert(pair<string, double>("milk", 2.0));

// 调用make_pair函数模板插入新元素
um.insert(make_pair("milk", 2.0));