Map

---

map 的全部方法

方法	说明
构造函数	创建 map 容器，支持多种初始化方式。
empty()	检查容器是否为空。
size()	返回容器中元素的数量。
clear()	清空容器中的所有元素。
insert()	插入单个元素或范围。
erase()	按键或迭代器删除元素。
find()	查找指定键的迭代器。
count()	返回指定键的数量（始终为 0 或 1）。
at()	访问指定键对应的值，不存在时抛出异常。
operator[]	访问或插入指定键的值。
swap()	交换两个 map 容器的内容。
lower_bound()	返回第一个不小于指定键的迭代器。
upper_bound()	返回第一个大于指定键的迭代器。
equal_range()	返回一对迭代器，表示键的范围。
emplace()	原地构造并插入元素。
key_comp()	返回键比较函数对象。
value_comp()	返回值比较函数对象。

---

1. 添加和删除元素的方法

1.1 insert

• 功能：在 map 中插入键值对。

• 返回值：pair<iterator, bool>，表示插入的元素位置和插入是否成功。

• 示例：

  #include <map>
  #include <iostream>
  using namespace std;
  
  int main() {
      map<int, string> m;
      auto result = m.insert({1, "one"});
      cout << "Inserted: " << result.second << endl; // 输出：Inserted: 1
  
      // 插入失败（键已存在）
      result = m.insert({1, "uno"});
      cout << "Inserted: " << result.second << endl; // 输出：Inserted: 0
      return 0;
  }

---

1.2 emplace

• 功能：原地构造并插入一个元素。

• 返回值：与 insert 类似。

• 示例：

  m.emplace(2, "two");

---

1.3 erase

• 功能：删除指定键或迭代器位置的元素。

• 返回值：无（迭代器版）或删除的元素数量（按键删除）。

• 示例：

  m.erase(1);               // 按键删除
  m.erase(m.begin());       // 按迭代器删除

---

1.4 clear

• 功能：清空 map 中的所有元素。

• 示例：

  m.clear();

---

1.5 swap

• 功能：交换两个 map 容器的内容。

• 示例：

  map<int, string> m1{{1, "one"}}, m2{{2, "two"}};
  m1.swap(m2);

---

2. 查找元素的方法

2.1 find

• 功能：返回指定键的迭代器；如果键不存在，返回 end()。

• 示例：

  auto it = m.find(1);
  if (it != m.end()) {
      cout << "Found: " << it->second << endl;
  }

---

2.2 count

• 功能：判断指定键是否存在。

• 返回值：1 表示键存在，0 表示不存在。

• 示例：

  if (m.count(2)) {
      cout << "Key exists" << endl;
  }

---

2.3 lower_bound

• 功能：返回第一个不小于指定键的迭代器。

• 示例：

  auto it = m.lower_bound(1);

---

2.4 upper_bound

• 功能：返回第一个大于指定键的迭代器。

• 示例：

  auto it = m.upper_bound(1);

---

2.5 equal_range

• 功能：返回键的上下界迭代器对。

• 示例：

  auto range = m.equal_range(1);
  for (auto it = range.first; it != range.second; ++it) {
      cout << it->first << ": " << it->second << endl;
  }

---

3. 遍历 map 的方法

3.1 迭代器遍历

• 功能：通过迭代器遍历 map。

• 示例：

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

---

3.2 范围循环

• 功能：使用 range-based for 遍历。

• 示例：

  for (const auto &pair : m) {
      cout << pair.first << ": " << pair.second << endl;
  }

---

4. 其他方法

4.1 at

• 功能：访问指定键的值，若键不存在则抛出异常。

• 示例：

  cout << m.at(1) << endl;

---

4.2 operator[]

• 功能：访问或插入键对应的值；如果键不存在，会创建默认值。

• 示例：

  m[3] = "three";

---

4.3 size

• 功能：返回 map 中元素的数量。

• 示例：

  cout << m.size() << endl;

---

4.4 empty

• 功能：检查 map 是否为空。

• 示例：

  if (m.empty()) {
      cout << "Map is empty" << endl;
  }

---

完整示例

#include <map>
#include <iostream>
using namespace std;

int main() {
    map<int, string> m;

    // 插入元素
    m.insert({1, "one"});
    m[2] = "two";

    // 遍历
    for (const auto &pair : m) {
        cout << pair.first << ": " << pair.second << endl;
    }

    // 查找
    if (m.count(1)) {
        cout << "Key 1 exists with value: " << m[1] << endl;
    }

    // 删除
    m.erase(1);
    cout << "Size after deletion: " << m.size() << endl;

    return 0;
}

unordered_map与map的不同

std::unordered_map 和 std::map 都是 C++ 中的关联容器（associative containers），但它们之间有几个重要的区别，主要体现在元素的存储方式、查找效率和遍历顺序等方面：

1. 底层数据结构

• std::map: 使用 红黑树（一种平衡的二叉查找树）作为底层数据结构。所有的元素按照 键的顺序 自动排序（默认按照 < 运算符排序）。
• std::unordered_map: 使用 哈希表 作为底层数据结构。元素的存储顺序是 无序的，它通过哈希函数将键映射到桶中。

2. 元素顺序

• std::map: 自动根据键的顺序排列元素，保持键值的升序（可以自定义排序规则）。
• std::unordered_map: 元素的顺序是 无序的，插入的顺序可能和遍历时的顺序不同。

3. 查找效率

• std::map: 查找、插入、删除操作的时间复杂度为 **O(log n)**，因为它是基于红黑树实现的，所有操作都需要遍历树。
• std::unordered_map: 查找、插入、删除操作的平均时间复杂度为 **O(1)**，但是在最坏情况下（哈希冲突较多时），它的复杂度可能退化到 **O(n)**。

4. 内存使用

• std::map: 因为是基于红黑树实现的，它需要更多的内存来存储节点指针等结构信息。
• std::unordered_map: 由于使用哈希表，它的内存开销可能更大，尤其是在哈希桶数量较多时。

5. 接口和功能

• std::map: 支持元素的有序遍历，可以使用 lower_bound、upper_bound 等方法进行区间查找。
• std::unordered_map: 不支持基于顺序的遍历，主要通过哈希函数提供对元素的快速查找。

6. 元素的键比较方式

• std::map: 使用键的比较函数来确定元素的顺序，默认使用 < 运算符。
• std::unordered_map: 使用哈希函数来计算键的哈希值，因此不需要键的比较函数。

示例：std::map 和 std::unordered_map 的对比

std::map 示例

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> m;
    m[3] = "three";
    m[1] = "one";
    m[2] = "two";

    // 遍历输出时，元素按键的顺序排列
    for (const auto& pair : m) {
        std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    return 0;
}

输出：

1 -> one
2 -> two
3 -> three

std::unordered_map 示例

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> um;
    um[3] = "three";
    um[1] = "one";
    um[2] = "two";

    // 遍历输出时，元素的顺序是无序的
    for (const auto& pair : um) {
        std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    return 0;
}

输出：

1 -> one
2 -> two
3 -> three

（输出顺序可能不同）

总结

• 如果你需要元素按某种顺序排列（如升序或降序），并且查找操作的效率要求较高，可以使用 std::map。
• 如果你更关注插入、查找和删除操作的 平均 O(1) 时间复杂度，且不需要有序存储元素，则 std::unordered_map 是更合适的选择。