C++ STL中实现容器映射主要依赖std::map和std::unordered_map，前者基于红黑树，保证按键有序，操作复杂度为O(log N)，适合需要顺序访问或范围查询的场景；后者基于哈希表，平均操作复杂度为O(1)，性能更高但不保证顺序，适用于对查询速度要求高且无需排序的场合。选择时需权衡有序性、性能和内存开销。自定义类型作键时，std::map需重载operator
在C++的STL中，要实现容器的映射功能，我们主要依赖于
std::map
和
std::unordered_map
这两种关联容器。它们的核心思想都是将一个“键”（Key）与一个“值”（Value）关联起来，形成一对一或一对多的映射关系，方便我们通过键快速查找对应的值。说白了，就是给你一个标签，你就能找到它背后的内容。
解决方案
实现容器映射，最直接的办法就是使用STL提供的
std::map
和
std::unordered_map
。
std::map
是基于红黑树实现的，它能保证所有元素都按键的顺序进行存储。这意味着当你遍历一个
std::map
时，你会得到一个按键排序的结果。它的查找、插入和删除操作的平均时间复杂度都是 O(log N)，这里的N是容器中元素的数量。如果你对数据的顺序有要求，或者需要进行范围查询，
std::map
是个不错的选择。
#include #include
而
std::unordered_map
则完全是另一番光景，它基于哈希表实现。它的优势在于，在理想情况下，查找、插入和删除操作的平均时间复杂度可以达到 O(1)，也就是常数时间。这对于需要极高性能查询的场景非常诱人。但它不保证元素的顺序，遍历结果是无序的。如果哈希函数设计不当，或者遇到大量哈希冲突，最坏情况下性能会退化到 O(N)。
立即学习“C++免费学习笔记（深入）”；
#include #include #include int main() { std::unordered_map student_scores; // 插入元素 student_scores["Alice"] = 95; student_scores["Bob"] = 88; student_scores.insert({"Charlie", 92}); // 查找元素 auto it = student_scores.find("Bob"); if (it != student_scores.end()) { std::cout << "Bob's score: " <second << std::endl; } // 遍历元素 (无序) std::cout << "Unordered map elements:" << std::endl; for (const auto& pair : student_scores) { std::cout << pair.first << ": " << pair.second << std::endl; } return 0;}
选择哪个，就看你对顺序有没有要求，以及对性能的侧重点了。
std::map 与 std::unordered_map 之间如何选择？
在我看来，这两种映射容器的选择，其实是C++编程中一个很经典的权衡问题，没有绝对的“最好”，只有“最适合”。
首先，我们得明白它们的核心差异：
std::map
强调的是有序性，它的底层是红黑树，这是一种自平衡二叉搜索树。这意味着当你需要迭代器按照键的升序（或自定义顺序）访问元素时，
std::map
是你的不二之选。比如，你想按学生姓名的字母顺序打印成绩单，或者需要查找某个范围内的键值对，
std::map
能轻松满足。然而，红黑树的操作复杂度是 O(log N)，这意味着随着数据量的增长，每次查找、插入或删除操作的时间成本会以对数级别增长。对于小规模数据，这可能不是问题，但对于百万千万级别的数据，O(log N) 的开销就可能变得可观。
std::unordered_map
则完全放弃了键的有序性，转而追求极致的平均性能。它基于哈希表实现，通过哈希函数将键映射到表中的一个“桶”里。理想情况下，哈希函数能将键均匀地分布到各个桶中，这样查找、插入和删除的平均时间复杂度就能达到惊人的 O(1)。这在处理海量数据且对顺序无要求时，性能优势是压倒性的。比如，你可能只是需要快速判断一个用户ID是否存在，或者根据商品SKU快速获取库存信息，
std::unordered_map
能提供近乎瞬时的响应。但要注意，这是“平均”情况，如果哈希函数设计不好，或者数据本身导致大量哈希冲突，那么性能可能会退化到 O(N)，甚至比
std::map
还慢。此外，
std::unordered_map
通常会比
std::map
占用更多的内存，因为它需要维护一个哈希表结构，包括可能存在的空桶。
所以，我的经验是：
如果数据量不大，或者需要键的有序性，或者需要进行范围查询，或者对最坏情况的性能有严格要求（O(log N) 是稳定的），那就用
std::map
。如果数据量很大，对键的顺序没有要求，且追求极致的平均查询、插入、删除速度，并且能够接受在极少数情况下可能出现的性能波动（哈希冲突），那就用
std::unordered_map
。另外，自定义类型作为键时，
std::unordered_map
需要你提供一个好的哈希函数和相等比较器，这会增加一些实现上的复杂性，而
std::map
只需要一个小于比较器。
自定义类型作为键时，需要注意哪些实现细节？
当我们要用自定义的类或结构体作为
std::map
或
std::unordered_map
的键时，就不能像使用
int
或
std::string
那样直接了。容器需要知道如何比较这些自定义键，或者如何为它们生成哈希值。
对于
std::map
，它依赖于键的严格弱序（Strict Weak Ordering）。这意味着它需要知道如何判断一个键是否“小于”另一个键。最常见的做法是重载
operator<
作为类的成员函数或友元函数。
#include #include
如果没有重载
operator<
，也可以提供一个自定义的比较器作为
std::map
的模板参数，比如
std::map
。
对于
std::unordered_map
，它需要两样东西：
哈希函数 (Hash Function)：一个能够将自定义类型转换为
std::size_t
类型哈希值的函数。相等比较器 (Equality Comparator)：一个能够判断两个自定义类型对象是否相等的函数。通常通过重载
operator==
来实现。
哈希函数通常通过特化
std::hash
模板或者提供一个自定义的哈希函数对象（functor）来实现。
#include #include #include #include // for std::hashstruct CustomKey { int id; std::string name; // 1. 重载相等运算符 bool operator==(const CustomKey& other) const { return id == other.id && name == other.name; } // 为了方便打印 friend std::ostream& operator<<(std::ostream& os, const CustomKey& k) { return os << "{" << k.id << ", " << k.name << "}"; }};// 2. 为 CustomKey 特化 std::hashnamespace std { template struct hash { std::size_t operator()(const CustomKey& k) const { // 一个简单的哈希组合方法，通常会用 boost::hash_combine 或类似技术 // 这里为了示例，简单组合 std::size_t h1 = std::hash{}(k.id); std::size_t h2 = std::hash{}(k.name); return h1 ^ (h2 << 1); // 简单的哈希组合 } };}int main() { std::unordered_map data_map; data_map[{101, "Apple"}] = 1.99; data_map[{203, "Banana"}] = 0.79; data_map[{101, "Apple"}] = 2.05; // 会更新已有值 std::cout << "Value for {101, Apple}: " << data_map[{101, "Apple"}] << std::endl; for (const auto& pair : data_map) { std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl; } return 0;}
哈希函数的质量至关重要。一个好的哈希函数应该能将不同的键尽可能均匀地分布到不同的哈希值上，减少冲突，从而保证
std::unordered_map
的平均 O(1) 性能。如果哈希函数总是返回相同的值，那
unordered_map
就会退化成链表，性能直接掉到 O(N)。
除了基本的映射，STL还有哪些高级或变种用法可以实现类似功能？
除了
std::map
和
std::unordered_map
这两个最直接的映射容器，STL及其周边还有一些变种或技巧可以实现类似映射的功能，或者处理更复杂的映射场景。
一个很常见的变种是一对多映射，即一个键可以对应多个值。STL提供了
std::multimap
和
std::unordered_multimap
来解决这个问题。它们的使用方式和
std::map
/
std::unordered_map
类似，只是当插入一个已存在的键时，它们不会覆盖旧值，而是将新值添加到该键对应的集合中。查找时，你需要通过
equal_range
方法获取一个迭代器范围，来访问所有与该键关联的值。
#include #include
另一种不太直接但有时有效的“映射”方式，特别是在键空间有限且连续、或者数据量相对较小但需要极高查询速度时，可以考虑使用
std::vector
配合
std::pair
或自定义结构体，然后进行排序和二分查找。这本质上是模拟
std::map
的底层机制，但少了红黑树的动态平衡开销。
#include #include #include #include // For std::sort and std::lower_boundstruct DataEntry { int id; std::string value; bool operator<(const DataEntry& other) const { return id < other.id; }};int main() { std::vector data = { {3, "Banana"}, {1, "Apple"}, {5, "Cherry"} }; // 排序，使其可以进行二分查找 std::sort(data.begin(), data.end()); // 查找 ID 为 3 的元素 int target_id = 3; auto it = std::lower_bound(data.begin(), data.end(), DataEntry{target_id, ""}); if (it != data.end() && it->id == target_id) { std::cout << "Found ID " << target_id << ": " <value << std::endl; } else { std::cout << "ID " << target_id << " not found." << std::endl; } return 0;}
这种方式在数据量固定且不常变动时，可以避免
std::map
每次插入的节点分配和平衡开销。插入新元素时需要重新排序或保持有序插入，开销会比较大。
此外，如果你需要一个非常稀疏的整数到值的映射，并且键的范围可能非常大但实际使用的键很少，有时可以考虑使用
std::vector
结合一个偏移量，或者直接用
std::map
。对于非常小的、连续的整数键，直接使用
std::vector
或
std::array
作为查找表，通过索引访问，性能是最高的 O(1)。
总之，STL提供了丰富的工具箱，关键在于理解它们的底层机制和性能特性，然后根据具体的应用场景和需求做出最合适的选择。
以上就是C++如何在STL中实现容器映射功能的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1476019.html
微信扫一扫 
支付宝扫一扫 
