107 std::map (关联容器)
作者Lou Xiao, deepseek创建时间2025-04-02 17:44:58更新时间2025-04-02 17:44:58
1. 基本概念
1.1 定义与特性
- 关联容器：基于键值对(key-value)存储元素
- 排序特性：元素按键的升序自动排序(默认)
- 唯一键：每个键在map中只能出现一次
- 底层实现：通常用红黑树(自平衡二叉查找树)实现
1.2 头文件
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <map>
1.3 模板参数
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
template<
2
class Key,
3
class T,
4
class Compare = std::less<Key>,
5
class Allocator = std::allocator<std::pair<const Key, T>>
6
> class map;
Key：键类型T：值类型Compare：比较函数对象类型(默认std::less<Key>)Allocator：分配器类型
2. 构造函数与初始化
2.1 常用构造方式
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::map<int, std::string> m1; // 空map
2
std::map<int, std::string> m2 = {{1, "one"}, {2, "two"}}; // 初始化列表
3
std::map<int, std::string> m3(m2.begin(), m2.end()); // 范围构造
4
std::map<int, std::string> m4(m3); // 拷贝构造
2.2 自定义比较函数
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
struct CaseInsensitiveCompare {
2
bool operator()(const std::string& a, const std::string& b) const {
3
return std::lexicographical_compare(
4
a.begin(), a.end(), b.begin(), b.end(),
5
[](char c1, char c2) { return tolower(c1) < tolower(c2); });
6
}
7
};
8
9
std::map<std::string, int, CaseInsensitiveCompare> caseInsensitiveMap;
3. 元素访问
3.1 下标操作符 []
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::map<std::string, int> m;
2
m["apple"] = 5; // 插入或修改
3
int count = m["apple"]; // 访问，若不存在会插入默认构造的值
3.2 at() 方法
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
try {
2
int count = m.at("apple"); // 访问，若不存在抛出std::out_of_range异常
3
} catch(const std::out_of_range& e) {
4
std::cerr << e.what() << '\n';
5
}
3.3 迭代器访问
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
for(auto it = m.begin(); it != m.end(); ++it) {
2
std::cout << it->first << ": " << it->second << '\n';
3
}
4. 容量操作
| 方法 | 描述 |
|---|---|
empty() | 检查容器是否为空 |
size() | 返回元素数量 |
max_size() | 返回可容纳的最大元素数 |
5. 修改操作
5.1 插入元素
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
// 使用insert
2
m.insert(std::make_pair(3, "three"));
3
m.insert({{4, "four"}, {5, "five"}}); // 初始化列表
4
5
// 使用emplace (C++11)
6
m.emplace(6, "six");
7
8
// 使用insert_or_assign (C++17)
9
m.insert_or_assign(3, "THREE"); // 若存在则更新，不存在则插入
5.2 删除元素
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
m.erase(3); // 通过键删除
2
auto it = m.find(4);
3
if(it != m.end()) {
4
m.erase(it); // 通过迭代器删除
5
}
6
m.erase(m.begin(), m.end()); // 范围删除
7
m.clear(); // 清空map
5.3 合并map (C++17)
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::map<int, std::string> m1 = {{1, "one"}, {2, "two"}};
2
std::map<int, std::string> m2 = {{2, "TWO"}, {3, "three"}};
3
m1.merge(m2);
4
// m1: {{1, "one"}, {2, "two"}, {3, "three"}}
5
// m2: {{2, "TWO"}}
6. 查找操作
| 方法 | 描述 |
|---|---|
find(key) | 查找键，返回迭代器，未找到返回end() |
count(key) | 返回匹配键的数量(0或1) |
contains(key) | (C++20)检查是否存在键 |
lower_bound(key) | 返回第一个不小于key的元素的迭代器 |
upper_bound(key) | 返回第一个大于key的元素的迭代器 |
equal_range(key) | 返回匹配键的范围(pair |
7. 迭代器
| 迭代器 | 描述 |
|---|---|
begin(), cbegin() | 指向第一个元素的迭代器 |
end(), cend() | 指向末尾(最后一个元素之后)的迭代器 |
rbegin(), crbegin() | 指向最后一个元素的反向迭代器 |
rend(), crend() | 指向开头之前位置的反向迭代器 |
8. 观察器
| 方法 | 描述 |
|---|---|
key_comp() | 返回键比较函数 |
value_comp() | 返回值比较函数(比较pair) |
9. 性能分析
| 操作 | 时间复杂度 |
|---|---|
| 插入 | O(log n) |
| 删除 | O(log n) |
| 查找 | O(log n) |
| 访问 | O(log n) |
| 遍历 | O(n) |
10. 相关容器比较
| 容器 | 键唯一 | 排序 | 底层实现 | 主要特点 |
|---|---|---|---|---|
std::map | 是 | 是 | 红黑树 | 自动排序，键唯一 |
std::multimap | 否 | 是 | 红黑树 | 允许重复键 |
std::unordered_map | 是 | 否 | 哈希表 | 更快查找，不排序 |
std::unordered_multimap | 否 | 否 | 哈希表 | 允许重复键，不排序 |
11. 最佳实践
- 键选择：键类型应支持严格弱序比较
- 自定义比较：复杂键类型可自定义比较函数
- 避免频繁插入删除：影响红黑树平衡
- 批量操作：使用范围插入/删除提高效率
- C++17特性：利用
try_emplace和insert_or_assign简化代码
12. 示例代码
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <map>
3
#include <string>
4
5
int main() {
6
// 创建并初始化map
7
std::map<std::string, int> wordCount = {
8
{"apple", 5},
9
{"banana", 3},
10
{"cherry", 8}
11
};
12
13
// 插入元素
14
wordCount.insert({"date", 4});
15
wordCount.emplace("elderberry", 2);
16
17
// 访问元素
18
std::cout << "apple count: " << wordCount["apple"] << "\n";
19
20
// 查找元素
21
if(wordCount.find("banana") != wordCount.end()) {
22
std::cout << "banana exists\n";
23
}
24
25
// 遍历map (C++11范围for)
26
for(const auto& [word, count] : wordCount) {
27
std::cout << word << ": " << count << "\n";
28
}
29
30
// 删除元素
31
wordCount.erase("cherry");
32
33
return 0;
34
}
std::map 常用 API 的整理表格
| 名称 | 用途 | 原型 | 代码示例 | 注释 |
|---|---|---|---|---|
insert | 插入键值对 | pair<iterator, bool> insert(const value_type& val); | map<int, string> m; m.insert({1, "one"}); | 返回一个 pair，第二个元素表示是否插入成功 |
emplace | 原地构造键值对 | pair<iterator, bool> emplace(Args&&... args); | m.emplace(2, "two"); | 避免拷贝，效率高于 insert |
operator[] | 访问或插入元素 | mapped_type& operator[](const key_type& k); | m[3] = "three"; string s = m[3]; | 若键不存在，会默认构造一个值 |
at | 安全访问元素 | mapped_type& at(const key_type& k); | string s = m.at(1); | 键不存在时抛出 std::out_of_range |
find | 查找元素 | iterator find(const key_type& k); | auto it = m.find(2); if (it != m.end()) {...} | 返回迭代器，未找到时等于 end() |
erase | 删除元素 | size_type erase(const key_type& k); | m.erase(1); | 返回删除的元素数量（0 或 1） |
clear | 清空容器 | void clear() noexcept; | m.clear(); | 容器大小变为 0 |
size | 获取元素数量 | size_type size() const noexcept; | int n = m.size(); | 时间复杂度 O(1) |
empty | 判断是否为空 | bool empty() const noexcept; | if (m.empty()) {...} | 等价于 size() == 0 |
count | 统计键出现的次数 | size_type count(const key_type& k) const; | if (m.count(2)) {...} | 对于 map 返回 0 或 1 |
lower_bound | 返回第一个不小于键的迭代器 | iterator lower_bound(const key_type& k); | auto it = m.lower_bound(3); | 用于范围查询 |
upper_bound | 返回第一个大于键的迭代器 | iterator upper_bound(const key_type& k); | auto it = m.upper_bound(3); | 常与 lower_bound 配合使用 |
equal_range | 返回匹配键的范围 | pair<iterator, iterator> equal_range(const key_type& k); | auto p = m.equal_range(3); | 返回的区间是 [lower_bound, upper_bound) |
begin/end | 获取迭代器 | iterator begin() noexcept;iterator end() noexcept; | for (auto it = m.begin(); it != m.end(); ++it) {...} | 用于遍历，begin() 指向第一个元素 |
rbegin/rend | 获取反向迭代器 | reverse_iterator rbegin() noexcept;reverse_iterator rend() noexcept; | for (auto it = m.rbegin(); it != m.rend(); ++it) {...} | 反向遍历（从大到小） |
补充说明：
- 键值对类型：
value_type是pair<const Key, T>，键（Key）不可修改。 - 时间复杂度：
- 查找/插入/删除：O(log n)（基于红黑树实现）
-begin()/end()：O(1) - 自定义排序：可通过比较函数模板参数实现，例如
std::map<int, string, std::greater<int>>。
文章目录