map、unordered_map、set 和 unordered_set的小介绍

1. map

• 简介：

  map 是 C++ STL 中的关联容器，存储键值对（key-value pair），所有元素按 键值升序（或自定义排序）存储。

• 主要特性：

  1. 底层实现：使用 红黑树 实现，提供了自动排序功能。

  2. 元素有序：插入元素后，按键值排序。

  3. 时间复杂度：插入、删除、查找：O(logn)（因为树的深度为 O(logn) ）。

  4. 内存占用：较小（相比 unordered_map，红黑树的实现比哈希表节省内存）。

  5. 迭代器：提供双向迭代器，支持正向和反向遍历。

• 常见用法：

  • 存储有序键值对。

  • 查找某个范围内的键值。

• 举一个例子

  #include <map>
  #include <iostream>
  using namespace std;
  
  int main() {
      map<int, string> m;
      m[3] = "C";
      m[1] = "A";
      m[2] = "B";
  
      // 遍历输出
      cout << "map contents:\n";
      for (auto it : m) {
          cout << it.first << ": " << it.second << endl;
      }
  
      // 查找
      auto it = m.find(2); // 返回指向键为2的迭代器
      if (it != m.end()) {
          cout << "Found key 2: " << it->second << endl;
      }
  }
  

  输出如下：

  

2. unordered_map

• 简介：

  unordered_map 是 C++ STL 中的无序关联容器，用于存储键值对。其底层实现是 哈希表。

• 主要特性：

  1. 底层实现：

  2. 使用哈希表，元素存储位置基于键的哈希值。

  3. 元素无序：元素存储顺序与插入顺序、键值大小无关。

  4. 时间复杂度：插入、删除、查找：平均 O(1)，最坏

     标签：map,set,键值,哈希,include,unordered
     From： https://www.cnblogs.com/hisun9/p/18553445