孙意讲解STL映射：东北大学秦皇岛ACM培训中map详解

STL（Standard Template Library）是C++编程语言的标准库，它提供了一系列模板类和算法，使得开发者可以方便地处理各种数据结构。在这一天的主题"STL应用专题——day 3 映射.pptx"中，主要关注了STL中的map容器。 map是STL中的一种关联容器，它实现了键值对（key-value）的存储和访问。map内部使用红黑二叉树（Red-Black Tree）作为其底层数据结构，这使得map中的数据是有序的，根据键（key）自动排序，从而简化了查找、插入和删除操作。它的主要特点包括： 1. **自动键值对应**：map确保每个键（key）都唯一对应一个值（value），这在处理去重问题时非常有用。 2. **高效查找**：插入、删除和查找操作的时间复杂度通常为O(log n)，这是因为红黑树提供了良好的平衡性。 3. **可变类型支持**：key和value可以是任意类型，包括自定义类型，提供了极大的灵活性。 4. **基本操作**： - `begin()`和`end()`函数用于获取迭代器，分别指向map的起始和结束位置。 - `empty()`检查map是否为空。 - `find(key)`函数用于查找指定键，返回一个迭代器指向键对应的值，如果没有找到则返回`end()`。 - `count(key)`计算键的出现次数，返回0或1。 - `size()`返回map中元素的数量。 在实际编程中，创建map实例和插入数据可以通过以下方式实现： ```cpp #include <map> map<int, string> map_student; // 插入数据 map_student.insert({1, "student1"}); // 使用make_pair或者value_type构造 // 或者 // map_student[1] = "student1"; // 数组方法，可能会覆盖已有键的值 // 遍历map for (auto it = map_student.begin(); it != map_student.end(); ++it) { std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl; } // 查找 auto it = map_student.find(1); // 如果找到1，则输出对应的学生名 if (it != map_student.end()) { std::cout << "Found student with id 1: " << it->second << std::endl; } else { std::cout << "Student with id 1 not found." << std::endl; } ``` STL中的map是C++编程中一种强大的数据结构，它提供了高效且有序的数据存储和查询功能，广泛应用于需要按键查找和管理关联数据的场景。熟练掌握map的使用和操作，能够极大提升程序的组织和性能。