编辑“︁C++map”︁

{{DISPLAYTITLE:C++ map}}
'''C++ map''' 是 [[C++标准模板库|C++ STL]] 中的一个关联容器，它存储由键值（key）和映射值（value）组成的元素，并根据键自动排序。map 通常实现为红黑树，因此其查找、插入和删除操作的时间复杂度均为 <math>O(\log n)</math>。map 中的每个键都是唯一的，如果尝试插入重复键，新值将覆盖旧值。

== 基本特性 ==
* '''键值对存储'''：每个元素是一个 pair 对象，包含 key 和 value
* '''自动排序'''：元素按 key 的升序排列（默认使用 <code>std::less<Key></code>）
* '''唯一键'''：容器中不允许有重复的 key
* '''高效查找'''：基于红黑树实现，查找效率为对数时间

== 头文件 ==
使用 map 需要包含头文件：
<syntaxhighlight lang="cpp">
#include <map>
</syntaxhighlight>

== 基本操作 ==
=== 声明与初始化 ===
<syntaxhighlight lang="cpp">
// 空map
std::map<std::string, int> wordCount;

// 初始化列表
std::map<int, std::string> idToName = {
    {1, "Alice"},
    {2, "Bob"},
    {3, "Charlie"}
};
</syntaxhighlight>

=== 插入元素 ===
有三种主要插入方式：
<syntaxhighlight lang="cpp">
std::map<int, std::string> m;

// 1. 使用insert和pair
m.insert(std::pair<int, std::string>(4, "David"));

// 2. 使用insert和make_pair
m.insert(std::make_pair(5, "Eve"));

// 3. 使用下标操作符
m[6] = "Frank";  // 如果键不存在会自动创建
</syntaxhighlight>

=== 访问元素 ===
<syntaxhighlight lang="cpp">
std::map<int, std::string> m = {{1, "Apple"}, {2, "Banana"}};

// 使用下标操作符（键不存在时会创建）
std::cout << m[1] << std::endl;  // 输出: Apple

// 使用at方法（键不存在时抛出异常）
std::cout << m.at(2) << std::endl;  // 输出: Banana

// 使用find方法（安全访问）
auto it = m.find(3);
if (it != m.end()) {
    std::cout << it->second << std::endl;
} else {
    std::cout << "Key not found" << std::endl;
}
</syntaxhighlight>

=== 删除元素 ===
<syntaxhighlight lang="cpp">
std::map<int, std::string> m = {{1, "A"}, {2, "B"}, {3, "C"}};

// 通过键删除
m.erase(2);  // 删除键为2的元素

// 通过迭代器删除
auto it = m.find(3);
if (it != m.end()) {
    m.erase(it);
}

// 删除所有元素
m.clear();
</syntaxhighlight>

== 迭代器 ==
map 提供双向迭代器：
<syntaxhighlight lang="cpp">
std::map<int, std::string> m = {{1, "One"}, {2, "Two"}, {3, "Three"}};

// 正向迭代
for (auto it = m.begin(); it != m.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

// 反向迭代
for (auto rit = m.rbegin(); rit != m.rend(); ++rit) {
    std::cout << rit->first << ": " << rit->second << std::endl;
}

// 范围for循环（C++11）
for (const auto& pair : m) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}
</syntaxhighlight>

== 容量查询 ==
<syntaxhighlight lang="cpp">
std::map<int, int> m = {{1, 10}, {2, 20}};

std::cout << "Size: " << m.size() << std::endl;      // 输出: 2
std::cout << "Empty: " << m.empty() << std::endl;    // 输出: 0 (false)
std::cout << "Max size: " << m.max_size() << std::endl;
</syntaxhighlight>

== 性能分析 ==
<mermaid>
gantt
    title map操作时间复杂度
    dateFormat  X
    axisFormat %s
    section 操作
    查找 : 0, 5
    插入 : 5, 10
    删除 : 10, 15
</mermaid>

* 查找：<math>O(\log n)</math>
* 插入：<math>O(\log n)</math>
* 删除：<math>O(\log n)</math>

== 实际应用案例 ==
=== 单词统计 ===
<syntaxhighlight lang="cpp">
#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> wordCount;
    std::string word;
    
    while (std::cin >> word) {
        ++wordCount[word];  // 自动初始化不存在的键为0
    }
    
    // 输出统计结果（按字母顺序）
    for (const auto& pair : wordCount) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    return 0;
}
</syntaxhighlight>

输入：
<pre>
apple banana apple cherry banana apple
</pre>

输出：
<pre>
apple: 3
banana: 2
cherry: 1
</pre>

=== 学生成绩管理系统 ===
<syntaxhighlight lang="cpp">
#include <iostream>
#include <map>
#include <string>

class Student {
public:
    std::string name;
    int score;
    
    Student(std::string n, int s) : name(n), score(s) {}
};

int main() {
    std::map<int, Student> studentMap;
    
    // 添加学生（学号为键）
    studentMap.insert({1001, Student("Alice", 95)});
    studentMap[1002] = Student("Bob", 88);
    studentMap[1003] = Student("Charlie", 92);
    
    // 查询学生成绩
    int id = 1002;
    auto it = studentMap.find(id);
    if (it != studentMap.end()) {
        std::cout << "Student " << it->second.name 
                  << " (ID: " << it->first 
                  << ") has score: " << it->second.score << std::endl;
    } else {
        std::cout << "Student not found!" << std::endl;
    }
    
    return 0;
}
</syntaxhighlight>

输出：
<pre>
Student Bob (ID: 1002) has score: 88
</pre>

== 高级特性 ==
=== 自定义比较函数 ===
可以自定义键的排序规则：
<syntaxhighlight lang="cpp">
struct CaseInsensitiveCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::lexicographical_compare(
            a.begin(), a.end(),
            b.begin(), b.end(),
            [](char c1, char c2) { return tolower(c1) < tolower(c2); }
        );
    }
};

int main() {
    std::map<std::string, int, CaseInsensitiveCompare> wordMap;
    
    wordMap["Apple"] = 1;
    wordMap["banana"] = 2;
    wordMap["apple"] = 3;  // 会覆盖"Apple"
    
    for (const auto& pair : wordMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    return 0;
}
</syntaxhighlight>

输出：
<pre>
apple: 3
banana: 2
</pre>

=== 与unordered_map比较 ===
{| class="wikitable"
|+ map vs unordered_map
! 特性 !! map !! unordered_map
|-
| 实现方式 || 红黑树 || 哈希表
|-
| 排序 || 按键排序 || 无序
|-
| 查找时间 || <math>O(\log n)</math> || 平均<math>O(1)</math>，最坏<math>O(n)</math>
|-
| 内存使用 || 通常较少 || 通常较多
|-
| 迭代顺序 || 按键排序 || 不确定
|}

== 常见问题 ==
=== 为什么使用map而不是vector<pair>? ===
* map 保证元素按键排序
* map 提供高效的查找操作（<math>O(\log n)</math> vs vector的<math>O(n)</math>）
* map 提供方便的键值访问接口

=== 如何选择map还是unordered_map? ===
* 需要有序数据 → 选择 map
* 需要最高效的查找 → 选择 unordered_map
* 内存受限 → 考虑 map
* 需要频繁遍历 → 两者均可，取决于是否需要有序

== 总结 ==
C++ map 是一个强大的关联容器，它：
* 存储键值对并自动排序
* 提供高效的查找、插入和删除操作
* 保证键的唯一性
* 适用于需要按键快速查找和有序遍历的场景

掌握 map 的使用是 C++ 程序员的重要技能，它在许多实际应用中都能发挥重要作用，如配置管理、数据索引和统计等场景。

[[Category:编程语言]]
[[Category:C++]]
[[Category:C++stl 容器]]