C++ 关联容器 map/set 小记

C++ 关联容器 map/set 小记

一、容器对比

容器	底层结构	有序性	查找复杂度	特点
set	红黑树	有序	$O(\log n)$	唯一键
multiset	红黑树	有序	$O(\log n)$	允许重复键
map	红黑树	有序	$O(\log n)$	键值对，键唯一
multimap	红黑树	有序	$O(\log n)$	键值对，键可重复
unordered_set	哈希表	无序	$O(1)$ 平均	唯一键
unordered_map	哈希表	无序	$O(1)$ 平均	键值对，键唯一

二、set / multiset

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

int main() {
    set<int> s;

    // 插入
    s.insert(3);
    s.insert(1);
    s.insert(4);
    s.insert(1);  // 重复元素会被忽略

    // 遍历（自动有序）
    for (int x : s) cout << x << " ";  // 输出: 1 3 4
    cout << endl;

    // 查找
    if (s.find(3) != s.end()) cout << "found" << endl;
    if (s.count(3)) cout << "found" << endl;  // 返回 0 或 1

    // 删除
    s.erase(3);

    // 常用成员函数
    cout << s.size() << endl;     // 元素个数
    cout << s.empty() << endl;    // 是否为空
    s.clear();                    // 清空

    // 边界操作
    set<int> s2 = {1, 3, 5, 7, 9};
    cout << *s2.lower_bound(5) << endl;  // >=5 的第一个，输出: 5
    cout << *s2.upper_bound(5) << endl;  // >5 的第一个，输出: 7

    return 0;
}

三、map / multimap

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

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

    // 插入
    m["apple"] = 5;
    m["banana"] = 3;
    m.insert({"orange", 4});
    m.insert(make_pair("grape", 2));

    // 访问
    cout << m["apple"] << endl;           // 输出: 5
    cout << m.at("banana") << endl;       // 输出: 3（带边界检查）

    // 遍历
    for (auto& p : m) {
        cout << p.first << ": " << p.second << endl;
    }

    // 查找
    auto it = m.find("apple");
    if (it != m.end()) {
        cout << it->second << endl;
    }

    // 删除
    m.erase("apple");
    m.erase(it);  // 通过迭代器删除

    // 其他成员函数
    cout << m.size() << endl;
    cout << m.count("banana") << endl;  // 返回 0 或 1
    m.clear();

    return 0;
}

四、unordered_set / unordered_map

#include <iostream>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int main() {
    unordered_set<int> us = {3, 1, 4, 1, 5};
    for (int x : us) cout << x << " ";  // 顺序不确定

    cout << endl;

    unordered_map<string, int> um;
    um["a"] = 1;
    um["b"] = 2;
    um.insert({"c", 3});

    for (auto& p : um) {
        cout << p.first << ": " << p.second << endl;
    }

    // 成员函数与 set/map 类似
    us.find(3);
    us.count(4);
    us.erase(1);
    um["a"];
    um.at("b");

    return 0;
}

五、常用成员函数速查

set / map 共有

函数	作用
insert(val)	插入元素
erase(val/it)	删除元素（值或迭代器）
find(val)	查找，返回迭代器
count(val)	统计出现次数
size()	元素个数
empty()	是否为空
clear()	清空
begin() / end()	迭代器

set 特有

函数	作用
lower_bound(val)	第一个 $\geq$ val 的迭代器
upper_bound(val)	第一个 $>$ val 的迭代器

map 特有

函数	作用
operator[]	访问/插入元素
at(key)	访问元素（带边界检查）