C++ STL set与map核心特性与红黑树实现解析

1. STL容器进阶：set与map的核心特性

在C++标准模板库(STL)中，set和map是两种基于红黑树实现的关联容器，它们提供了高效的查找、插入和删除操作。与序列容器(vector、list等)不同，关联容器通过键(key)来组织和访问元素，而不是通过位置索引。

1.1 set容器的本质与特点

set是一个有序集合，它存储唯一元素并自动排序。其核心特性包括：

• 元素自动按升序排列（可通过比较函数自定义）
• 每个元素值必须唯一（不允许重复）
• 插入/删除/查找时间复杂度均为O(log n)
• 底层通常实现为红黑树（自平衡二叉搜索树）

cpp复制#include <set>
#include <iostream>

int main() {
    std::set<int> numbers = {5, 2, 8, 2, 1};  // 重复的2只会保留一个
    
    // 自动排序输出：1 2 5 8
    for(int num : numbers) {
        std::cout << num << " ";
    }
    
    // 查找操作
    if(numbers.find(5) != numbers.end()) {
        std::cout << "\n5 exists in the set";
    }
}

注意：set的迭代器是双向迭代器，不支持随机访问（不能像vector那样用[]操作符直接访问元素）

1.2 map容器的结构与使用场景

map是键值对的关联容器，同样基于红黑树实现。与set不同，map存储的是pair<const Key, T>类型的元素，其中：

• 键(key)必须唯一且不可修改
• 值(value)可以修改
• 元素按键的升序自动排列

cpp复制#include <map>
#include <string>

int main() {
    std::map<std::string, int> studentScores;
    
    // 插入元素
    studentScores["Alice"] = 90;
    studentScores["Bob"] = 85;
    studentScores.insert({"Charlie", 88});
    
    // 遍历输出（按键排序）
    for(const auto& pair : studentScores) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }
    
    // 查找并修改值
    auto it = studentScores.find("Bob");
    if(it != studentScores.end()) {
        it-