C++ STL 进阶：set 与 map 容器使用详解 | 极客日志

C++算法

C++ STL 进阶：set 与 map 容器使用详解

STL 关联式容器主要包括 set、map 及其多版本。set 保证元素唯一且有序，map 提供键值映射。pair 辅助存储成对数据。核心操作涵盖构造、插入、删除、查找及范围查询。结合 LeetCode 实战案例，展示如何利用容器特性解决数组交集、链表环检测及词频统计问题。

橘子海发布于 2026/3/26更新于 2026/4/251 浏览

C++ STL 进阶：set 与 map 容器使用详解

C++ STL 进阶：set 与 map 容器使用详解

容器分类概览

STL 中的容器主要分为序列式容器和关联式容器。序列式容器（如 vector、list）强调元素的线性存储顺序，通过位置索引或迭代器访问；而关联式容器（如 set、map）则基于树或哈希表实现，通过关键字（Key）进行高效检索。

维度	序列式容器	关联式容器
逻辑结构	线性序列	非线性结构（树、哈希表）
元素关联	仅通过位置顺序关联	通过键值的有序性或哈希映射关联
访问依据	存储位置（索引或迭代器）	关键字（Key）
典型实现	`vector`, `list`, `deque`	`set`, `map`, `unordered_set`

set 容器详解

std::set 是关联式容器的一种，内部通常由红黑树实现。它有两个核心特性：自动排序和元素唯一性。插入重复元素时会被自动忽略。

模板参数

template<class T, class Compare = std::less<T>, class Alloc = std::allocator<T>>
class set;

T: 元素类型，需支持比较操作。
Compare: 比较器，默认按升序排列。
Alloc: 内存分配器。

构造与初始化

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

  {
    
    set<> s1;

    
     myints[] = {, , , , };
    ;

    
    ;

    
    set<, greater<>> s4;
     ;
}

// 插入示例
set<int> s;
s.insert(10); // 成功
s.insert(10); // 失败，返回 false

// 删除示例
auto it = s.find(10);
if (it != s.end()) s.erase(it);

// 区间删除示例
set<int> s = {10, 20, 30, 40, 50};
auto itlow = s.lower_bound(20);
auto itup = s.upper_bound(40);
s.erase(itlow, itup); // 删除 [20, 40] 区间内的元素

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

int main() {
    // 基础特性：去重 + 排序
    set<int> s = {5, 2, 7, 2, 8, 5, 9}; 
    // 输出：2 5 7 8 9

    // 批量插入
    s.insert({2, 8, 3, 9}); 

    // 字符串集合并按字典序排序
    set<string> strset = {"sort", "insert", "add"};
    for (const auto& e : strset) {
        cout << e << " "; // add insert sort
    }
    return 0;
}

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

int main() {
    multiset<int> ms = {4, 2, 7, 2, 4, 8};
    // 输出：2 2 4 4 7 8

    int x = 2;
    cout << "Count: " << ms.count(x) << endl; // 输出 2

    auto pos = ms.find(x);
    while (pos != ms.end() && *pos == x) {
        cout << *pos << " ";
        ++pos;
    }
    return 0;
}

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

int main() {
    // 定义 pair
    pair<string, int> p("apple", 10);

    // 访问成员
    cout << p.first << ": " << p.second << endl;

    // 辅助函数 make_pair
    auto p2 = make_pair(1, "hello");
    return 0;
}

template<class Key, class T, class Compare = less<Key>, class Alloc = allocator<pair<const Key, T>>>
class map;

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

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

    // 插入
    dict["left"] = "左边";
    dict.insert(make_pair("right", "右边"));

    // 访问
    if (dict.count("left")) {
        cout << dict["left"] << endl;
    }

    // 注意：dict["unknown"] 会插入一个空字符串键值对
    return 0;
}

// 统计词频的经典写法
map<string, int> countMap;
string arr[] = {"apple", "banana", "apple"};
for (const auto& str : arr) {
    countMap[str]++; // 简化了 find + insert + update 的逻辑
}

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());
        vector<int> ret;
        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;
    }
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> visited;
        ListNode* cur = head;
        while (cur) {
            auto ret = visited.insert(cur);
            if (!ret.second) return cur; // 插入失败说明已存在，即环入口
            cur = cur->next;
        }
        return nullptr;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> m;
        Node* copyHead = nullptr;
        Node* copyTail = nullptr;
        Node* curr = head;

        // 复制 next 指针
        while (curr) {
            if (!copyTail) {
                copyHead = copyTail = new Node(curr->val);
            } else {
                copyTail->next = new Node(curr->val);
                copyTail = copyTail->next;
            }
            m[curr] = copyTail;
            curr = curr->next;
        }

        // 处理 random 指针
        curr = head;
        Node* copy = copyHead;
        while (curr) {
            copy->random = curr->random ? m[curr->random] : nullptr;
            curr = curr->next;
            copy = copy->next;
        }
        return copyHead;
    }
};

class Solution {
public:
    struct Compare {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
            return x.second < y.second || (x.second == y.second && x.first > y.first);
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> m;
        for (const auto& w : words) m[w]++;

        priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> pq(m.begin(), m.end());
        vector<string> ret;
        for (int i = 0; i < k; ++i) {
            ret.push_back(pq.top().first);
            pq.pop();
        }
        return ret;
    }
};