// ===== CodeLab: C++ STL 容器:map 与 set =====
// 来源: https://aoerliang.dpdns.org/articles/cpp-stl-map
// 以下代码片段按文章出现顺序拼接, 共 5 段

// ----- 片段 1 (cpp) -----
#include <map>
#include <string>
using namespace std;

map<string, int> scores;
scores["Alice"] = 95;      // 插入
scores["Bob"] = 88;
scores["Alice"] = 96;      // 覆盖旧值

// 统计词频的经典写法
map<string, int> freq;
freq[word]++;              // 不存在则先插入 0 再加 1

// ----- 片段 2 (cpp) -----
// find:找不到返回 end()
auto it = scores.find("Alice");
if (it != scores.end()) {
    cout << it->first << " = " << it->second;
}

// count:0 或 1,判断键是否存在
if (scores.count("Tom") == 0) {
    cout << "Tom 不在表中";
}

scores.erase("Bob");            // 按键删除
scores.erase(scores.begin());   // 按迭代器删除

// ----- 片段 3 (cpp) -----
#include <set>

set<int> s = {5, 3, 8, 3, 1};   // 自动排序并去重 → {1,3,5,8}
s.insert(3);                    // 已存在,插入失败
s.insert(7);                    // → {1,3,5,7,8}

if (s.count(5)) {               // 成员判断 O(log n)
    cout << "5 在集合中";
}

// 求有序集合的边界
auto lo = s.lower_bound(3);     // 第一个 >= 3 的元素
auto up = s.upper_bound(5);     // 第一个 > 5 的元素

// ----- 片段 4 (cpp) -----
#include <unordered_map>

unordered_map<int, int> cnt;
for (int x : nums) cnt[x]++;    // 统计频次,平均 O(1)

// 注意:哈希容器没有 lower_bound,
// 遍历顺序也不保证与插入一致

// ----- 片段 5 (cpp) -----
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> pos;   // 值 → 下标
    for (int i = 0; i < nums.size(); ++i) {
        int need = target - nums[i];
        if (pos.count(need)) {
            return {pos[need], i};
        }
        pos[nums[i]] = i;
    }
    return {};
}