C++ STL 中 set 与 map 的实现原理及算法实战应用

删除最小值可直接使用 s.erase(s.begin())。

查找元素推荐使用容器自带的 find 方法，效率高于算法库的 std::find。

// 直接删除指定值
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);
    cout << x << "删除成功" << endl;
}

迭代器失效问题： 调用 erase 后，指向被删除节点的迭代器立即失效，访问会导致未定义行为。

set: count 与 bounds

count 用于判断元素是否存在，存在返回 1，否则 0。

lower_bound 返回第一个大于等于给定值的迭代器，upper_bound 返回第一个大于给定值的迭代器。两者结合可实现区间删除。

set<int> mset;
for (int i = 1; i < 10; i++) {
    mset.insert(i * 10);
}
// 删除 [30, 50] 区间内的元素
auto itlow = mset.lower_bound(30);
auto itup = mset.upper_bound(50);
mset.erase(itlow, itup);

multiset 与 set

multiset 允许键值重复，仅排序不去重。查找时 find 返回中序遍历的第一个匹配项，配合迭代器自增可遍历所有相同键值。

map: insert 与 operator[]

map 的 insert 返回 pair<iterator, bool>。插入成功返回新节点迭代器和 true，失败返回已存在节点迭代器和 false。

operator[] 内部调用了 insert。如果 key 不存在，会先默认构造 value 再插入，并返回 value 引用；如果 key 存在，直接返回 value 引用。这使得 operator[] 兼具查找、插入和修改功能。

string myarray[] = {"秋", "冬", "夏", "春", "夏", "秋"};
map<string, int> countMap;
for (const auto& e : myarray) {
    countMap[e]++; // 自动统计词频
}

multimap 与 map 差异

multimap 支持 key 冗余，不支持 operator[]，因为无法确定修改哪个重复 key 对应的 value。

算法实战案例

两个数组的交集

利用 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;
            s.insert(cur);
            cur = cur->next;
        }
        return nullptr;
    }
};

随机链表的复制

使用 map 建立原链表节点与新链表节点的映射关系，分两步完成 next 和 random 指针的拷贝。

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 加稳定排序。利用 map 天然的字典序 + stable_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;
    }
};

set 与 map 构造对比

set 和 map 底层均为红黑树，支持正向和反向迭代，默认按升序遍历。

• set: iterator 不可修改关键字，否则破坏树结构。
• map: 支持修改 value，但不支持修改 key。