set 与 map 底层实现及高频算法实战

erase 和 find

删除最小值可以直接删除起始迭代器：

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

迭代器失效问题： 如果使用迭代器定位后删除，该迭代器会立即失效，访问会导致未定义行为。

auto pos = s.find(x);
if (pos != s.end()) {
    s.erase(pos); // pos 在此处之后失效
}

查找效率上，容器自带的 find 方法利用树结构，复杂度 O(logN)，优于算法库的 std::find（O(N)）。

lower_bound 和 upper_bound

这两个函数用于区间查找，常用于二分搜索场景。

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

auto itlow = mset.lower_bound(30); // 返回 >= 30 的第一个位置
auto itup = mset.upper_bound(50);  // 返回 > 50 的第一个位置
mset.erase(itlow, itup);           // 删除 [30, 50] 区间内的元素

multiset 与 set 的区别

multiset 允许键值重复，仅排序不去重。查找时，find 返回的是第一个匹配项，通过不断递增迭代器可以获取所有相同值的节点。

map 的核心用法

map 存储 <key, value> 对，同样基于红黑树，Key 有序且唯一。

insert 返回值

insert 返回一个 pair<iterator, bool>。如果插入成功，second 为 true；如果 Key 已存在，插入失败，second 为 false，且 first 指向已存在的节点。

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

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 不存在，它会先创建一个默认初始化的 Value，然后返回引用。这可以用来方便地计数。
2. 修改便捷：如果 Key 存在，直接返回现有 Value 的引用。

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

multimap 差异

multimap 支持 Key 冗余，因此不支持 operator[] 进行单值修改，因为无法确定要修改哪一个重复的 Key。

力扣算法实战

掌握容器特性后，我们可以更高效地解决经典算法题。

两个数组的交集

题目要求返回两个数组的交集。利用 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; // 已访问，说明有环
            s.insert(cur);
            cur = cur->next;
        }
        return nullptr;
    }
};

虽然快慢指针法更节省空间，但 set 方案代码直观，适合快速验证逻辑。

随机链表的复制

深拷贝带随机指针的链表。核心难点在于 random 指针指向的节点可能尚未创建。使用 map 建立原节点到新节点的映射关系。

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

        // 第一遍：构建 next 链并建立映射
        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 个高频单词

统计词频并排序。map 负责计数，vector + sort 负责排序。

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

这里有个细节：当频率相同时，需要按字典序排序。map 本身按键字典序存储，配合 stable_sort 的稳定性，可以保证频率相同的情况下保持原有的字典序。

set 和 map 对比总结

在实际开发中，如果需要频繁查找或统计，优先考虑 set 或 map。理解它们的底层机制，能帮你写出性能更优的代码。