C++里面的map结构

### C++ 中 `std::map` 的使用方法和特性 #### 定义与初始化 `std::map` 是一个关联容器，用于存储键值对（key-value pairs），并根据键自动排序。默认情况下，键是按照升序排列的。以下是定义和初始化 `std::map` 的几种方式： ```cpp #include <iostream> #include <map> int main() { // 默认定义格式（默认按 key 升序存储） std::map<int, std::string> myMap; // 指定数据按 key 升序存储 std::map<int, std::string, std::less<int>> myMap1; // 指定数据按 key 降序存储 std::map<int, std::string, std::greater<int>> myMap2; // 使用初始化列表直接初始化 map std::map<int, std::string> employeeMap = { {1, "Alice"}, {2, "Bob"}, {3, "Charlie"} }; return 0; } ``` #### 插入元素 向 `std::map` 中插入元素有多种方法，包括使用 `insert` 函数、`emplace` 函数以及直接赋值操作符 `[]`。 ```cpp std::map<int, std::string> myMap; // 使用 insert 函数插入键值对 myMap.insert(std::make_pair(1, "Apple")); // 使用 emplace 函数插入键值对 myMap.emplace(2, "Banana"); // 使用 [] 运算符插入或更新键值对 myMap[3] = "Cherry"; ``` #### 遍历 `std::map` `std::map` 支持正序和倒序遍历。正序遍历时，元素按照键的升序排列；倒序遍历时，元素按照键的降序排列。 ##### 正序遍历 ```cpp for (const auto& pair : myMap) { std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl; } ``` ##### 倒序遍历 ```cpp for (auto it = myMap.rbegin(); it != myMap.rend(); ++it) { std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl; } ``` #### 查找元素 `std::map` 提供了高效的查找功能，可以通过 `find` 方法来查找特定的键。 ```cpp auto it = myMap.find(2); if (it != myMap.end()) { std::cout << "Found: Key: " << it->first << ", Value: " << it->second << std::endl; } else { std::cout << "Key not found" << std::endl; } ``` #### 删除元素 删除 `std::map` 中的元素可以使用 `erase` 方法，既可以删除单个键值对，也可以删除范围内的所有元素。 ```cpp // 删除指定键的元素 myMap.erase(2); // 删除迭代器指向的元素 auto it = myMap.find(1); if (it != myMap.end()) { myMap.erase(it); } // 删除某个范围内的元素 myMap.erase(myMap.begin(), myMap.end()); ``` #### 特性 - **有序性**：`std::map` 内部使用红黑树实现，因此它的元素总是按照键的顺序排列[^3]。 - **时间复杂度**：插入、删除和查找操作的时间复杂度为 $O(\log N)$，其中 $N$ 是容器中的元素数量[^3]。 - **内存占用**：相比 `std::unordered_map`，`std::map` 的内存占用较低，因为它不需要预先分配大量内存来存储哈希表。 - **适用场景**：当需要有序的数据存储或者对内存大小敏感时，应选择 `std::map`；如果追求更高的查找效率，则可以选择 `std::unordered_map`。