C++ 中的 <code>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。根据具体的需求选择合适的容器，可以显著提升程序的性能和开发效率。