CSP-S 备考之 STL 容器关联容器键类型的深度剖析

在 CSP-S 备考的 3 - 4 个月基础学习阶段，STL 容器中的关联容器是一个重要的知识点，尤其是 map 和 unordered_map 中键类型的限制及自定义键类型的适配方法。

一、关联容器键类型的基本限制

对于 map 容器，其键类型必须支持严格弱序。这意味着在进行元素比较时，要遵循一定的规则，能够明确地判断一个键是否小于另一个键。例如，常见的基本数据类型如 int、double 等都满足这个要求。

而 unordered_map 容器则要求键类型必须有哈希函数和等于谓词。哈希函数用于将键映射到一个桶中，以便快速查找；等于谓词用于判断两个键是否相等。

二、自定义键类型时的适配方法

当我们使用自定义的键类型时，就需要进行相应的适配。

对于 map ，需要定义小于运算符（operator<）。比如我们自定义一个结构体作为键类型：

struct MyKey {
    int a;
    int b;

    bool operator<(const MyKey& other) const {
        if (a < other.a) return true;
        if (a == other.a && b < other.b) return true;
        return false;
    }
};

对于 unordered_map ，则需要提供哈希函数和等于运算符（operator==）。可以这样实现：

struct MyKey {
    int a;
    int b;

    bool operator==(const MyKey& other) const {
        return a == other.a && b == other.b;
    }
};

struct MyKeyHash {
    std::size_t operator()(const MyKey& k) const {
        return std::hash<int>()(k.a) ^ std::hash<int>()(k.b);
    }
};

// 使用时
std::unordered_map<MyKey, int, MyKeyHash> myMap;

总之，在备考 CSP-S 的过程中，深入理解 STL 容器关联容器键类型的限制及适配方法，对于解决相关问题至关重要。通过大量的练习和实际应用，能够更好地掌握这一知识点，为后续的竞赛打下坚实的基础。

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！