C++ 学习杂记05：std::map-洪萨配资

概述

std::map是 C++ 标准模板库（STL）中的一个关联容器，它存储键值对（key-value pairs），并根据键（key）自动排序。std::map通常基于红黑树（一种自平衡二叉搜索树）实现，因此能保证对数时间复杂度的查找、插入和删除操作。

基本特性

头文件：<map>
定义：template <class Key, class T, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<const Key, T>>> class map;
键唯一性：每个键在map中只能出现一次
排序：元素始终按键的升序排列（默认使用std::less<Key>）
时间复杂度：
- 查找：O(log n)
- 插入：O(log n)
- 删除：O(log n)

基本用法

1. 创建和初始化

#include <iostream> #include <map> #include <string> int main() { // 空map std::map<int, std::string> map1; // 使用初始化列表 std::map<int, std::string> map2 = { {1, "Alice"}, {2, "Bob"}, {3, "Charlie"} }; // 复制构造 std::map<int, std::string> map3(map2); // 范围构造 std::map<int, std::string> map4(map2.begin(), map2.end()); return 0; }

2. 插入元素

std::map<int, std::string> myMap; // 使用insert myMap.insert({1, "Apple"}); myMap.insert(std::make_pair(2, "Banana")); myMap.insert(std::pair<const int, std::string>(3, "Cherry")); // 使用下标运算符（如果键不存在则插入） myMap[4] = "Date"; // 插入键4，值为"Date" myMap[5] = "Elderberry"; // 使用emplace（C++11及以上） myMap.emplace(6, "Fig");

3. 访问元素

std::map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}}; // 使用下标运算符（注意：如果键不存在，会创建新元素） std::cout << myMap[1] << std::endl; // 输出: One // 使用at（如果键不存在，抛出std::out_of_range异常） try { std::cout << myMap.at(2) << std::endl; // 输出: Two } catch (const std::out_of_range& e) { std::cout << "Key not found!" << std::endl; } // 使用find（安全的方式） auto it = myMap.find(3); if (it != myMap.end()) { std::cout << it->second << std::endl; // 输出: Three }

4. 删除元素

std::map<int, std::string> myMap = { {1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"} }; // 通过迭代器删除 auto it = myMap.find(2); if (it != myMap.end()) { myMap.erase(it); } // 通过值删除 myMap.erase(3); // 删除一个范围 myMap.erase(myMap.find(4), myMap.end()); // 删除所有元素 myMap.clear();

5. 遍历元素

std::map<int, std::string> myMap = {{1, "Red"}, {2, "Green"}, {3, "Blue"}}; // 使用迭代器 for (auto it = myMap.begin(); it != myMap.end(); ++it) { std::cout << it->first << ": " << it->second << std::endl; } // 使用范围for循环（C++11及以上） for (const auto& pair : myMap) { std::cout << pair.first << ": " << pair.second << std::endl; } // 使用结构化绑定（C++17及以上） for (const auto& [key, value] : myMap) { std::cout << key << ": " << value << std::endl; }

容量查询

std::map<int, std::string> myMap = {{1, "A"}, {2, "B"}}; // 获取元素数量 std::cout << "Size: " << myMap.size() << std::endl; // 输出: 2 // 检查是否为空 std::cout << "Empty: " << std::boolalpha << myMap.empty() << std::endl; // 输出: false // 获取最大可能的大小 std::cout << "Max size: " << myMap.max_size() << std::endl;

查找操作

std::map<int, std::string> myMap = {{1, "A"}, {2, "B"}, {3, "C"}}; // find - 查找键，返回迭代器 auto it = myMap.find(2); if (it != myMap.end()) { std::cout << "Found: " << it->second << std::endl; } // count - 检查键是否存在（对于map，返回0或1） if (myMap.count(3) > 0) { std::cout << "Key 3 exists" << std::endl; } // lower_bound - 返回第一个不小于key的元素的迭代器 auto lb = myMap.lower_bound(2); if (lb != myMap.end()) { std::cout << "Lower bound: " << lb->first << " -> " << lb->second << std::endl; } // upper_bound - 返回第一个大于key的元素的迭代器 auto ub = myMap.upper_bound(2); if (ub != myMap.end()) { std::cout << "Upper bound: " << ub->first << " -> " << ub->second << std::endl; } // equal_range - 返回匹配键的范围 auto range = myMap.equal_range(2); for (auto i = range.first; i != range.second; ++i) { std::cout << i->first << " -> " << i->second << std::endl; }

自定义比较函数

#include <iostream> #include <map> #include <string> // 自定义比较函数 - 按字符串长度排序 struct StringLengthCompare { bool operator()(const std::string& a, const std::string& b) const { return a.length() < b.length(); } }; int main() { // 使用自定义比较函数 std::map<std::string, int, StringLengthCompare> lengthMap; lengthMap.insert({"apple", 5}); lengthMap.insert({"kiwi", 4}); lengthMap.insert({"banana", 6}); for (const auto& pair : lengthMap) { std::cout << pair.first << ": " << pair.second << std::endl; } return 0; }

性能注意事项

时间复杂度：
- 查找、插入、删除：O(log n)
- 遍历：O(n)
空间复杂度：O(n)，每个元素需要额外的指针空间（通常每个节点需要3个指针）
与std::unordered_map对比：
- std::map：有序，基于红黑树，O(log n)操作
- std::unordered_map：无序，基于哈希表，平均O(1)操作，最坏O(n)
使用场景：
- 需要有序遍历
- 元素数量相对稳定
- 键的比较操作开销不大
- 内存使用不是主要限制

线程安全性

多个线程可以同时读取同一个std::map对象
如果有任何线程修改std::map，必须确保没有其他线程同时访问该对象
对于多线程环境，考虑使用互斥锁或并发容器（如Intel TBB的concurrent_hash_map）

最佳实践

避免频繁的插入删除：如果频繁操作，考虑std::unordered_map
使用emplace替代insert：避免不必要的临时对象创建
使用find而不是operator[]检查存在性：operator[]会插入不存在的键
考虑使用std::unordered_map：当不需要有序遍历时
使用auto简化迭代器声明：提高代码可读性

示例应用

#include <iostream> #include <map> #include <string> class StudentDatabase { private: std::map<int, std::string> students; public: void addStudent(int id, const std::string& name) { auto result = students.emplace(id, name); if (!result.second) { std::cout << "Student with ID " << id << " already exists!" << std::endl; } } bool removeStudent(int id) { return students.erase(id) > 0; } std::string getStudentName(int id) const { auto it = students.find(id); if (it != students.end()) { return it->second; } return "Student not found"; } void listAllStudents() const { if (students.empty()) { std::cout << "No students in database." << std::endl; return; } std::cout << "Student List (sorted by ID):" << std::endl; for (const auto& [id, name] : students) { std::cout << "ID: " << id << ", Name: " << name << std::endl; } } size_t getStudentCount() const { return students.size(); } }; int main() { StudentDatabase db; db.addStudent(1001, "Alice Johnson"); db.addStudent(1003, "Bob Smith"); db.addStudent(1002, "Charlie Brown"); db.listAllStudents(); std::cout << "\nStudent 1002: " << db.getStudentName(1002) << std::endl; db.removeStudent(1002); std::cout << "\nAfter removing student 1002:" << std::endl; db.listAllStudents(); return 0; }