Set与Map容器专题

• 竞赛中的重要性：
  • 算法优化的关键工具
  • 简化复杂问题的解决方案
  • 提高代码的可读性和维护性

• 内存效率：
  • 红黑树需要额外的指针空间
  • 每个节点需要存储颜色信息和父子指针
  • 相比哈希表有更高的内存开销

• C++中的实现：

// 自定义哈希函数示例
struct MyHash {
    size_t operator()(const string& s) const {
        return hash<string>()(s);
    }
};

unordered_set<string, MyHash> custom_set;

• 性能影响因素：
  • 哈希函数的质量
  • 负载因子的大小
  • 数据分布的特性
  • 冲突解决策略的效率

• CSP-J/S竞赛特点：
  • 题目难度适中，数据规模可控
  • 注重基础算法和数据结构
  • 推荐：掌握两种类型，根据题意选择

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

int main() {
    int n, x;
    set<int> s;
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        s.insert(x);
    }
    
    cout << s.size() << endl;
    return 0;
}

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

int main() {
    map<string, int> wordCount;
    string word;
    
    while (cin >> word) {
        wordCount[word]++;
    }
    
    for (auto& p : wordCount) {
        cout << p.first << ": " << p.second << endl;
    }
    
    return 0;
}

#include <unordered_map>
#include <list>
using namespace std;

class LRUCache {
private:
    int capacity;
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> map;
    
public:
    LRUCache(int capacity) : capacity(capacity) {}
    
    int get(int key) {
        if (map.find(key) == map.end()) return -1;
        
        // 移动到链表头部
        cache.splice(cache.begin(), cache, map[key]);
        return map[key]->second;
    }
    
    void put(int key, int value) {
        if (map.find(key) != map.end()) {
            // 更新值并移动到头部
            map[key]->second = value;
            cache.splice(cache.begin(), cache, map[key]);
        } else {
            // 插入新元素
            if (cache.size() == capacity) {
                // 删除尾部元素
                map.erase(cache.back().first);
                cache.pop_back();
            }
            cache.emplace_front(key, value);
            map[key] = cache.begin();
        }
    }
};

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

map<string, int> variables;

int evaluate(const string& expr) {
    istringstream iss(expr);
    string token;
    int result = 0;
    char op = '+';
    
    while (iss >> token) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            op = token[0];
        } else {
            int value;
            if (isdigit(token[0])) {
                value = stoi(token);
            } else {
                value = variables[token];
            }
            
            switch (op) {
                case '+': result += value; break;
                case '-': result -= value; break;
                case '*': result *= value; break;
                case '/': result /= value; break;
            }
        }
    }
    
    return result;
}

题目3：缓存模拟

• 要求：使用unordered_map实现简单缓存
• 功能：支持get和put操作
• 限制：缓存大小固定
• 难度：★★☆☆☆

题目6：LRU缓存

• 要求：结合unordered_map和链表实现
• 功能：完整的LRU缓存机制
• 性能：所有操作O(1)时间复杂度
• 难度：★★★★☆

选择原则总结：

1. 需要有序性 → 选择Sorted类型
2. 需要快速访问 → 选择Hash类型
3. 数据量小 → 两者差异不大
4. 数据量大 → 优先考虑Hash类型
5. 需要范围查询 → 只能选择Sorted类型