map 与 set 深度解析

定义与作用

std::map 和 std::set 是基于红黑树（自平衡二叉搜索树）实现的有序关联容器，提供 O(log n) 的查找、插入和删除操作，元素始终按键排序。

#include <map>
#include <set>

std::map<std::string, int> scores;
scores["大翔"] = 98;

std::set<int> uniqueIds{1, 2, 3, 3, 2};  // {1, 2, 3}

容器	存储	键唯一	默认排序
`std::set`	仅键	是	`std::less<Key>`
`std::multiset`	仅键	否	`std::less<Key>`
`std::map`	键值对	是	`std::less<Key>`
`std::multimap`	键值对	否	`std::less<Key>`

核心原理

红黑树结构

lower_bound / upper_bound / equal_range

完整示例

示例一：飞翔科技项目任务看板

场景说明：孔蓝用 std::map 管理飞翔科技的产品任务优先级看板。

#include <iostream>
#include <map>
#include <string>
#include <algorithm>

struct TaskInfo {
    std::string assignee;
    std::string status;  // TODO / DOING / DONE
    int estimateHours;
};

void printBoard(const std::map<int, TaskInfo>& board) {
    std::cout << "=== 飞翔科技任务看板 ===\n";
    std::cout << "优先级 | 负责人 | 状态   | 预估工时\n";
    for (const auto& [prio, info] : board) {   // C++17 结构化绑定
        std::cout << "  P" << prio << "   | "
                  << info.assignee << " | "
                  << info.status << " | "
                  << info.estimateHours << "h\n";
    }
}

int main() {
    std::map<int, TaskInfo> board;

    // 插入任务（按优先级自动排序）
    board[3] = {"白歌", "DOING", 8};   // 优先级 3
    board[1] = {"大翔", "DONE", 2};    // 优先级 1（最高）
    board[5] = {"小崔", "TODO", 4};    // 优先级 5
    board[2] = {"黄俪", "DOING", 6};   // 优先级 2
    board[4] = {"李眉", "TODO", 3};    // 优先级 4

    printBoard(board);

    // lower_bound / upper_bound：找出优先级 >=3 且 <5 的任务
    std::cout << "\n--- 优先级 [3, 5) 的任务 ---\n";
    auto low = board.lower_bound(3);
    auto high = board.upper_bound(4);  // < 5 即 ≤4
    for (auto it = low; it != high; ++it)
        std::cout << "P" << it->first << ": "
                  << it->second.assignee << " - "
                  << it->second.status << "\n";

    // 区间删除：移除所有 TODO 任务
    std::cout << "\n--- 移除 DONE 任务后 ---\n";
    for (auto it = board.begin(); it != board.end(); ) {
        if (it->second.status == "DONE")
            it = board.erase(it);
        else
            ++it;
    }
    printBoard(board);
}

预期输出：

=== 飞翔科技任务看板 ===
优先级 | 负责人 | 状态   | 预估工时
  P1   | 大翔 | DONE | 2h
  P2   | 黄俪 | DOING | 6h
  P3   | 白歌 | DOING | 8h
  P4   | 李眉 | TODO | 3h
  P5   | 小崔 | TODO | 4h

--- 优先级 [3, 5) 的任务 ---
P3: 白歌 - DOING
P4: 李眉 - TODO

--- 移除 DONE 任务后 ---
=== 飞翔科技任务看板 ===
优先级 | 负责人 | 状态   | 预估工时
  P2   | 黄俪 | DOING | 6h
  P3   | 白歌 | DOING | 8h
  P4   | 李眉 | TODO | 3h
  P5   | 小崔 | TODO | 4h

逐段分析：

map 自动按优先级排序（红黑树维护有序性）
lower_bound(3)：找到第一个键 >=3 的迭代器 → P3
upper_bound(4)：找到第一个键 >4 的迭代器 → P5（不包含）
erase 返回下一个有效迭代器，支持安全的遍历删除

示例二：set 实现 IP 黑名单

场景说明：李眉用 std::set 和自定义比较器实现飞翔科技的 IP 黑名单，支持高效查询。

#include <iostream>
#include <set>
#include <string>
#include <vector>

struct IPAddress {
    int octets[4];

    // 自定义排序：按数值大小而非字符串
    bool operator<(const IPAddress& other) const {
        for (int i = 0; i < 4; ++i) {
            if (octets[i] != other.octets[i])
                return octets[i] < other.octets[i];
        }
        return false;  // 相等
    }
};

std::string to_string(const IPAddress& ip) {
    return std::to_string(ip.octets[0]) + "." +
           std::to_string(ip.octets[1]) + "." +
           std::to_string(ip.octets[2]) + "." +
           std::to_string(ip.octets[3]);
}

class IPBlacklist {
public:
    void block(IPAddress ip) {
        auto [it, inserted] = blocked_.insert(ip);
        if (inserted)
            std::cout << "[封禁] " << to_string(ip) << "\n";
        else
            std::cout << "[重复] " << to_string(ip) << " 已在黑名单\n";
    }

    bool isBlocked(const IPAddress& ip) const {
        return blocked_.find(ip) != blocked_.end();
    }

    // 列出某个 IP 段内的所有封禁 IP
    void listRange(const IPAddress& start, const IPAddress& end) const {
        auto lo = blocked_.lower_bound(start);
        auto hi = blocked_.upper_bound(end);
        int count = 0;
        for (auto it = lo; it != hi; ++it) ++count;
        std::cout << "IP 段 " << to_string(start) << " ~ "
                  << to_string(end) << " 共封禁 " << count << " 个\n";
    }

private:
    std::set<IPAddress> blocked_;
};

int main() {
    IPBlacklist blacklist;

    blacklist.block({192, 168, 1, 100});
    blacklist.block({10, 0, 0, 55});
    blacklist.block({192, 168, 1, 50});
    blacklist.block({192, 168, 1, 200});
    blacklist.block({10, 0, 0, 55});  // 重复

    std::cout << std::boolalpha;
    std::cout << "192.168.1.100 是否封禁: "
              << blacklist.isBlocked({192, 168, 1, 100}) << "\n";
    std::cout << "192.168.1.99 是否封禁: "
              << blacklist.isBlocked({192, 168, 1, 99}) << "\n";

    blacklist.listRange({192, 168, 1, 0}, {192, 168, 1, 150});
}

预期输出：

[封禁] 192.168.1.100
[封禁] 10.0.0.55
[封禁] 192.168.1.50
[封禁] 192.168.1.200
[重复] 10.0.0.55 已在黑名单
192.168.1.100 是否封禁: true
192.168.1.99 是否封禁: false
IP 段 192.168.1.0 ~ 192.168.1.150 共封禁 2 个

逐段分析：

operator< 按八位组数值排序，而非字典序（10 < 192 vs "10" > "192"）
insert 返回 pair<iterator, bool>，可判断是否插入成功（键唯一）
find O(log n) 查找，lower_bound / upper_bound 实现范围查询

易错场景与面试考点

易错场景

1. map 的 operator[] 会插入默认值

std::map<std::string, int> m;
int x = m["不存在"];  // 插入 {"不存在", 0}！
// 应使用 find 或 at()

2. 自定义比较器必须严格弱序

struct BadCompare {
    bool operator()(int a, int b) const {
        return a <= b;  // ❌ 不满足严格弱序（= 不能为 true）
    }
};
std::set<int, BadCompare> s;  // 未定义行为！

3. 修改 map 的 key

std::map<int, std::string> m{{1, "大翔"}};
auto it = m.begin();
// it->first = 2;   // ❌ first 是 const，不能修改
m.insert_or_assign(2, m.extract(1).mapped());  // C++17 正确方法

面试考点

考点	要点
底层实现	红黑树，O(log n) 操作
lower_bound / upper_bound	二分查找边界，区间查询
equal_range	返回 `pair<lower_bound, upper_bound>`
operator[] vs at	`[]` 插入默认值，`at()` 抛异常
自定义比较器	严格弱序，`a < a` 必须为 false
multiset/multimap	允许重复键，equal_range 用于遍历
insert 返回值	`pair<iterator, bool>`，bool 表示是否插入成功