map和set：平衡二叉搜索树的STL实现

上回我们讲解了 平衡二叉搜索树（AVL树或红黑树），这次我们来聊聊由平衡二叉搜索树实现的两个重要容器：map 和 set。

如果还不清楚平衡二叉搜索树是什么，建议先去看看上一篇文章哦~

什么是map和set？

map 和 set 都是 关联容器，它们底层就是用 红黑树 实现的。

之前我们学的 stack 和 queue 是顺序容器，而 map 和 set 是关联容器，最大的区别就是：关联容器支持高效的查找。

set（集合）：

• 里面不重复存储元素
• 主要用来去重和快速查找某个元素是否存在
• 就像一个装了互不相同物品的盒子

map（映射）：

• 存储的是 键值对（key-value）
• 通过 key 可以快速找到 value
• 就像一个字典，通过拼音（key）查汉字（value）

简单理解：

• set = 只有key的map
• map = set升级版，每个key绑定了一个value

map和set的特点

为什么 map 和 set 查找效率高？ 因为它们底层是 红黑树：

• 查找、插入、删除 的时间复杂度都是 O(logN)
• 元素会自动按照 key 排序
• 底层会自动 去重（特别是set）

这可比我们之前学的 vector 一个个遍历找元素快多了！

map 和 set 的特点：

• 元素自动按key排序（默认升序）
• 不支持下标随机访问
• 不支持迭代器随机访问（但可以用迭代器遍历）
• set的元素必须唯一，map的key必须唯一

set常用API

set 常用的接口：
insert()：插入元素
find()：查找元素（返回迭代器）
erase()：删除元素
count()：统计元素个数（0或1，因为不重复）
empty()：判断是否为空
size()：获取元素个数
begin() / end()：获取迭代器

set使用示例

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

int main()
{
    set<int> s;

    // insert: 插入元素（自动去重，按升序排列）
    s.insert(3);
    s.insert(1);
    s.insert(5);
    s.insert(3);  // 重复元素，不会重复插入

    // size: 获取元素个数
    cout << "set size: " << s.size() << endl;  // 输出3，重复的3只存了一个

    // 遍历set（set本身是有序的）
    cout << "set elements: ";
    for (auto it = s.begin(); it != s.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;  // 输出：1 3 5

    // find: 查找元素
    auto it = s.find(3);
    if (it != s.end())
    {
        cout << "found: " << *it << endl;
    }
    else
    {
        cout << "not found" << endl;
    }

    // count: 统计元素个数
    cout << "count of 3: " << s.count(3) << endl;  // 输出1
    cout << "count of 10: " << s.count(10) << endl;  // 输出0

    // erase: 删除元素
    s.erase(1);
    cout << "after erase 1, size: " << s.size() << endl;  // 输出2

    return 0;
}

map常用API

map 常用的接口：
insert()：插入键值对
operator[]：重点！ 通过key访问value（超级好用）
find()：查找key（返回迭代器）
erase()：删除键值对
count()：统计key是否存在
empty()：判断是否为空
size()：获取键值对个数
begin() / end()：获取迭代器

map使用示例

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

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

    // insert: 插入键值对（多种方式）
    m.insert(pair<string, string>("apple", "苹果"));
    m.insert(make_pair("banana", "香蕉"));
    m["orange"] = "橙子";  // 直接用[]赋值，更方便！

    // operator[]: 通过key获取value
    cout << "apple: " << m["apple"] << endl;
    cout << "banana: " << m["banana"] << endl;

    // size: 获取元素个数
    cout << "map size: " << m.size() << endl;  // 输出3

    // find: 查找key
    auto it = m.find("apple");
    if (it != m.end())
    {
        cout << "found: " << it->first << " = " << it->second << endl;
    }

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

    // erase: 删除键值对
    m.erase("banana");
    cout << "after erase, size: " << m.size() << endl;  // 输出2

    return 0;
}

map和set的简单模拟实现

其实 map 和 set 的底层就是 红黑树，我们可以简单模仿一下：

#include <iostream>
using namespace std;

// 红黑树节点颜色
enum Color { RED, BLACK };

// 红黑树节点结构
template<class K, class V>
struct RBTreeNode
{
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Color _color;

    RBTreeNode(const pair<K, V>& kv)
        : _kv(kv)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _color(RED)
    {}
};

// 简化的红黑树（只展示核心思想）
template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
public:
    RBTree()
        : _root(nullptr)
    {}

    // insert: 插入节点
    bool insert(const pair<K, V>& kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            _root->_color = BLACK;
            return true;
        }

        // 查找插入位置（按key比较）
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (kv.first < cur->_kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (kv.first > cur->_kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                return false;  // key已存在，不插入
            }
        }

        // 插入新节点
        cur = new Node(kv);
        if (kv.first < parent->_kv.first)
            parent->_left = cur;
        else
            parent->_right = cur;
        cur->_parent = parent;

        // todo: 这里还需要红黑树的旋转和变色处理，保证平衡
        // 为了简化，这里省略......

        return true;
    }

    // find: 查找节点
    Node* find(const K& key)
    {
        Node* cur = _root;
        while (cur)
        {
            if (key < cur->_kv.first)
                cur = cur->_left;
            else if (key > cur->_kv.first)
                cur = cur->_right;
            else
                return cur;  // 找到了
        }
        return nullptr;
    }

private:
    Node* _root;
};

int main()
{
    // 模拟set（只存key）
    RBTree<int, int> setTree;
    setTree.insert(make_pair(3, 3));
    setTree.insert(make_pair(1, 1));
    setTree.insert(make_pair(5, 5));

    // 模拟map（存key-value）
    RBTree<string, string> mapTree;
    mapTree.insert(make_pair("apple", "苹果"));
    mapTree.insert(make_pair("banana", "香蕉"));

    cout << "模拟set插入成功" << endl;
    cout << "模拟map插入成功" << endl;

    return 0;
}

简单说明：

• 真正的红黑树实现还有很多 旋转 和 变色 的细节，来保证树的平衡
• 我们这里只是展示核心思想：按key 比较后插入到合适位置
• STL中的 map 和 set 都是用红黑树实现的，查找效率是 O(logN)

multiset和multimap

除了 set 和 map，STL还提供了 multiset 和 multimap：

• multiset：允许重复 元素的集合
• multimap：允许重复key 的映射

用法和 set、map 几乎一样，区别就是 insert() 时不会去重。

总结

set 是集合，存不重复的元素，重点接口是 insert、find、erase。
map 是映射，存 key-value 对，重点接口是 insert、operator[]、find、erase。
它们底层都是 红黑树，查找、插入、删除效率都是 O(logN)。
multiset 和 multimap 是允许重复的版本。