c++STL中map和set的原理（关联式容器）
在C++的STL（Standard Template Library）中，map和set是关联式容器，用于存储和管理一组按照键值进行排序和唯一性限制的元素。这两个容器都基于平衡二叉搜索树（通常是红黑树）实现。
map是一个键值对的集合，其中每个元素都由一个唯一的键（key）和一个相关联的值（value）组成。键值对按照键的顺序进行排序，因此可以通过键快速查找对应的值。键必须是唯一的，如果插入了具有相同键的元素，则会覆盖原有的键值对。
set是一个存储唯一值的集合。它的元素按照严格的弱序进行排序，不允许重复的元素存在。因此，如果尝试插入一个已经存在于set中的元素，插入操作将会被忽略。
这两个容器的实现基于平衡二叉搜索树（Balanced Binary Search Tree），通常是红黑树（Red-Black Tree）。红黑树是一种自平衡二叉搜索树，具有如下特性：
每个节点要么是红色，要么是黑色。
根节点是黑色的。
每个叶子节点（NIL节点，空节点）是黑色的。
如果一个节点是红色的，则它的两个子节点都是黑色的。
对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。
这些特性保证了红黑树的平衡性，并且在最坏情况下，查找、插入和删除操作的时间复杂度都是O(log n)。
对于map和set，它们的成员函数和操作符的实现都利用了红黑树的特性，以提供高效的元素查找和插入操作。例如，map中的operator[]可以用于通过键快速查找对应的值，insert()函数用于插入新的键值对，find()函数用于查找给定键的位置等等。
总而言之，map和set在STL中是通过红黑树实现的关联式容器，提供了高效的元素查找和插入操作，并且保持了元素的排序和唯一性约束。
当使用map时，可以考虑一个学生成绩管理的示例。我们可以使用map来存储学生的姓名作为键（key），成绩作为相关联的值（value）。以下是一个简单的示例代码：
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<std::string, int> studentScores;
// 插入学生成绩
studentScores["Alice"] = 90;
studentScores["Bob"] = 80;
studentScores["Charlie"] = 95;
studentScores["David"] = 87;
// 查找学生成绩
std::cout << "Bob's score: " << studentScores["Bob"] << std::endl;
// 修改学生成绩
studentScores["Bob"] = 85;
std::cout << "Bob's updated score: " << studentScores["Bob"] << std::endl;
// 遍历学生成绩
std::cout << "All student scores:\\n";
for (const auto& pair : studentScores) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}在这个例子中，我们使用map来存储学生姓名和对应的成绩。通过键值对的形式，我们可以通过学生的姓名快速查找对应的成绩，并且能够修改成绩。
另一方面，当使用set时，考虑一个简单的示例，我们要存储一些整数，并且保持它们的唯一性。以下是一个示例代码：
#include <iostream>
#include <set>
int main() {
std::set<int> numbers;
// 插入整数
numbers.insert(10);
numbers.insert(5);
numbers.insert(15);
numbers.insert(10); // 重复元素，将被忽略
// 查找整数
int target = 5;
if (numbers.find(target) != numbers.end()) {
std::cout << "Number " << target << " found!" << std::endl;
} else {
std::cout << "Number " << target << " not found!" << std::endl;
}
// 遍历整数集合
std::cout << "All numbers in the set:\\n";
for (const auto& number : numbers) {
std::cout << number << std::endl;
}
return 0;
}在这个例子中，使用set来存储一组整数，并且由于set的特性，重复的整数将被自动忽略。可以使用find()函数来查找特定的整数是否存在于集合中，并且遍历整数集合时，元素会按照严格的弱序进行输出。
