笔记

根据往年题目，可以将题型分为三种：算法题目；高程相关（模版等）；大模拟（参考 CSP 第 3 题）；其他课程相关（如编译原理） 本笔记仅整理高程相关的面向对象知识点及语法

模板实现 stl

HashMap

#include <iostream>
#include <functional> // for std::hash

// 自定义哈希映射类
template<class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
class CustomHashMap {
private:
    struct Entry {
        Key key;
        T value;
        Entry(const Key& k, const T& v) : key(k), value(v) {}
    };

    std::vector<std::list<Entry>> table;
    size_t capacity;
    Hash hasher;
    KeyEqual key_equal;
    size_t size;

    size_t hash(const Key& key) const {
        return hasher(key) % capacity;
    }

public:
    CustomHashMap(size_t cap = 101) : capacity(cap), table(cap), size(0) {}

    void insert(const Key& key, const T& value) {
        size_t index = hash(key);
        for (auto& entry : table[index]) {
            if (key_equal(entry.key, key)) {
                entry.value = value; // 更新现有键的值
                return;
            }
        }
        table[index].emplace_back(key, value);
        size++;
    }

    bool get(const Key& key, T& value) const {
        size_t index = hash(key);
        for (const auto& entry : table[index]) {
            if (key_equal(entry.key, key)) {
                value = entry.value;
                return true;
            }
        }
        return false;
    }

    bool remove(const Key& key) {
        size_t index = hash(key);
        auto& entries = table[index];
        for (auto it = entries.begin(); it != entries.end(); ++it) {
            if (key_equal(it->key, key)) {
                entries.erase(it);
                size--;
                return true;
            }
        }
        return false;
    }

    bool contains(const Key& key) const {
        size_t index = hash(key);
        for (const auto& entry : table[index]) {
            if (key_equal(entry.key, key)) {
                return true;
            }
        }
        return false;
    }

    void print() const {
        for (size_t i = 0; i < capacity; ++i) {
            if (!table[i].empty()) {
                std::cout << "Bucket " << i << ": ";
                for (const auto& entry : table[i]) {
                    std::cout << "(" << entry.key << ", " << entry.value << ") ";
                }
                std::cout << std::endl;
            }
        }
    }
};

// 自定义哈希函数
struct CustomHash {
    size_t operator()(int key) const {
        return key % 10; // 简单的哈希函数示例
    }
};

// 示例使用
int main() {
    // 使用默认哈希函数和键比较函数
    CustomHashMap<int, std::string> myMap;

    // 使用自定义哈希函数
    CustomHashMap<int, std::string, CustomHash> customMap;

    // 插入键值对
    myMap.insert(1, "one");
    customMap.insert(1, "one");

    // 获取并打印值
    std::string value;
    if (myMap.get(1, value)) {
        std::cout << "Default Hash - Key 1 has value: " << value << std::endl;
    }

    if (customMap.get(1, value)) {
        std::cout << "Custom Hash - Key 1 has value: " << value << std::endl;
    }

    return 0;
}

PriorityQueue

#include <vector>
#include <functional>
#include <iostream>
#include <stdexcept>

template<class T, class Compare = std::less<T>>
class PriorityQueue {
public:
    void push(const T& value) {
        data.push_back(value);
        heapify_up(data.size() - 1);
    }

    const T& top() const {
        if (data.empty()) {
            throw std::runtime_error("PriorityQueue is empty");
        }
        return data.front();
    }

    void pop() {
        if (data.empty()) {
            throw std::runtime_error("PriorityQueue is empty");
        }
        std::swap(data.front(), data.back());
        data.pop_back();
        if (!data.empty()) {
            heapify_down(0);
        }
    }

    bool empty() const {
        return data.empty();
    }

    size_t size() const {
        return data.size();
    }

private:
    std::vector<T> data;
    Compare compare;

    void heapify_up(size_t index) {
        while (index > 0) {
            size_t parent = (index - 1) / 2;
            if (compare(data[parent], data[index])) {
                std::swap(data[parent], data[index]);
                index = parent;
            } else {
                break;
            }
        }
    }

    void heapify_down(size_t index) {
        size_t left = 2 * index + 1;
        size_t right = 2 * index + 2;
        size_t largest = index;

        if (left < data.size() && compare(data[largest], data[left])) {
            largest = left;
        }
        if (right < data.size() && compare(data[largest], data[right])) {
            largest = right;
        }
        if (largest != index) {
            std::swap(data[index], data[largest]);
            heapify_down(largest);
        }
    }
};

int main() {
    PriorityQueue<int, std::less<int>> pq; // 使用 std::less<int> 实现最大堆

    pq.push(3);
    pq.push(1);
    pq.push(4);

    std::cout << "Top element: " << pq.top() << std::endl; // 输出 4

    pq.pop();
    std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 3

    return 0;
}