# C++ map&set关联容器完全指南

# 📚 C++ 关联容器完全指南

本文详细介绍 C++ 标准库中的四种核心关联容器：`std::map`、`std::set`、`std::unordered_map`、`std::unordered_set`。涵盖构造、插入、查找、删除、性能特性及完整函数列表。

## 容器类型对比

| 类型 | 特性 |
| --- | --- |
| 🔷 有序关联容器 | `map`：键值对，键唯一，按**键排序**（红黑树）  
`set`：键集合，元素唯一，按**值排序** |
| ⚡ 无序关联容器 | `unordered_map`：键值对，键唯一，基于**哈希表**  
`unordered_set`：键集合，元素唯一，基于**哈希表** |

* * *

## 1\. std::map **有序 · 键值对**

`std::map` 是基于**红黑树**的有序关联容器，存储 **键-值对**，键唯一并按升序排列。

### 头文件与命名空间

```cpp
#include <map>
```

### 模板参数

```cpp
template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class map;
```

### 构造与初始化

| 方式 | 示例 |
| --- | --- |
| 默认构造 | `std::map<int, std::string> m;` |
| 初始化列表 | `std::map<int, std::string> m = {{1,"a"}, {2,"b"}};` |
| 范围构造 | `std::map<int, std::string> m(begin, end);` |
| 拷贝/移动构造 | `std::map<int, std::string> m2(m1);`  
`std::map<int, std::string> m2(std::move(m1));` |

### 插入元素

*   `insert(pair)`：返回 `pair<iterator,bool>`，布尔表示是否成功。
    
*   `emplace(args...)`：原地构造键值对。
    
*   `emplace_hint(hint, args...)`：带提示插入。
    
*   `operator[]`：若键存在返回引用，否则插入默认值。
    
*   `try_emplace(key, args...)` (C++17)：键不存在才插入，更安全。
    

### 访问元素

*   `at(key)`：返回值的引用，键不存在抛 `std::out_of_range`。
    
*   `operator[]`：可能插入默认值，不能用于 const 对象。
    

### 查找元素

*   `find(key)`：返回迭代器，未找到返回 `end()`。
    
*   `count(key)`：返回 0 或 1。
    
*   `contains(key)` (C++20)：返回 bool。
    
*   `lower_bound(key)` / `upper_bound(key)`：边界查找。  
    📘 lower\_bound: 第一个 ≥ key 📘 upper\_bound: 第一个 > key
    
*   `equal_range(key)`：返回键等于 key 的范围。
    

### 删除元素

*   `erase(iterator)`、`erase(key)`、`erase(first,last)`
    
*   `clear()`：清空所有元素。
    

### 迭代器

支持正向、反向、常量迭代器：`begin()`, `end()`, `rbegin()`, `rend()`, `cbegin()`, `cend()` 等。

### 自定义比较

```cpp
struct MyCompare {
    bool operator()(const int& a, const int& b) const {
        return a > b;   // 降序
    }
};
std::map<int, std::string, MyCompare> m;
```

### 性能复杂度

*   插入/删除/查找：O(log n)
    
*   遍历：O(n)
    

### C++11/17/20 新特性

*   C++11：`emplace`, `cbegin/cend`, 移动语义
    
*   C++17：`try_emplace`, `insert_or_assign`, `extract`
    
*   C++20：`contains`
    

### ⚠️ map 易错点

1.  `operator[]` 会插入默认值，误用可能导致意外插入。
    
2.  遍历时删除必须正确处理迭代器失效：`it = m.erase(it);`
    
3.  自定义比较必须满足严格弱序。
    
4.  键是 const 的，不能通过迭代器修改键。
    

### map 相关函数列表

| 函数名 | 参数 | 功能 |
| --- | --- | --- |
| `map()` | 无 | 默认构造空 map。 |
| `map(std::initializer_list<value_type> init)` | `init` - 初始化列表 | 用初始化列表构造。 |
| `map(const map& other)` | `other` - 另一个 map | 拷贝构造。 |
| `map(map&& other)` | `other` - 右值 map | 移动构造。 |
| `iterator begin()` | 无 | 返回首元素迭代器。 |
| `iterator end()` | 无 | 返回尾后迭代器。 |
| `bool empty() const` | 无 | 判断是否为空。 |
| `size_type size() const` | 无 | 返回元素个数。 |
| `T& operator[](const key_type& key)` | `key` - 键 | 访问或插入默认值。 |
| `T& at(const key_type& key)` | `key` - 键 | 带边界检查的访问。 |
| `std::pair<iterator,bool> insert(const value_type& value)` | `value` - 键值对 | 插入元素，返回是否成功。 |
| `iterator insert(const_iterator hint, const value_type& value)` | `hint` - 提示位置，`value` - 键值对 | 带提示插入。 |
| `template<class... Args> std::pair<iterator,bool> emplace(Args&&... args)` | `args` - 构造参数包 | 原地构造并插入。 |
| `iterator erase(iterator pos)` | `pos` - 要删除的迭代器 | 删除 pos 指向元素，返回下一迭代器。 |
| `size_type erase(const key_type& key)` | `key` - 要删除的键 | 删除键对应的元素，返回删除个数（0/1）。 |
| `void clear()` | 无 | 清空所有元素。 |
| `iterator find(const key_type& key)` | `key` - 键 | 查找键，返回迭代器。 |
| `size_type count(const key_type& key) const` | `key` - 键 | 返回键出现的次数（0/1）。 |
| `bool contains(const key_type& key) const (C++20)` | `key` - 键 | 判断键是否存在。 |
| `iterator lower_bound(const key_type& key)` | `key` - 键 | 返回第一个不小于 key 的迭代器。 |
| `iterator upper_bound(const key_type& key)` | `key` - 键 | 返回第一个大于 key 的迭代器。 |
| `std::pair<iterator,iterator> equal_range(const key_type& key)` | `key` - 键 | 返回键等于 key 的范围。 |

* * *

## 2\. std::set **有序 · 键集合**

`std::set` 是基于**红黑树**的有序关联容器，存储**唯一键**，元素按值自动排序。

### 头文件与命名空间

```cpp
#include <set>
```

### 模板参数

```cpp
template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;
```

### 构造与初始化

| 方式 | 示例 |
| --- | --- |
| 默认构造 | `std::set<int> s;` |
| 初始化列表 | `std::set<int> s = {1,2,3};` |
| 范围构造 | `std::set<int> s(begin, end);` |

### 插入元素

*   `insert(value)`：返回 `pair<iterator,bool>`。
    
*   `emplace(args...)`：原地构造。
    
*   `emplace_hint(hint, args...)`：带提示插入。
    

### 查找元素

*   `find(key)`：返回迭代器。
    
*   `count(key)`：返回 0 或 1。
    
*   `contains(key)` (C++20)：返回 bool。
    
*   `lower_bound(key)` / `upper_bound(key)`
    
*   `equal_range(key)`
    

### 删除元素

*   `erase(iterator)`、`erase(key)`、`erase(first,last)`
    
*   `clear()`
    

### 迭代器

同 map，支持正向、反向、常量迭代器。

### 自定义比较

```cpp
struct MyCompare {
    bool operator()(const int& a, const int& b) const {
        return a > b;   // 降序
    }
};
std::set<int, MyCompare> s;
```

### 性能复杂度

*   插入/删除/查找：O(log n)
    

### ⚠️ set 易错点

1.  元素是 const 的，不能通过迭代器修改。
    
2.  插入已存在的元素会失败，可通过返回值判断。
    
3.  自定义比较必须满足严格弱序。
    

### set 相关函数列表

| 函数名 | 参数 | 功能 |
| --- | --- | --- |
| `set()` | 无 | 默认构造空 set。 |
| `set(std::initializer_list<value_type> init)` | `init` - 初始化列表 | 用初始化列表构造。 |
| `iterator begin()` | 无 | 返回首元素迭代器。 |
| `iterator end()` | 无 | 返回尾后迭代器。 |
| `bool empty() const` | 无 | 判断是否为空。 |
| `size_type size() const` | 无 | 返回元素个数。 |
| `std::pair<iterator,bool> insert(const value_type& value)` | `value` - 要插入的值 | 插入元素，返回是否成功。 |
| `iterator insert(const_iterator hint, const value_type& value)` | `hint` - 提示位置，`value` - 值 | 带提示插入。 |
| `template<class... Args> std::pair<iterator,bool> emplace(Args&&... args)` | `args` - 构造参数包 | 原地构造并插入。 |
| `iterator erase(iterator pos)` | `pos` - 要删除的迭代器 | 删除元素，返回下一迭代器。 |
| `size_type erase(const key_type& key)` | `key` - 要删除的值 | 删除键，返回删除个数（0/1）。 |
| `void clear()` | 无 | 清空所有元素。 |
| `iterator find(const key_type& key)` | `key` - 值 | 查找值，返回迭代器。 |
| `size_type count(const key_type& key) const` | `key` - 值 | 返回值出现的次数（0/1）。 |
| `bool contains(const key_type& key) const (C++20)` | `key` - 值 | 判断值是否存在。 |
| `iterator lower_bound(const key_type& key)` | `key` - 值 | 返回第一个不小于 key 的迭代器。 |
| `iterator upper_bound(const key_type& key)` | `key` - 值 | 返回第一个大于 key 的迭代器。 |
| `std::pair<iterator,iterator> equal_range(const key_type& key)` | `key` - 值 | 返回值等于 key 的范围。 |

* * *

## 3\. std::unordered\_map **无序 · 键值对**

`std::unordered_map` 是基于**哈希表**的无序关联容器，存储 **键-值对**，键唯一，平均 O(1) 访问。

### 头文件与命名空间

```cpp
#include <unordered_map>
```

### 模板参数

```cpp
template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class unordered_map;
```

### 插入元素

*   `insert(pair)`：返回 `pair<iterator,bool>`。
    
*   `emplace(args...)`、`emplace_hint`
    
*   `operator[]`：若键存在返回引用，否则插入默认值。
    
*   `try_emplace(key, args...)` (C++17)
    
*   `insert_or_assign(key, value)` (C++17)
    

### 访问元素

*   `at(key)`：抛异常版
    
*   `operator[]`：可能插入默认值
    

### 查找元素

*   `find(key)`：返回迭代器
    
*   `count(key)`：返回 0 或 1
    
*   `contains(key)` (C++20)
    
*   `equal_range(key)`
    

> 注意：无序容器没有 `lower_bound/upper_bound`，因为元素无序。

### 桶接口（哈希表特有）

*   `bucket_count()`：桶的数量
    
*   `max_bucket_count()`
    
*   `bucket_size(size_type n)`：第 n 个桶的元素个数
    
*   `bucket(key)`：键所在的桶索引
    
*   `load_factor()`：当前负载因子
    
*   `max_load_factor()`：最大负载因子（可设置）
    
*   `rehash(n)`：预留至少 n 个桶
    
*   `reserve(n)`：预留至少 n 个元素的空间
    

### 自定义哈希与相等比较

```cpp
struct MyHash {
    size_t operator()(const int& x) const {
        return std::hash<int>()(x) ^ (x >> 1);
    }
};
struct MyEqual {
    bool operator()(const int& a, const int& b) const {
        return a == b;
    }
};
std::unordered_map<int, std::string, MyHash, MyEqual> m;
```

### 性能复杂度

*   平均插入/删除/查找：O(1)，最坏 O(n)（哈希冲突严重）
    
*   遍历：O(n)
    

### ⚠️ unordered\_map 易错点

1.  哈希函数质量差会导致严重性能下降，甚至退化为 O(n)。
    
2.  `operator[]` 会插入默认值，与 map 相同。
    
3.  迭代器在 rehash 后会失效，但插入元素不一定会 rehash。
    
4.  键类型必须支持哈希和相等比较。
    

### unordered\_map 相关函数列表

| 函数名 | 参数 | 功能 |
| --- | --- | --- |
| `unordered_map()` | 无 | 默认构造空 unordered\_map。 |
| `unordered_map(std::initializer_list<value_type> init)` | `init` - 初始化列表 | 用初始化列表构造。 |
| `iterator begin()` | 无 | 返回首元素迭代器。 |
| `iterator end()` | 无 | 返回尾后迭代器。 |
| `bool empty() const` | 无 | 判断是否为空。 |
| `size_type size() const` | 无 | 返回元素个数。 |
| `T& operator[](const key_type& key)` | `key` - 键 | 访问或插入默认值。 |
| `T& at(const key_type& key)` | `key` - 键 | 带边界检查的访问。 |
| `std::pair<iterator,bool> insert(const value_type& value)` | `value` - 键值对 | 插入元素，返回是否成功。 |
| `iterator insert(const_iterator hint, const value_type& value)` | `hint` - 提示位置（仅作为优化提示） | 带提示插入。 |
| `template<class... Args> std::pair<iterator,bool> emplace(Args&&... args)` | `args` - 构造参数包 | 原地构造并插入。 |
| `iterator erase(iterator pos)` | `pos` - 要删除的迭代器 | 删除元素，返回下一迭代器。 |
| `size_type erase(const key_type& key)` | `key` - 要删除的键 | 删除键对应的元素，返回删除个数（0/1）。 |
| `void clear()` | 无 | 清空所有元素。 |
| `iterator find(const key_type& key)` | `key` - 键 | 查找键，返回迭代器。 |
| `size_type count(const key_type& key) const` | `key` - 键 | 返回键出现的次数（0/1）。 |
| `bool contains(const key_type& key) const (C++20)` | `key` - 键 | 判断键是否存在。 |
| `size_type bucket_count() const` | 无 | 返回桶的数量。 |
| `size_type bucket_size(size_type n) const` | `n` - 桶索引 | 返回第 n 个桶的元素个数。 |
| `float load_factor() const` | 无 | 返回当前负载因子（元素数/桶数）。 |
| `void rehash(size_type n)` | `n` - 新桶数下限 | 重新哈希，使桶数至少为 n。 |
| `void reserve(size_type n)` | `n` - 预留元素数 | 预先分配空间，使负载因子不超过 max\_load\_factor。 |

* * *

## 4\. std::unordered\_set **无序 · 键集合**

`std::unordered_set` 是基于**哈希表**的无序关联容器，存储**唯一键**，平均 O(1) 访问。

### 头文件与命名空间

```cpp
#include <unordered_set>
```

### 模板参数

```cpp
template<
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> class unordered_set;
```

### 插入元素

*   `insert(value)`、`emplace`、`emplace_hint`
    

### 查找元素

*   `find(key)`
    
*   `count(key)`
    
*   `contains(key)` (C++20)
    
*   `equal_range(key)`
    

### 桶接口

与 unordered\_map 相同：`bucket_count`, `bucket_size`, `load_factor`, `rehash`, `reserve` 等。

### 自定义哈希与相等比较

与 unordered\_map 类似，需提供哈希函数和相等比较器。

### 性能复杂度

*   平均插入/删除/查找：O(1)，最坏 O(n)
    

### ⚠️ unordered\_set 易错点

1.  元素不可修改（const），修改必须删除再插入。
    
2.  哈希冲突会导致性能下降，必要时使用 `reserve` 预分配。
    
3.  自定义类型需要提供哈希函数和相等比较。
    

### unordered\_set 相关函数列表

| 函数名 | 参数 | 功能 |
| --- | --- | --- |
| `unordered_set()` | 无 | 默认构造空 unordered\_set。 |
| `unordered_set(std::initializer_list<value_type> init)` | `init` - 初始化列表 | 用初始化列表构造。 |
| `iterator begin()` | 无 | 返回首元素迭代器。 |
| `iterator end()` | 无 | 返回尾后迭代器。 |
| `bool empty() const` | 无 | 判断是否为空。 |