移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——13.map&&set(无习题）

C++ 中的 set 和 map 容器详细总结

1. 概述

C++ 标准模板库（STL）提供了多种关联容器，用于管理键值对和集合的数据。其中，set 和 map 是最常用的两种关联容器。set 用于存储唯一的元素集合，而 map 则用于存储键值对，其中每个键都是唯一的。它们都使用红黑树（自平衡二叉搜索树）作为底层实现，因此可以提供高效的插入、查找和删除操作。本文将详细介绍 set 和 map 容器的特点、使用方法、底层机制及其应用场景。

2. set 容器

2.1 什么是 set？

set 是一种关联容器，用于存储唯一的、有序的元素集合。与 vector 等序列容器不同，set 中的元素按一定顺序（通常为升序）存储，并且不允许重复元素。由于 set 使用红黑树实现，因此它的插入、查找和删除操作的时间复杂度为 O(log n)。

2.2 set 的特点

• 元素唯一性：set 中的元素必须是唯一的，不能有重复元素。
• 有序性：set 中的元素默认按升序存储，用户可以自定义排序规则。
• 高效的查找：set 提供高效的查找、插入和删除操作，时间复杂度为 O(log n)。
• 自动排序：元素在插入时会自动按顺序排列。

2.3 set 的常用操作

• 插入元素：可以使用 insert() 函数将元素插入到 set 中。

#include <set>
#include <iostream>

int main() {
    std::set<int> s;
    s.insert(10);
    s.insert(5);
    s.insert(20);
    s.insert(10);  // 重复元素不会插入

    for (int val : s) {
        std::cout << val << " ";  // 输出：5 10 20
    }
    return 0;
}

• 删除元素：可以使用 erase() 函数删除指定的元素。

s.erase(10);  // 删除元素 10

• 查找元素：可以使用 find() 函数查找指定元素是否存在。

if (s.find(5) != s.end()) {
    std::cout << "元素 5 存在" << std::endl;
}

• 获取大小：可以使用 size() 函数获取 set 中的元素个数。

std::cout << "Set 的大小: " << s.size() << std::endl;

2.4 set 的底层实现

set 的底层使用红黑树（自平衡二叉搜索树）实现。红黑树是一种平衡二叉树，保证在最坏情况下，插入、删除和查找的时间复杂度都是 O(log n)。在红黑树中，元素按照键值自动排序，因此 set 的插入操作不仅将元素添加到集合中，还会自动维护元素的顺序。

2.5 set 的应用场景

• 元素去重：set 常用于需要存储唯一元素的场景，例如从一个包含重复元素的集合中提取唯一值。
• 有序数据存储：由于 set 中的元素是有序的，可以用于需要对数据进行排序并快速查找的场景。
• 集合操作：set 可以用于实现集合的基本操作，如交集、并集和差集。

2.6 set 的优缺点

• 优点：
  • 自动维护元素的唯一性。
  • 元素自动排序，查找效率高。
• 缺点：
  • 插入和删除的效率比 unordered_set 稍低，因为需要维护平衡树结构。
  • 无法通过下标访问元素。

3. map 容器

3.1 什么是 map？

map 是一种关联容器，用于存储键值对（key-value）。每个键（key）都是唯一的，不能重复；而值（value）可以是相同的。map 的实现方式和 set 类似，也是基于红黑树。键值对中的键会自动按顺序排列，以便于快速查找、插入和删除。

3.2 map 的特点

• 键唯一性：map 中的键必须是唯一的，不能有重复键。
• 有序性：map 中的键按一定顺序（默认升序）存储，用户可以自定义排序规则。
• 键值对存储：map 存储的是键值对，每个键映射到一个值。
• 高效的查找：map 提供高效的查找、插入和删除操作，时间复杂度为 O(log n)。

3.3 map 的常用操作

• 插入键值对：可以使用 insert() 或 operator[] 插入键值对。

#include <map>
#include <iostream>

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

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

• 查找元素：可以使用 find() 函数查找指定键是否存在。

if (m.find(2) != m.end()) {
    std::cout << "键 2 存在，值为: " << m[2] << std::endl;
}

• 删除元素：可以使用 erase() 函数删除指定的键值对。

m.erase(1);  // 删除键为 1 的键值对

• 获取大小：可以使用 size() 函数获取 map 中的键值对数量。

std::cout << "Map 的大小: " << m.size() << std::endl;

3.4 map 的底层实现

map 的底层实现同样基于红黑树，这保证了键值对在插入时可以自动排序，同时支持高效的查找和删除操作。红黑树是一种平衡树，其高度大致保持在 log(n) 级别，因此能够确保操作的时间复杂度为 O(log n)。

3.5 map 的应用场景

• 键值对存储：map 非常适合用于需要以键值对方式存储数据的场景，如词频统计、数据表映射等。
• 快速查找：map 提供高效的查找机制，适合用于需要根据键快速查找对应值的场景。
• 排序数据存储：由于 map 中的键是有序的，它适合用于需要对数据按键进行排序的场景。

3.6 map 的优缺点

• 优点：
  • 键唯一且有序，能够自动排序。
  • 提供高效的查找、插入和删除操作。
• 缺点：
  • 插入和删除操作的效率比 unordered_map 略低，因为需要维护平衡树结构。
  • 无法通过下标直接访问键。

4. multiset 和 multimap

4.1 multiset

multiset 是 set 的变种，允许存储重复的元素。其底层实现也是基于红黑树，操作的时间复杂度同样为 O(log n)。

multiset 的常用操作

• 插入元素：与 set 类似，可以使用 insert() 函数插入元素。

std::multiset<int> ms;
ms.insert(10);
ms.insert(5);
ms.insert(10);  // 允许插入重复元素

• 删除元素：可以使用 erase() 函数删除元素，但它会删除所有等于该值的元素。

ms.erase(10);  // 删除所有值为 10 的元素

4.2 multimap

multimap 是 map 的变种，允许多个相同的键映射到不同的值。其底层实现同样是基于红黑树。

multimap 的常用操作

• 插入键值对：可以使用 insert() 函数插入键值对。

std::multimap<int, std::string> mm;
mm.insert({1, "one"});
mm.insert({1, "uno"});  // 允许插入重复的键

• 查找元素：可以使用 equal_range() 函数获取具有相同键的元素范围。

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

5. 无序容器：unordered_set 和 unordered_map

5.1 unordered_set

unordered_set 是一种哈希表实现的集合容器，与 set 不同，它不维护元素的顺序。unordered_set 提供常数时间复杂度的插入、删除和查找操作，但在最坏情况下，时间复杂度可能退化为 O(n)。

unordered_set 的特点

• 无序性：元素的存储顺序不固定。
• 哈希表实现：底层使用哈希表，因此插入、删除和查找的平均时间复杂度为 O(1)。

5.2 unordered_map

unordered_map 是一种基于哈希表实现的关联容器，存储键值对，键是唯一的。它与 map 的区别在于，不维护键的顺序，查找、插入和删除操作的平均时间复杂度为 O(1)。

unordered_map 的特点

• 无序性：键的存储顺序不固定。
• 哈希表实现：底层使用哈希表，因此查找、插入和删除的平均时间复杂度为 O(1)。

6. set、map 与无序容器的对比

6.1 有序与无序

• set 和 map：存储的数据是有序的，适合需要保持元素排序的场景。
• unordered_set 和 unordered_map：存储的数据是无序的，适合只关心快速查找和插入的场景。

6.2 时间复杂度

• set 和 map：插入、删除和查找操作的时间复杂度为 O(log n)。
• unordered_set 和 unordered_map：插入、删除和查找操作的平均时间复杂度为 O(1)，但最坏情况下为 O(n)。

6.3 内存使用

• set 和 map：由于使用红黑树实现，内存使用相对较高，但能保证数据有序。
• unordered_set 和 unordered_map：使用哈希表实现，内存使用较为紧凑，但在发生哈希冲突时性能会下降。

7. 示例代码总结

以下是一个完整的示例代码，展示了 set、map、multiset、multimap、unordered_set 和 unordered_map 的基本使用方法：

#include <iostream>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <string>

int main() {
    // set 示例
    std::set<int> s = {1, 2, 3, 4, 5};
    s.insert(6);
    s.erase(3);
    for (int val : s) {
        std::cout << "Set element: " << val << std::endl;
    }

    // map 示例
    std::map<int, std::string> m;
    m[1] = "one";
    m[2] = "two";
    m[3] = "three";
    m.erase(2);
    for (const auto &pair : m) {
        std::cout << "Map element: " << pair.first << ": " << pair.second << std::endl;
    }

    // unordered_set 示例
    std::unordered_set<int> us = {10, 20, 30, 40};
    us.insert(50);
    us.erase(20);
    for (int val : us) {
        std::cout << "Unordered_set element: " << val << std::endl;
    }

    // unordered_map 示例
    std::unordered_map<int, std::string> um;
    um[1] = "apple";
    um[2] = "banana";
    um[3] = "cherry";
    um.erase(1);
    for (const auto &pair : um) {
        std::cout << "Unordered_map element: " << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

8. 总结

C++ 中的 set 和 map 容器在数据管理和组织方面非常有用，它们基于红黑树实现，保证了数据的有序性和高效的查找、插入、删除操作。对于需要存储唯一且有序数据的场景，可以选择使用 set，而对于需要以键值对方式存储数据的场景，可以选择使用 map。在需要允许重复元素的情况下，可以使用 multiset 或 multimap。如果对元素的顺序没有要求且更关心操作效率，可以选择无序容器 unordered_set 和 unordered_map。根据具体的需求选择合适的容器，可以显著提升程序的性能和开发效率。