set 和 map 底层实现详解及 LeetCode 高频算法实战

s.insert({2, 3, 4, 5});
for (auto e : s) {
    cout << e << " ";
}

set: erase 和 find

删除操作

由于 set 默认升序，删除最小值可直接移除起始迭代器：

s.erase(s.begin());

删除指定值时，erase 返回被删除元素的个数（对于 set 通常是 0 或 1）：

int x;
cin >> x;
int num = s.erase(x);
if (num == 0) {
    cout << x << "不存在" << endl;
} else {
    cout << x << "删除成功" << endl;
}

更推荐的方式是使用 find 获取迭代器后删除，这样能避免多次查找开销：

auto pos = s.find(x);
if (pos != s.end()) {
    s.erase(pos);
    cout << x << "删除成功" << endl;
} else {
    cout << x << "不存在" << endl;
}

注意迭代器失效问题： 调用 erase(pos) 后，pos 指向的节点已被销毁，该迭代器立即失效。此时再访问 *pos 会导致野指针错误。如果是删除根节点，虽然红黑树结构通过替代法维持了平衡，但原迭代器依然无效。

查找效率

容器自带的 find 方法效率更高（O(logN)），优于算法库中的 std::find（O(N)）：

auto pos1 = find(s.begin(), s.end(), x); // O(N)
auto pos2 = s.find(x);                   // O(logN)

set: count

利用 count 进行存在性判断。在 set 中，元素唯一，返回值非 0 即 1。

if (s.count(x)) {
    cout << x << "在集合中" << endl;
} else {
    cout << x << "不在集合中" << endl;
}

set: lower_bound 和 upper_bound

这两个函数用于定位区间，常用于范围删除或查找。

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

int main() {
    set<int> mset;
    for (int i = 1; i < 10; i++) {
        mset.insert(i * 10);
    }
    // 10 20 30 40 50 60 70 80 90

    // [30, 50] 区间，左闭右开
    auto itlow = mset.lower_bound(30); // 返回 >= 30 的第一个位置
    auto itup = mset.upper_bound(50);  // 返回 > 50 的第一个位置

    mset.erase(itlow, itup); // 删除这段区间的值

    for (auto e : mset) {
        cout << e << " ";
    }
    // 输出：10 20 60 70 80 90
    return 0;
}

multiset 和 set

multiset 与 set 用法类似，主要区别在于允许键值冗余（不去重）。multiset 仅排序，保留所有重复项。

查找时，find 会返回中序遍历遇到的第一个匹配项。通过不断递增迭代器，可以遍历出所有相同的值。

map：insert

map 的 insert 返回值为 pair<iterator, bool>。

• 插入成功：返回新插入节点的迭代器和 true。
• 插入失败：返回已存在 key 对应节点的迭代器和 false。

这意味着 insert 兼具插入与查找功能。

// 插入一个 pair<key, value>
pair<iterator, bool> ret = insert({k, mapped_type()});

map: operator[]

operator[] 是 map 最便捷的访问方式，其内部逻辑如下：

mapped_type& operator[](const key_type& k) {
    pair<iterator, bool> ret = insert({k, mapped_type()});
    iterator it = ret.first;
    return it->second;
}

工作原理：

1. Key 不存在：尝试插入 {k, 默认值}。插入成功后，返回新值的引用。适合统计词频等场景。
2. Key 存在：插入失败，直接返回已存在值的引用。适合修改映射值。

示例：词频统计

int main() {
    string myarray[] = {"秋", "冬", "夏", "春", "夏", "秋", "夏", "春", "夏", "秋", "秋", "冬"};
    map<string, int> countMap;
    for (const auto& e : myarray) {
        countMap[e]++; // 不存在则初始化为 0 再自增，存在则直接自增
    }
    for (const auto& it : countMap) {
        cout << it.first << ":" << it.second << endl;
    }
    return 0;
}

multimap 和 map 的差异

1. Key 冗余：multimap 支持 Key 重复，map 不支持。
2. Find 行为：multimap 的 find 返回第一个匹配的迭代器，若有多个相同 Key，需配合 equal_range 或循环遍历。
3. Operator[]：multimap 不支持 operator[]，因为无法确定修改哪一个重复 Key 对应的值。

LeetCode 经典题目实战

两个数组的交集

思路：利用 set 的去重和有序特性。

1. 将两个数组分别转为 set，去除重复元素并排序。
2. 使用双指针遍历两个 set。
3. 若 *it1 < *it2，说明 it1 当前值不可能是交集，it1++。
4. 若相等，加入结果集，两指针均 ++。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret;
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());

        auto it1 = s1.begin();
        auto it2 = s2.begin();

        while (it1 != s1.end() && it2 != s2.end()) {
            if (*it1 < *it2) {
                ++it1;
            } else if (*it1 > *it2) {
                ++it2;
            } else {
                ret.push_back(*it1);
                ++it1;
                ++it2;
            }
        }
        return ret;
    }
};

环形链表

思路：利用 set 存储已访问过的节点指针。

1. 遍历链表，检查当前节点是否在 set 中。
2. 若在，说明遇到环，返回该节点。
3. 若不在，插入 set 并继续向后。
4. 若走到 nullptr，无环。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> s;
        ListNode* cur = head;
        while (cur) {
            if (s.count(cur)) return cur;
            s.insert(cur);
            cur = cur->next;
        }
        return nullptr;
    }
};

随机链表的复制

思路：深拷贝需要处理 random 指针，使用 map<Node*, Node*> 建立原节点与新节点的映射关系。

1. 第一遍遍历：创建新节点，建立映射 randomMap[ptr] = copytail。
2. 第二遍遍历：根据映射表设置新节点的 random 指针。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> randomMap;
        Node* copyhead = nullptr, *copytail = nullptr;
        Node* ptr = head;

        // 第一遍：构建新链表并建立映射
        while (ptr) {
            if (!copytail) {
                copytail = copyhead = new Node(ptr->val);
            } else {
                copytail->next = new Node(ptr->val);
                copytail = copytail->next;
            }
            randomMap[ptr] = copytail;
            ptr = ptr->next;
        }

        // 第二遍：处理 random 指针
        Node* copy = copyhead;
        ptr = head;
        while (ptr) {
            if (ptr->random) {
                copy->random = randomMap[ptr->random];
            }
            copy = copy->next;
            ptr = ptr->next;
        }
        return copyhead;
    }
};

前 K 个高频单词

思路：统计频率 -> 转换为 Vector -> 自定义排序。

1. 使用 map<string, int> 统计词频，map 天然按键字典序排序。
2. 将 map 转为 vector<pair<string, int>>。
3. 使用 stable_sort 进行稳定排序。当频率相同时，保持原有顺序（即字典序）。
4. 取前 K 个元素。

class Solution {
public:
    struct kvFunction {
        bool operator()(const pair<string, int>& w1, const pair<string, int>& w2) {
            return w1.second > w2.second; // 频率高的在前
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countMap;
        for (auto& it : words) {
            countMap[it]++;
        }

        vector<pair<string, int>> v(countMap.begin(), countMap.end());
        stable_sort(v.begin(), v.end(), kvFunction());

        vector<string> ret;
        for (int i = 0; i < k; i++) {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};

set 和 map 的构造对比

总结来说，set 关注 Key 的唯一性与有序性，而 map 在此基础上增加了 Key 到 Value 的映射能力。在实际开发中，理解它们的底层机制有助于写出更高效、更安全的代码。