C++的map库作为STL标准模板库中的有序关联容器，主要用于存储和管理唯一键值对数据集合。其核心功能是通过红黑树结构自动维护键的有序性（默认升序排列），提供O(log n)时间复杂度的元素查找、插入和删除操作，支持键的唯一性约束及自定义排序规则。该容器提供键值对的快速检索（find/count）、动态更新（operator[]）、范围查询（lower_bound/upper_bound）等接口，适用于需要按键有序遍历或范围操作的场景（如字典管理、事件调度系统），但相比基于哈希表的unordered_map在插入效率上略低，以换取稳定的排序特性。

---

1. 基本概念

特点

• 有序性：std::map中的元素按键值的升序（默认）或自定义顺序存储。
• 唯一键：std::map中每个键是唯一的，不能重复。
• 自动排序：插入元素时会根据键值自动排序。
• 时间复杂度：查找、插入和删除操作的时间复杂度为 (O(\log n))，因为底层实现是平衡二叉树。

头文件

#include <map>

模板定义

template<class Key,             // 键类型class T,               // 值类型class Compare = std::less<Key>,  // 比较函数对象，默认按升序排序class Allocator = std::allocator<std::pair<const Key, T>> // 内存分配器
> class map;

---

2. 常用成员函数

构造函数

1. 默认构造函数

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

2. 范围构造函数

   std::vector<std::pair<int, std::string>> vec = {{1, "A"}, {2, "B"}};
   std::map<int, std::string> m(vec.begin(), vec.end());
   

3. 拷贝构造函数

   std::map<int, std::string> m1 = m;
   

4. 移动构造函数

   std::map<int, std::string> m2 = std::move(m1);
   

---

插入操作

1. 单个元素插入

   std::map<int, std::string> m;
   m.insert({1, "A"}); // 返回 std::pair<iterator, bool>
   

2. 使用下标操作符插入

   m[2] = "B"; // 如果键不存在，会创建新元素
   

3. 范围插入

   std::vector<std::pair<int, std::string>> vec = {{3, "C"}, {4, "D"}};
   m.insert(vec.begin(), vec.end());
   

4. 使用emplace插入

   m.emplace(5, "E"); // 更高效，避免额外的拷贝
   

---

删除操作

1. 按键删除

   m.erase(1); // 删除键为1的元素
   

2. 按迭代器删除

   auto it = m.find(2);
   if (it != m.end()) {m.erase(it);
   }
   

3. 范围删除

   m.erase(m.begin(), m.find(4)); // 删除键小于4的元素
   

---

查找操作

1. find

   auto it = m.find(3); // 返回指向键为3的迭代器或 m.end()
   

2. count

   if (m.count(3)) {std::cout << "Key 3 exists.\n";
   }
   

3. lower_bound 和 upper_bound
   • lower_bound：返回第一个不小于指定键的迭代器。
   • upper_bound：返回第一个大于指定键的迭代器。

   auto it1 = m.lower_bound(3);
   auto it2 = m.upper_bound(3);
   

4. equal_range

   auto range = m.equal_range(3); // 返回一个范围 [lower_bound, upper_bound)
   

---

访问操作

1. 通过下标访问

   std::cout << m[3]; // 如果键不存在，会插入一个默认值
   

2. 通过at访问

   std::cout << m.at(3); // 如果键不存在，会抛出异常
   

---

容量操作

1. empty

   if (m.empty()) {std::cout << "Map is empty.\n";
   }
   

2. size

   std::cout << "Size: " << m.size();
   

3. max_size

   std::cout << "Max size: " << m.max_size();
   

---

迭代器

1. 正向迭代器

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

2. 反向迭代器

   for (auto it = m.rbegin(); it != m.rend(); ++it) {std::cout << it->first << ": " << it->second << "\n";
   }
   

---

观察器

1. key_comp
   返回用于比较键的函数对象。

   auto comp = m.key_comp();
   if (comp(1, 2)) {std::cout << "1 is less than 2.\n";
   }
   

2. value_comp
   返回用于比较键值对的函数对象。

   auto comp = m.value_comp();
   if (comp({1, "A"}, {2, "B"})) {std::cout << "First pair is smaller.\n";
   }
   

---

交换和清空

1. swap

   std::map<int, std::string> m1, m2;
   m1.swap(m2);
   

2. clear

   m.clear();
   

---

3. 自定义排序

可以通过第三个模板参数Compare自定义排序规则。例如：

struct CustomCompare {bool operator()(const int& a, const int& b) const {return a > b; // 降序}
};std::map<int, std::string, CustomCompare> m;

---

4. 注意事项

1. 效率问题
   • std::map适用于需要频繁查找、插入和删除的场景，但如果只需要按键值存储，可以考虑std::unordered_map，其查找复杂度为 (O(1))。
2. 下标操作符的副作用
   • 使用m[key]访问不存在的键时，会插入一个默认值。
3. 迭代器失效
   • 插入操作不会使迭代器失效。
   • 删除操作会使指向被删除元素的迭代器失效。

---

5. 应用场景

• 存储键值对数据，例如字典、配置项等。
• 实现有序的查找表。
• 需要按键排序的场景。

---

我的追求是做一个完整的人，一个结合了完美与不完美的人。 ​ —黛比·福特