📚 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 易错点

operator[] 会插入默认值，误用可能导致意外插入。
遍历时删除必须正确处理迭代器失效：it = m.erase(it);
自定义比较必须满足严格弱序。
键是 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 易错点

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

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 易错点

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

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 易错点

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

unordered_set 相关函数列表

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

Command Palette

Comments

C++

C++ 类核心知识完整总结

More from this blog

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

容器类型对比

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

头文件与命名空间

模板参数

构造与初始化

插入元素

访问元素

查找元素

删除元素

迭代器

自定义比较

性能复杂度

C++11/17/20 新特性

⚠️ map 易错点

map 相关函数列表

2. std::set 有序 · 键集合

头文件与命名空间

模板参数

构造与初始化

插入元素

查找元素

删除元素

迭代器

自定义比较

性能复杂度

⚠️ set 易错点

set 相关函数列表

3. std::unordered_map 无序 · 键值对

头文件与命名空间

模板参数

插入元素

访问元素

查找元素

桶接口（哈希表特有）

自定义哈希与相等比较

性能复杂度

⚠️ unordered_map 易错点

unordered_map 相关函数列表

4. std::unordered_set 无序 · 键集合

头文件与命名空间

模板参数

插入元素

查找元素

桶接口

自定义哈希与相等比较

性能复杂度

⚠️ unordered_set 易错点

unordered_set 相关函数列表