C++ Set 与 Map 底层实现及高频算法实战

Set: erase 和 find

删除最小值：由于 Set 按升序存储，s.erase(s.begin()) 会直接删除最小的元素。

s.erase(s.begin());
for (auto e : s) {
    cout << e << " "; // 剩余元素
}

删除指定值：

int x;
cin >> x;
// 方法 1：返回值表示删除的元素个数
int num = s.erase(x);
if (num == 0) {
    cout << x << "不存在" << endl;
} else {
    cout << x << "删除成功" << endl;
}

// 方法 2：先查找再删除
auto pos = s.find(x);
if (pos != s.end()) {
    s.erase(pos);
    cout << x << "删除成功" << endl;
} else {
    cout << x << "不存在" << endl;
}

注意迭代器失效问题：在方法 2 中，erase(pos) 后，pos 指向的节点已被移除，该迭代器立即失效。若后续访问 *pos 会导致野指针错误。删除根节点时虽可能通过替代法维持树结构，但原迭代器依然无效。

查找效率对比：

int x;
auto pos1 = find(s.begin(), s.end(), x); // 算法库实现，O(N)
auto pos2 = s.find(x);                   // 容器成员函数，O(logN)

显然，直接使用容器的 find 更高效。

Set: count

利用 count 进行存在性判断。对于 Set，返回值为 0 或 1。

cin >> x;
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 允许键值重复，仅保证有序。

int main() {
    multiset<int> s = {4, 2, 3, 1, 5, 6, 8, 6, 43, 2, 5};
    auto it = s.begin();
    while (it != s.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    int x;
    cin >> x;
    auto pos = s.find(x);
    // 找到第一个匹配项后，继续 ++ 可遍历所有相同值的元素
    while (pos != s.end() && *pos == x) {
        cout << *pos << " ";
        ++pos;
    }
    cout << endl;
    return 0;
}

注意：find 在 Multiset 中只返回中序遍历的第一个匹配项。若要处理所有重复项，需配合循环 ++ 迭代器。

Map: insert

insert 返回 pair<iterator, bool>。展开来看，value_type 是 pair<const key_type, mapped_type>。

• 插入成功：返回 {新插入值的迭代器，true}。
• 插入失败（Key 已存在）：返回 {已存在 Key 的迭代器，false}。

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

// 示例逻辑
pair<iterator, bool> ret = map.insert({key, value});
if (ret.second) {
    // 插入成功
} else {
    // 插入失败，ret.first 指向已有元素
}

Map: operator[]

operator[] 内部调用了 insert，并返回映射值的引用。

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, mapped_type()}（默认构造值），返回该值的引用。适合计数场景。
2. 若 Key 存在：不插入，直接返回现有值的引用。适合修改场景。

int main() {
    string myarray[] = {"秋", "冬", "夏", "春", "夏", "秋", "夏", "春", "夏", "秋", "秋", "冬"};
    map<string, int> countMap;
    for (const auto& e : myarray) {
        countMap[e]++; // 自动统计频率
    }
    for (const auto& it : countMap) {
        cout << it.first << ":" << it.second << endl;
    }
    return 0;
}

总结：operator[] 既可用于插入新键值对，也可用于更新已有键的值。对于计数统计非常方便。

Multimap 和 Map 的差异

1. Key 冗余：Multimap 支持 Key 重复，Map 不支持。
2. 操作差异：Multimap 的 find 返回第一个匹配项；operator[] 在 Multimap 中不可用（因为无法确定返回哪个 Key 对应的 Value），仅支持 insert。

力扣题目实战

两个数组的交集

思路：利用 Set 的去重和有序特性。将两个数组转为 Set，使用双指针遍历。

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 的唯一性检测节点是否重复访问。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> s;
        ListNode* cur = head;
        while (cur) {
            if (s.count(cur)) {
                return cur; // 发现环，返回入口节点
            } else {
                s.insert(cur); // 标记访问
                cur = cur->next;
            }
        }
        return nullptr; // 无环
    }
};

注意：count 返回 1 表示存在，0 表示不存在。此解法空间复杂度为 O(N)。

随机链表的复制

思路：深拷贝需同时处理 next 和 random 指针。使用 Map 建立原节点与新节点的映射关系。

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];
            } else {
                copy->random = nullptr;
            }
            copy = copy->next;
            ptr = ptr->next;
        }
        return copyhead;
    }
};

前 K 个高频单词

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

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;
    }
};

关键点：

1. map 天然按键字典序升序存储。
2. stable_sort 保证频率相同时保持原有顺序（即字典序）。
3. 组合起来实现了'频率降序，同频字典序升序'的需求。

Set 和 Map 构造对比

两者均支持正向和反向迭代，且都依赖红黑树维持平衡与有序性。在实际开发中，理解其底层机制有助于选择合适的数据结构并规避迭代器失效等陷阱。