当前位置：首页 > news >正文

c++ std::map

news 2025/9/20 18:26:02

c++ map

C++ 中的 std::map 是一个关联容器，用于存储 键值对（Key-Value），并根据键（Key）自动排序。其底层实现基于 红黑树，因此支持高效的插入、查找和删除操作（时间复杂度为 \(O(\log n)\)）。以下是 std::map 的使用简介：

1. 基本概念

键值对（Key-Value）：每个元素由唯一的键（Key）和对应的值（Value）组成，类似字典。
有序性：键默认按升序排列（可通过自定义比较器修改）。
唯一性：键必须是唯一的，不允许重。
应用场景：适合需要快速查找、插入和删除键值对的场景，如数据库索引、配置映射等。

2. 定义与初始化

#include <map>
#include <string>int main() {// 定义一个 map，键为 int，值为 stringstd::map<int, std::string> myMap;// 初始化方式 1：直接赋值myMap[1] = "apple";myMap[2] = "banana";// 初始化方式 2：使用 insert 插入 pairmyMap.insert(std::pair<int, std::string>(3, "cherry"));// 初始化方式 3：使用列表初始化（C++11）std::map<int, std::string> myMap2 = {{4, "date"},{5, "elderberry"}};return 0;
}

3. 插入数据

常用方法：

// 使用 operator[]
myMap[6] = "fig";// 使用 insert 插入单个元素
myMap.insert({7, "grape"});// 使用 emplace 直接构造元素（C++11）
myMap.emplace(8, "honeydew");// 批量插入（通过迭代器区间）
std::vector<std::pair<int, std::string>> vec = {{9, "kiwi"}, {10, "lemon"}};
myMap.insert(vec.begin(), vec.end());

4. 查找数据

查找键是否存在：

auto it = myMap.find(3);
if (it != myMap.end()) {std::cout << "Found: " << it->second << std::endl; // 输出 "cherry"
} else {std::cout << "Key not found!" << std::endl;
}

获取值（推荐使用 at() 避免意外插入）：

try {std::cout << myMap.at(3) << std::endl; // 输出 "cherry"
} catch (const std::out_of_range& e) {std::cout << "Key not found!" << std::endl;
}

5. 删除数据

按键删除：

myMap.erase(3); // 删除键为 3 的元素

按迭代器删除：

auto it = myMap.find(4);
if (it != myMap.end()) {myMap.erase(it);
}

批量删除：

myMap.erase(5, 7); // 删除键在 [5,7) 范围内的元素（C++20）

6. 遍历 map

使用迭代器：

for (auto it = myMap.begin(); it != myMap.end(); ++it) {std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}

使用范围 for 循环（C++11）：

for (const auto& [key, value] : myMap) {std::cout << "Key: " << key << ", Value: " << value << std::endl;
}

反向遍历：

for (auto it = myMap.rbegin(); it != myMap.rend(); ++it) {std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}

7. 其他常用操作

判断键是否存在：

bool exists = myMap.count(3) > 0; // count 返回 0 或 1

获取大小与清空：

std::cout << "Size: " << myMap.size() << std::endl;
myMap.clear(); // 清空所有元素

合并两个 map（C++17）：

std::map<int, std::string> map1 = {{1, "a"}, {2, "b"}};
std::map<int, std::string> map2 = {{3, "c"}, {2, "d"}};map1.merge(map2); // 合并 map2 到 map1，若键冲突则保留 map1 的值

8. 性能优化与注意事项

避免频繁插入/删除：
- 如果需要频繁修改键值对，考虑使用 std::unordered_map（哈希表实现，平均查找复杂度为 \(O(1)\)）。

自定义比较器：

默认按键升序排序，可通过自定义比较器实现降序或其他排序规则：

struct CompareDesc {bool operator()(int a, int b) const { return a > b; }
};
std::map<int, std::string, CompareDesc> myMap; // 按键降序排序

避免意外插入：
- 使用 at() 代替 operator[]，防止访问不存在的键时自动插入默认值。
批量插入优化：
- 使用 emplace_hint 提供插入位置的提示，减少红黑树调整次数：
```
auto hint = myMap.begin();
myMap.emplace_hint(hint, 11, "orange");
```
内存管理：
- 避免频繁拷贝大 map，可使用引用或指针传递。

9. 常见陷阱

键的不可变性：键的值不能直接修改（否则会破坏红黑树的排序结构）。若需修改键，需先删除旧键，再插入新键。
默认值插入：operator[] 在键不存在时会插入默认值，可能导致意外行为。
自定义类型的键：若键为自定义类型，需重载比较运算符或提供自定义比较器。

10. 与 `std::unordered_map` 的对比

特性	`std::map`	`std::unordered_map`
底层实现	红黑树（有序）	哈希表（无序）
查找复杂度	\(O(\log n)\)	平均 \(O(1)\)，最坏 \(O(n)\)
插入/删除复杂度	\(O(\log n)\)	平均 \(O(1)\)，最坏 \(O(n)\)
是否保持有序	是	否
适用场景	需要有序性或范围查询	需要高效率的随机访问