C++ map set

### C++ 中 `map` 和 `set` 的用法与区别 #### 定义与基本概念 在 C++ 标准库中，`std::map` 是一种关联容器，用于存储键值对（key-value pairs），其中键是唯一的，并按照特定顺序排列。而 `std::set` 则是一种只存储唯一键的集合容器[^1]。 #### 数据结构基础 - **`std::map`**: 基于平衡二叉树实现（通常是红黑树）。它允许快速查找、插入和删除操作，时间复杂度为 O(log n)。 - **`std::set`**: 同样基于平衡二叉树实现。它的主要功能是用来维护一组不重复的元素，并保持这些元素有序。 #### 使用方法对比 以下是两者的典型使用方式： ##### `std::map` ```cpp #include <iostream> #include <map> int main() { std::map<int, std::string> myMap; // 插入数据 myMap[1] = "one"; myMap[2] = "two"; // 查找数据 if (myMap.find(1) != myMap.end()) { std::cout << "Key 1 found with value: " << myMap[1] << std::endl; } // 遍历 map for (const auto& pair : myMap) { std::cout << pair.first << ": " << pair.second << std::endl; } } ``` ##### `std::set` ```cpp #include <iostream> #include <set> int main() { std::set<int> mySet; // 插入数据 mySet.insert(3); mySet.insert(1); // 查找数据 if (mySet.find(3) != mySet.end()) { std::cout << "Element 3 exists in the set." << std::endl; } // 遍历 set for (const int element : mySet) { std::cout << element << std::endl; } } ``` #### 主要差异总结 | 特性 | `std::map` | `std::set` | |-----------------|------------------------------------|-----------------------------------| | 存储的内容 | 键值对 | 单一的键 | | 是否有重复 | 不允许相同的键 | 不允许相同元素 | | 访问速度 | 对应键访问速度快 | 只能通过迭代器遍历 | | 底层实现 | 平衡二叉搜索树 | 平衡二叉搜索树 | #### 性能考量 由于两者都依赖于平衡二叉树结构，因此它们的时间复杂度相似，在大多数情况下均为 O(log n)，适用于需要频繁查询的数据集。 #### 实际应用案例 当需要管理具有唯一标识符的对象及其属性时可以选用 `std::map`；如果仅需保存一系列无序但互异项，则更适合采用 `std::set` 来简化程序逻辑并提高效率。