映射（关联）map
在 C++ STL（标准模板库）中，std::map 是一种关联容器，用于存储键值对。std::map 中的每个元素都由唯一的键和关联的值组成，并且根据键的顺序自动排序（默认是升序）。它基于红黑树实现，提供高效的插入、删除和查找操作。
1. 基本特点
键值对存储：
std::map中的每个元素都是一个std::pair<const Key, T>，其中Key是键，T是值。键的唯一性：
std::map中的键必须唯一，重复的键会覆盖原来的值。自动排序：
std::map中的键按照某种顺序进行排序，默认使用std::less（即按升序排序）。可以通过自定义比较器修改排序方式。底层实现：基于红黑树，确保查找、插入和删除的时间复杂度为 O(log n)。
2. 基本操作
2.1 插入操作
insert(const value_type& val)：插入键值对，如果键已经存在，则插入失败。
返回一个
pair<iterator, bool>，iterator指向插入的位置，bool表示是否成功插入。时间复杂度：O(log n)。
示例：
std::map<int, std::string> myMap; myMap.insert(std::make_pair(1, "apple")); myMap.insert({2, "banana"});
operator[]：通过键访问元素，如果键不存在，则创建一个默认值。
时间复杂度：O(log n)。
示例：
myMap[3] = "cherry"; // 如果键 3 不存在，创建并插入默认值
2.2 查找操作
find(const Key& k)：查找键
k，返回指向对应键值对的迭代器，如果未找到则返回end()。时间复杂度：O(log n)。
示例：
auto it = myMap.find(1); if (it != myMap.end()) { std::cout << "Found: " << it->second << std::endl; }
count(const Key& k)：返回键
k是否存在的数量，std::map中键是唯一的，所以返回值要么是0（不存在），要么是1（存在）。时间复杂度：O(log n)。
示例：
if (myMap.count(1) > 0) { std::cout << "Key 1 exists" << std::endl; }
2.3 删除操作
erase(iterator pos)：删除指定位置的元素，返回下一个元素的迭代器。
时间复杂度：O(log n)。
示例：
auto it = myMap.find(2); if (it != myMap.end()) { myMap.erase(it); // 删除键为 2 的元素 }
erase(const Key& k)：根据键
k删除元素，返回删除的元素数量（只能是 0 或 1）。时间复杂度：O(log n)。
示例：
myMap.erase(1); // 删除键为 1 的元素
2.4 其他操作
size()：返回
map中元素的数量。时间复杂度：O(1)。
示例：
std::cout << "Size: " << myMap.size() << std::endl; // 输出 map 中元素数量
empty()：检查
map是否为空，如果为空返回true。时间复杂度：O(1)。
示例：
if (myMap.empty()) { std::cout << "Map is empty" << std::endl; }
clear()：清除所有元素。
时间复杂度：O(n)。
示例：
myMap.clear(); // 清空 map
swap(map& other)：交换两个
map的内容。时间复杂度：O(1)。
示例：
std::map<int, std::string> myMap2; myMap.swap(myMap2); // 交换 myMap 和 myMap2 的内容
3. 遍历操作
std::map 支持使用迭代器遍历元素。
正向遍历：
for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}反向遍历：
for (auto it = myMap.rbegin(); it != myMap.rend(); ++it) {
std::cout << it->first << ": " << it->second << std::endl;
}4. 自定义排序
std::map 默认使用 std::less<Key> 作为排序准则，键按照升序排序。如果需要自定义排序，可以提供一个自定义的比较函数或函数对象。
自定义比较器示例（降序排序）：
struct Descending {
bool operator()(const int& a, const int& b) const {
return a > b;
}
};
std::map<int, std::string, Descending> myMap; // 使用降序排序5. 常用成员函数汇总
insert(const value_type& val)
插入键值对。
operator[](const Key& k)
通过键访问元素，如果不存在则插入默认值。
find(const Key& k)
查找键为 k 的元素，返回迭代器。
count(const Key& k)
返回键为 k 的元素个数（0 或 1）。
erase(const Key& k)
删除键为 k 的元素。
size()
返回元素的数量。
empty()
检查是否为空。
clear()
删除所有元素。
swap(map& other)
交换两个 map 的内容。
begin(), end()
返回正向迭代器，指向第一个元素和最后一个元素之后的位置。
rbegin(), rend()
返回反向迭代器，指向最后一个元素和第一个元素之前的位置。
6. 示例代码
#include <iostream>
#include <map>
int main() {
std::map<int, std::string> myMap;
// 插入元素
myMap.insert(std::make_pair(1, "apple"));
myMap[2] = "banana";
myMap[3] = "cherry";
// 查找元素
if (myMap.find(1) != myMap.end()) {
std::cout << "Found key 1: " << myMap[1] << std::endl;
}
// 遍历元素
for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
// 删除元素
myMap.erase(2);
// 输出删除后的 map
for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}7. 总结
std::map是一个关联容器，基于红黑树实现，键唯一且自动排序。主要操作的时间复杂度为 O(log n)，适合用于快速查找、插入和删除操作。
提供了丰富的接口用于操作键值对，并且可以自定义键的排序方式。
Last updated