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

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

容器类型对比

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

---

1. std::map 有序 · 键值对

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

头文件与命名空间

#include <map>

模板参数

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() 等。

自定义比较

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 是基于红黑树的有序关联容器，存储唯一键，元素按值自动排序。

头文件与命名空间

#include <set>

模板参数

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，支持正向、反向、常量迭代器。

自定义比较

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) 访问。

头文件与命名空间

#include <unordered_map>

模板参数

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 个元素的空间

自定义哈希与相等比较

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) 访问。

头文件与命名空间

#include <unordered_set>

模板参数

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	无	判断是否为空。