C++ std::map 容器详解

std::map 是 C++ 标准模板库（STL）中的关联容器，存储 键值对（key-value pairs），提供高效的查找、插入和删除操作（时间复杂度 O(log n)）。基于红黑树实现，元素按键 自动排序。

---

1. 基本特性

• 唯一键：每个键只能在 map 中出现一次
• 排序：元素按键的升序排列（默认）
• 头文件：#include <map>
• 声明：std::map<KeyType, ValueType> mapName;

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<int, std::string> studentMap;  // 键:学号(int), 值:姓名(string)
    return 0;
}

补充

std::pair 类模板简介

std::pair 是 C++ 标准库中的一个基础类模板，用于将两个值组合成一个单元（类似二元组）。它在关联容器（如 std::map）中扮演核心角色，用于存储键值对。

基本结构

template <class T1, class T2>
struct pair {
    T1 first;   // 第一个元素
    T2 second;  // 第二个元素
    
    // 构造函数和其他成员函数...
};

核心特性

1. 简单封装：将两个任意类型的值组合成单一实体
2. 公有成员：直接通过 first 和 second 访问元素
3. 头文件：#include <utility>（或间接通过 <map> 引入）

---

创建与使用示例

#include <iostream>
#include <utility>  // 包含 pair 的定义

int main() {
    // 方法1：直接构造
    std::pair<int, std::string> student(101, "Alice");
    std::cout << "ID: " << student.first 
              << ", Name: " << student.second << "\n";
    // 输出: ID: 101, Name: Alice

    // 方法2：使用 make_pair（自动推导类型）
    auto product = std::make_pair("iPhone", 999.99);
    std::cout << product.first << " costs $" << product.second << "\n";
    // 输出: iPhone costs $999.99

    // 方法3：C++11 统一初始化
    std::pair coordinates{3.5, -2.7};  // 推导为 pair<double, double>
    coordinates.second = 4.2;  // 修改第二个元素

    return 0;
}

---

在 std::map 中的关键作用

std::map 中的每个元素实际上都是 std::pair<const Key, Value> 类型：

#include <map>
#include <string>

int main() {
    std::map<int, std::string> employees = {
        {1001, "Alice"},  // 每个 {} 初始化一个 pair
        {1002, "Bob"}
    };

    // 遍历时得到 pair 对象
    for (const auto& entry : employees) {
        // entry 是 pair<const int, string>
        std::cout << "ID: " << entry.first 
                  << ", Name: " << entry.second << "\n";
    }
    
    // 插入新元素需要 pair
    employees.insert(std::make_pair(1003, "Charlie"));
    
    return 0;
}

---

主要应用场景

1. 从函数返回两个值：

   std::pair<bool, std::string> validateUser(int id) {
       if (id > 0) return {true, "Valid"};
       return {false, "Invalid ID"};
   }
   

2. 存储键值对（用于 map/unordered_map）

3. 比较操作：

   std::pair<int, int> p1{1, 2}, p2{3, 4};
   std::cout << (p1 < p2);  // 输出 1 (true)，按 first 优先比较
   

---

结构化绑定（C++17）

现代 C++ 支持直接解构 pair：

std::pair<std::string, int> player{"Ronaldo", 7};

// 直接绑定到变量
auto [name, number] = player;
std::cout << name << " wears #" << number;
// 输出: Ronaldo wears #7

---

总结

std::pair 是 C++ 中最简单的复合数据类型：

• 将两个值组合成单一实体
• 提供直接访问的 first 和 second 成员
• 是关联容器的底层构建块
• 支持现代 C++ 的解构语法

理解 pair 是掌握 std::map 和其他关联容器的关键基础，因为所有键值对操作都基于这个基本结构。

---

2. 初始化与赋值

// 默认初始化
std::map<int, std::string> m1;

// 初始化列表 (C++11)
std::map<int, std::string> m2 = {
    {1, "Alice"},
    {2, "Bob"},
    {3, "Charlie"}
};

// 拷贝构造
std::map<int, std::string> m3(m2);

// 范围构造
int keys[] = {5, 6, 7};
std::string vals[] = {"Dave", "Eve", "Frank"};
std::map<int, std::string> m4;
for (int i = 0; i < 3; ++i) {
    m4[keys[i]] = vals[i];
}

---

3. 元素访问

下标操作符 []

• 若键存在：返回对应值的引用
• 若键不存在：创建新键值对（值默认初始化）

std::map<char, int> charCount;
charCount['a'] = 5;   // 插入 {'a':5}
charCount['b']++;     // 插入 {'b':1}（int 默认值0）

std::cout << charCount['a'];  // 输出 5
std::cout << charCount['c'];  // 输出 0（创建了 {'c':0}）

---

---

---

后面我们复现map的时候还会重新再讲一遍的，这里大家也只是粗略的先理解一下。

at() 方法

• 键存在：返回对应值的引用
• 键不存在：抛出 std::out_of_range 异常

std::map<int, std::string> m = {{1, "Apple"}, {2, "Banana"}};
std::cout << m.at(1);  // "Apple"
// m.at(3);  // 抛出异常

---

4. 插入元素

insert()

• 插入单个元素或范围
• 返回 pair<iterator, bool>：迭代器指向元素，bool 表示是否插入成功

std::map<int, std::string> countryCodes;

// 插入单个元素
auto ret = countryCodes.insert({86, "China"});
if (ret.second) {
    std::cout << "插入成功！\n";
}

// 使用 make_pair
countryCodes.insert(std::make_pair(91, "India"));

// 插入多个元素 (C++11)
countryCodes.insert({{1, "USA"}, {81, "Japan"}});

// 插入结果检查
auto [it, success] = countryCodes.insert({86, "X"});  // 键86已存在
std::cout << "插入是否成功: " << success;  // 输出 0 (false)

emplace()

• 直接构造元素（避免临时对象复制）

countryCodes.emplace(33, "France");  // 等价于 insert({33, "France"})

---

5. 删除元素

erase()

• 按键删除：返回删除的元素数量（0或1）
• 按迭代器删除：返回下一个元素的迭代器
• 按范围删除：erase(begin, end)

std::map<int, std::string> m = {
    {1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}
};

// 按键删除
size_t n = m.erase(2);  // n=1

// 按迭代器删除
auto it = m.find(3);
if (it != m.end()) {
    it = m.erase(it);  // it 指向 {4, "D"}
}

// 删除范围
m.erase(m.begin(), m.end());  // 清空map

---

6. 查找元素

find()

• 返回指向元素的迭代器，若未找到则返回 end()

std::map<std::string, int> population = {
    {"Beijing", 2154}, 
    {"Shanghai", 2424}
};

auto it = population.find("Shanghai");
if (it != population.end()) {
    std::cout << "上海人口: " << it->second << "万\n";
} else {
    std::cout << "未找到数据\n";
}

count()

• 返回键出现的次数（0或1）

if (population.count("Tokyo") > 0) {
    std::cout << "找到东京数据\n";
} else {
    std::cout << "无东京数据\n";  // 输出此句
}

contains() (C++20)

• 直接返回 bool 表示键是否存在

if (population.contains("Beijing")) {
    std::cout << "包含北京数据\n";  // 输出此句
}

---

7. 遍历元素

迭代器遍历

std::map<int, std::string> m = {{10, "Ten"}, {20, "Twenty"}};

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

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

范围 for 循环

for (const auto& [key, value] : m) {  // C++17 结构化绑定
    std::cout << key << " = " << value << "\n";
}

---

8. 容量与状态查询

std::map<int, double> data = {{1, 1.1}, {2, 2.2}};

// 元素数量
std::cout << "元素个数: " << data.size() << "\n";  // 2

// 是否为空
std::cout << "是否为空: " << data.empty() << "\n";  // 0 (false)

// 最大可能元素数量
std::cout << "最大容量: " << data.max_size() << "\n";  // 极大值

---

9. 比较与交换

swap()

• 交换两个 map 的内容（高效，常数时间）

std::map<int, char> map1 = {{1, 'a'}, {2, 'b'}};
std::map<int, char> map2 = {{3, 'c'}};
map1.swap(map2);  // map1 变为 {{3,'c'}}, map2 变为 {{1,'a'}, {2,'b'}}

比较运算符

• 按字典序比较键值对

std::map<int, int> a = {{1,10}, {2,20}};
std::map<int, int> b = {{1,10}, {2,20}};
std::cout << (a == b);  // 1 (true)

---

10. 自定义排序规则

通过提供比较函数对象实现：

// 按字符串长度排序
struct LengthCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.length() < b.length();
    }
};

std::map<std::string, int, LengthCompare> lenMap = {
    {"apple", 1}, {"kiwi", 2}, {"banana", 3}
};

// 输出顺序: kiwi -> apple -> banana
for (const auto& [k, v] : lenMap) {
    std::cout << k << " ";  
}

---

11. 性能与复杂度

操作	时间复杂度	说明
插入/删除	O(log n)	红黑树平衡操作
查找	O(log n)	二分查找
遍历	O(n)	线性遍历所有元素
begin()/end()	O(1)	获取首尾迭代器

---

12. 典型应用场景

1. 字典/查找表：单词翻译、配置项存储

   std::map<std::string, std::string> dict = {{"hello", "你好"}, {"world", "世界"}};
   

2. 计数器：统计元素出现频率

   std::map<char, int> charFreq;
   for (char c : "programming") {
       charFreq[c]++;
   }
   

3. 索引系统：通过ID快速检索对象

   std::map<int, Employee> employeeDB;
   employeeDB[101] = Employee("Alice");
   

---

注意事项

1. 键的不可变性：通过迭代器修改键会导致未定义行为

   auto it = m.begin();
   // it->first = 100;  // 错误！键不可修改
   it->second = "New Value";  // 允许修改值
   

2. 迭代器失效：删除元素会使指向该元素的迭代器失效
3. 内存占用：每个元素需要额外存储红黑树的节点信息（比 std::vector 占用更多内存）
4. 替代方案：
   • 无需排序：用 std::unordered_map（哈希表，O(1) 平均查找）
   • 允许重复键：用 std::multimap

---

总结

std::map 是 C++ 中强大的有序关联容器，适用于需要按键排序和高效查找的场景。通过合理使用其接口，可以构建高性能的关键字检索系统。