[笔记]C++容器基础之Map| Kai@Codehubble
|
39
|
0
|
C++

2929 字
|
26 分钟

1. Map

在 C++ 标准库的容器家族中，std::map 绝对是 “明星成员”—— 它以键值对（Key/Value Pair）的形式存储数据，支持高效的查找、插入和删除操作，在数据映射、快速检索等场景中应用广泛（比如配置项存储、用户信息匹配等）。今天这篇文章，我们就从 map 的核心特性出发，一步步拆解它的用法、语法演进，以及同类容器 multimap 的差异，帮你彻底掌握这个实用工具。

特点：

  • 不允许有重复的 Key
  • map 存储的对象必须是具备可排序性的
  • 默认采用 less 定义排序行为
  • 可以自定义排序行为（通过仿函数）

1.1 初始化

初始化std::map，现在可以直接使用{}初始化列表。示例代码如下：

#include <iostream>
#include <map>
#include <string>

struct Employee {
    std::string Name;
    Employee(const std::string& wszName) : Name(wszName) {}
};

struct ReverseId {
    bool operator() (const int& key1, const int& key2) const {
        return (key1 <= key2)? false : true;
    }
};

int main() {
    // 使用初始化列表初始化std::map
    std::map<int, Employee, ReverseId> map1 = {
        {1, Employee("Tom")},
        {2, Employee("Jerry")},
        {3, Employee("Alice")}
    };

    for (const auto& [key, value] : map1) {
        std::cout << key << ": " << value.Name << std::endl;
    }

    return 0;
}

在上述代码中，通过{ {键值对1}, {键值对2},... }的形式直接初始化std::map，相比于旧的通过数组和指针的方式更加简洁明了。

在 C++17 中，对于一些标准库容器，引入了模板参数自动推导（Class Template Argument Deduction）。不过std::map由于存在多个模板参数（键类型、值类型、比较器类型），目前还不能完全利用 CTAD 进行最简化的声明，但对于只有键值类型的简单情况可以有一定的便利。例如：

#include <map>
#include <string>
int main() {
    // 这里编译器可以自动推导键值类型
    std::map m = { {1, "one"}, {2, "two"} }; 
    return 0;
}

但如果要自定义比较器，还是需要像之前那样显式指定模板参数 。

综上所述，C++11 及之后的标准在std::map的初始化和使用上提供了多种简化方式，提升了代码的可读性和编写效率。

1.2 插入元素

（1）insert() 函数：最安全，支持批量插入

insert() 是 map 插入的 “标准接口”，支持单个插入、批量插入，且遇到重复键会忽略插入（不会覆盖现有值），适合需要 “去重” 的场景：

#include <map>
#include <string>

std::map<int, std::string> empMap = {{1, "Tom"}, {2, "Jerry"}};

// 1. 插入单个pair（两种写法）
empMap.insert(std::make_pair(3, "Alice")); // C++98风格
empMap.insert({4, "Brown"});               // C++11+列表风格，更简洁

// 2. 批量插入（初始化列表）
empMap.insert({
    {5, "Fisher"},
    {6, "Lily"}
});

// 3. 检查插入结果（insert返回pair<iterator, bool>，bool表示是否插入成功）
auto result = empMap.insert({1, "Tom2"}); // 键1已存在，插入失败
if (!result.second) {
    std::cout << "键 " << result.first->first << " 已存在，值为：" << result.first->second << std::endl;
}

（2）operator[]：最简洁，但有 “陷阱”

[] 是 map 存取的 “快捷方式”，插入时直接通过 “键” 赋值即可，代码非常简洁，但要注意陷阱：
如果键不存在，[] 会自动插入一个 “默认构造的值”（比如 std::string 默认是空字符串，int 默认是 0），这可能导致意外的数据插入。

std::map<int, std::string> empMap = {{1, "Tom"}};

// 1. 插入新键（键2不存在，自动插入）
empMap[2] = "Jerry"; 

// 2. 修改已有键的值（键1存在，直接覆盖）
empMap[1] = "Tom Updated"; 

// 3. 陷阱：误插入默认值
std::cout << empMap[3]; // 键3不存在，自动插入 {3, ""}，输出空字符串

适用场景：确认键存在时修改值，或明确需要 “不存在则插入” 的场景。

（3）emplace()：C++11+ 高效插入，避免拷贝

emplace() 是 C++11 新增的插入方式，它直接在 map 内部构造 pair 对象，避免了 insert() 中可能的临时对象拷贝，效率更高：

std::map<int, Employee> empMap;

// emplace直接传入构造Employee的参数，内部构造pair
empMap.emplace(1, "Tom"); // 等价于 insert({1, Employee("Tom")})
empMap.emplace(2, "Jerry");

1.3 存取元素

（1）operator[]：快捷但有陷阱（前面提过）

Employee& e = map1[2];  
e.SetName(L"...");  
...

（2）at()：C++11+ 安全存取，不存在键抛异常

at() 是 C++11 新增的存取接口，只访问已存在的键，如果键不存在会抛出 std::out_of_range 异常，避免了 [] 的 “误插入” 陷阱，适合需要 “严格检查键存在性” 的场景：

#include <map>
#include <string>
#include <stdexcept>

std::map<int, std::string> empMap = {{1, "Tom"}, {2, "Jerry"}};

// 1. 访问已存在的键（正常返回值）
std::string& name = empMap.at(1);
name = "Tom Updated"; // 修改值

// 2. 访问不存在的键（抛异常）
try {
    empMap.at(3); // 键3不存在，抛出std::out_of_range
} catch (const std::out_of_range& e) {
    std::cout << "访问失败：" << e.what() << std::endl;
}

1.4 查找元素

（1）find()：返回迭代器，快速定位键

find() 是 map 查找的 “首选接口”，根据键查找，返回指向该键的迭代器；如果不存在，返回 end() 迭代器。由于 map 底层是红黑树，find() 的时间复杂度是 O(logn)，非常高效：

#include <map>
#include <string>
#include <iostream>

std::map<int, std::string> empMap = {{1, "Tom"}, {2, "Jerry"}, {3, "Alice"}};

// 查找键2
auto it = empMap.find(2);
if (it != empMap.end()) {
    std::cout << "找到键 " << it->first << "，值为：" << it->second << std::endl;
} else {
    std::cout << "未找到该键" << std::endl;
}

（2）count()：返回键的个数，适合 “检查存在性”

map 的键唯一，所以 count() 的返回值只有 0 或 1——0 表示键不存在，1 表示存在。用法比 find() 更简洁，适合只需要 “判断键是否存在” 的场景：

if (empMap.count(3)) {
    std::cout << "键3存在" << std::endl;
} else {
    std::cout << "键3不存在" << std::endl;
}

1.5 遍历

C++11 之前（C++98/03）的遍历方式

没有范围循环和auto，必须显式声明迭代器类型，通过begin()/end()控制循环范围，且需通过->first/->second访问键值：

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<int, std::string> myMap;
    myMap.insert(std::make_pair(1, "apple"));
    myMap.insert(std::make_pair(2, "banana"));
    myMap.insert(std::make_pair(3, "cherry"));

    // 方式1：普通迭代器遍历
    for (std::map<int, std::string>::iterator it = myMap.begin(); 
         it != myMap.end(); ++it) {
        int key = it->first;
        std::string value = it->second;
        std::cout << "Key: " << key << ", Value: " << value << std::endl;
    }

    // 方式2：常量迭代器（只读）
    for (std::map<int, std::string>::const_iterator it = myMap.begin(); 
         it != myMap.end(); ++it) {
        // 此时不能修改it->second，编译会报错
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    return 0;
}

缺点：

  • 迭代器类型声明冗长（std::map<int, std::string>::iterator）
  • 必须手动控制迭代器的起始（begin()）和终止（end()）
  • 访问键值需要通过->first/->second，不够直观

C++11 的遍历方式

引入了范围循环（range-based for loop） 和auto关键字，简化了迭代器声明和循环控制，但仍需通过first/second访问键值：

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<int, std::string> myMap = {
        {1, "apple"},    // C++11初始化列表，比insert更简洁
        {2, "banana"},
        {3, "cherry"}
    };

    // 方式1：通过auto简化迭代器类型，配合范围循环
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    // 方式2：范围循环直接遍历元素（最常用）
    for (const auto& element : myMap) {  // element类型是std::pair<const int, std::string>
        std::cout << "Key: " << element.first << ", Value: " << element.second << std::endl;
    }

    return 0;
}

改进点：

  • auto自动推导迭代器 / 元素类型，避免冗长声明
  • 范围循环for (const auto& element : myMap)无需手动控制begin()/end()，更简洁
  • 初始化列表{ {1, "apple"}, ... }比insert更直观

局限性：

  • 仍需通过element.first/element.second访问键值，不够直接

C++17 的遍历方式

在 C++11 基础上，引入结构化绑定（structured binding），可以直接将键值对解包为两个变量：

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<int, std::string> myMap = {
        {1, "apple"},
        {2, "banana"},
        {3, "cherry"}
    };

    // 结构化绑定直接解包键和值
    for (const auto& [key, value] : myMap) {  // [key, value]对应pair的first和second
        std::cout << "Key: " << key << ", Value: " << value << std::endl;
    }

    return 0;
}
  • 通过[key, value]直接绑定std::pair的两个成员，无需first/second
  • 代码可读性大幅提升，直观反映 "遍历键值对" 的意图

总结

可以看出，从 C++98 到 C++17，std::map的遍历语法逐渐向 "简洁化、直观化" 演进，尤其是 C++17 的结构化绑定，让代码最接近自然语言的表达逻辑。

1.6 删除元素

erase() 是 map 删除的核心函数，支持按 “迭代器”“键”“范围” 删除，灵活度很高：

std::map<int, std::string> empMap = {{1, "Tom"}, {2, "Jerry"}, {3, "Alice"}, {4, "Brown"}};

// 1. 按迭代器删除（删除第一个元素）
auto it = empMap.begin();
empMap.erase(it); // 删除 {1, "Tom"}

// 2. 按键删除（删除键3的元素）
size_t deletedCount = empMap.erase(3); // 返回删除的元素个数（map中0或1）
std::cout << "删除了 " << deletedCount << " 个元素" << std::endl; // 输出1

// 3. 按范围删除（删除从键2到末尾的元素）
auto startIt = empMap.find(2); // 找到键2的迭代器
empMap.erase(startIt, empMap.end()); // 删除 {2, "Jerry"}, {4, "Brown"}

注意：删除迭代器后，该迭代器会失效，不能再使用（比如 ++it），需重新获取。

1.6.1 遍历删除元素

一、遍历删除 map 特定元素

std::map 是有序关联容器，底层为红黑树。删除元素时，被删除的迭代器会失效，但其他迭代器不受影响。正确的做法是利用 erase 方法的返回值（下一个有效的迭代器）更新当前迭代器。

方法 1：使用 erase 的返回值（C++11 及以上推荐）

map::erase(iterator) 会返回被删除元素的下一个迭代器，可直接用于更新当前迭代器：

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

int main() {
    map<int, string> myMap = {
        {1, "a"}, {2, "b"}, {3, "c"}, {4, "d"}
    };

    // 目标：删除键为偶数的元素
    auto it = myMap.begin();
    while (it != myMap.end()) {
        if (it->first % 2 == 0) { // 满足删除条件（键为偶数）
            // erase返回下一个有效迭代器，直接赋值给it
            it = myMap.erase(it); 
        } else {
            // 不删除则正常递增迭代器
            ++it; 
        }
    }

    // 打印结果：{1:"a", 3:"c"}
    for (const auto& pair : myMap) {
        cout << pair.first << ":" << pair.second << " ";
    }
    return 0;
}

方法 2：先保存下一个迭代器（兼容 C++11 之前版本）

C++11 之前，map::erase 不返回迭代器，需先通过 it++ 保存下一个迭代器，再删除当前元素：

auto it = myMap.begin();
while (it != myMap.end()) {
    if (it->first % 2 == 0) {
        // 先通过it++获取下一个迭代器，再删除当前元素
        myMap.erase(it++); 
    } else {
        ++it;
    }
}

原理：it++ 会先返回当前迭代器的副本，再递增迭代器，因此删除的是 “旧” 迭代器，而 it 已指向下一步。

1.6.2 遍历删除错误做法及原因

1. 直接删除后递增迭代器：

// 错误！删除后it已失效，++it会导致未定义行为
while (it != myMap.end()) {
    if (condition) {
        myMap.erase(it); 
    }
    ++it; // 若it已被删除，此处操作非法
}

2. 使用范围for循环删除

// 错误！范围for循环内部的迭代器在删除后会失效
for (auto& pair : myMap) {
    if (condition) {
        myMap.erase(pair.first); // 导致循环迭代器失效
    }
}

1.7. 清空

clear() 是 std::map 的成员函数，调用后会删除容器中所有元素，并将 size() 置为 0，但容器本身仍可继续使用（可重新插入新元素）。

#include <iostream>
#include <map>
#include <string>

int main() {
    // 初始化一个map
    std::map<int, std::string> fruitMap = {
        {1, "苹果"},
        {2, "香蕉"},
        {3, "橙子"}
    };

    std::cout << "清空前元素数量：" << fruitMap.size() << std::endl; // 输出：3

    // 调用clear()清空容器
    fruitMap.clear();

    std::cout << "清空后元素数量：" << fruitMap.size() << std::endl; // 输出：0
    std::cout << "容器是否为空：" << (fruitMap.empty() ? "是" : "否") << std::endl; // 输出：是

    // 清空后仍可插入新元素
    fruitMap.insert({4, "葡萄"});
    std::cout << "重新插入后元素数量：" << fruitMap.size() << std::endl; // 输出：1

    return 0;
}

1.7.1 clear的底层行为

std::map 底层基于红黑树实现，clear() 的本质是遍历红黑树的所有节点并销毁，释放每个节点占用的内存，但不会销毁红黑树的底层结构框架（如根节点指针、分配器等）。

  • 对迭代器的影响：clear() 会使容器中所有迭代器失效（因为所有元素已被删除），调用前获取的迭代器在 clear() 后不可再使用。
  • 对容量的影响：clear() 仅改变 size()（元素数量），不影响 capacity（红黑树的潜在存储能力，标准未明确定义 map 的 capacity 概念）。

clear() 虽删除元素，但部分实现中可能保留红黑树的部分内部结构内存（如空节点、分配器缓存等）。若需彻底释放 map 占用的内存，可结合 “临时对象交换法”：

#include <map>

int main() {
    std::map<int, std::string> myMap;
    // 插入大量元素
    for (int i = 0; i < 10000; ++i) {
        myMap[i] = "test";
    }

    // 方法1：clear()仅删除元素，可能保留部分内存
    myMap.clear();

    // 方法2：与临时map交换，彻底释放内存
    std::map<int, std::string>().swap(myMap); 
    // 临时map析构时会释放所有内存，myMap变为空且内存被释放
}

原理：
创建一个临时空 map，通过 swap() 交换当前 map 与临时 map 的内部数据。临时 map 离开作用域时，会调用析构函数释放所有内存（包括红黑树的结构内存），而原 map 变为空且内存被彻底释放。

1.7.2 与 erase 范围删除的对比

clear() 与 erase(begin(), end()) 功能相似（均删除所有元素），但 clear() 是更简洁的专用接口

2. Multimap

std::multimap 是 map 的 “兄弟容器”，核心特性和 map 几乎一致，但有一个关键区别：允许键重复。当你需要 “一个键对应多个值” 时（比如一个班级对应多个学生、一个关键词对应多个搜索结果），multimap 就派上用场了。

2.1 multimap 的核心特性

  • 键可以重复，插入重复键会成功（不会忽略）；
  • 仍按键排序（默认升序，支持自定义比较器）；
  • 没有 operator[] 接口（因为一个键对应多个值，[] 无法确定返回哪个值）；
  • 查找时用 find() 返回第一个匹配的迭代器，count() 返回键的个数，equal_range() 返回所有匹配的范围。

比如一个班级有多个学生，用 multimap<int, std::string>（键是班级号，值是学生姓名）：

#include <map>
#include <string>
#include <iostream>

// 班级号 -> 学生姓名，允许一个班级多个学生
std::multimap<int, std::string> classMap = {
    {1, "Tom"},
    {1, "Jerry"}, // 键1重复，插入成功
    {2, "Alice"},
    {2, "Brown"},
    {3, "Lily"}
};

// 1. 统计班级1的学生数量
std::cout << "班级1的学生数：" << classMap.count(1) << std::endl; // 输出2

// 2. 查找班级2的所有学生（用equal_range）
auto [startIt, endIt] = classMap.equal_range(2); // C++17结构化绑定
std::cout << "班级2的学生：";
for (auto it = startIt; it != endIt; ++it) {
    std::cout << it->second << " "; // 输出 Alice Brown
}
std::cout << std::endl;

// 3. 遍历所有班级和学生
std::cout << "所有班级学生：" << std::endl;
for (const auto& [classId, student] : classMap) { // C++17结构化绑定
    std::cout << "班级" << classId << "：" << student << std::endl;
}

3. 总结

  1. 选择合适的初始化方式：C++11+ 优先用初始化列表，C++17 无自定义比较器可用 CTAD；
  2. 插入用 emplace ()，避免拷贝：尤其是值类型是自定义类时，emplace() 比 insert() 高效；
  3. 存取用 at () 还是 []：需要安全检查用 at()（抛异常），需要快捷插入用 []（注意误插入）；
  4. 遍历优先选 C++17 结构化绑定：代码最直观，实在用不了 C++17 就用 C++11 的范围 for + auto；
  5. 键重复用 multimap：map 键唯一，multimap 键可重复，根据业务场景选择；
  6. 注意键的可排序性：map 和 multimap 都需要键可排序，自定义键类型必须提供比较器（比如仿函数）。

std::map 作为 C++ 中最常用的关联容器，掌握它的特性和用法，能帮你在数据映射、快速检索场景中写出更高效、更简洁的代码。

STL
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇