C++STL映射map和unordered_map使用方法-C++-PHP中文网

map基于红黑树，有序且性能稳定，适用于需排序或范围查询的场景；unordered_map基于哈希表，平均操作为O(1)，但无序且最坏情况为O(N)，适合对性能敏感且无需排序的场景。选择时应根据是否需要键的顺序、性能要求及自定义类型的支持复杂度来决定。两者在API上相似，但底层机制不同，理解差异有助于高效编程。使用自定义类型作键时，map需定义正确的operator<或比较器以保证严格弱序，而unordered_map需提供哈希函数和operator==，并确保哈希一致性，否则会导致未定义行为。

c++stl映射map和unordered_map使用方法

C++ STL中的

map

登录后复制

和

unordered_map

登录后复制

都是用来存储键值对（key-value pairs）的容器，它们的核心功能都是通过键快速查找对应的值。但它们在底层实现、性能特性以及适用场景上有着本质的区别：

map

登录后复制

基于红黑树实现，键默认是有序的，而

unordered_map

登录后复制

则基于哈希表实现，键的顺序是不可预测的，但平均查找速度更快。选择哪一个，往往取决于你对数据有序性的需求以及对性能稳定性的考量。

std::map

登录后复制

和

std::unordered_map

登录后复制

的使用方法在API层面有很多相似之处，但理解其内部机制对高效编程至关重要。

解决方案

std::map

登录后复制

是一个有序关联容器，它将键值对按照键的严格弱序进行排序。这意味着当你遍历

map

登录后复制

时，会得到一个按键升序排列的序列。

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

void demonstrate_map() {
    std::map<int, std::string> student_grades;

    // 插入元素
    student_grades[101] = "Alice"; // 推荐的插入方式之一
    student_grades.insert({103, "Charlie"}); // C++11 initializer list
    student_grades.insert(std::make_pair(102, "Bob")); // 使用std::make_pair

    // 访问元素
    std::cout << "Student 101: " << student_grades[101] << std::endl;
    // 使用at()访问，如果键不存在会抛出std::out_of_range异常
    try {
        std::cout << "Student 104: " << student_grades.at(104) << std::endl;
    } catch (const std::out_of_range& e) {
        std::cerr << "Error: " << e.what() << std::endl;
    }

    // 遍历map（元素按键有序输出）
    std::cout << "Map contents (ordered by key):" << std::endl;
    for (const auto& pair : student_grades) {
        std::cout << "ID: " << pair.first << ", Name: " << pair.second << std::endl;
    }

    // 查找元素
    auto it = student_grades.find(102);
    if (it != student_grades.end()) {
        std::cout << "Found student 102: " << it->second << std::endl;
    } else {
        std::cout << "Student 102 not found." << std::endl;
    }

    // 删除元素
    student_grades.erase(101);
    std::cout << "After deleting student 101, map size: " << student_grades.size() << std::endl;
}

登录后复制

std::unordered_map

登录后复制

是一个无序关联容器，它通过哈希表来组织元素，这使得它在平均情况下具有O(1)的查找、插入和删除时间复杂度。但它的缺点是元素没有固定的顺序，并且在最坏情况下（哈希冲突严重）性能可能退化到O(N)。

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
#include <unordered_map>
#include <string>

void demonstrate_unordered_map() {
    std::unordered_map<std::string, int> word_counts;

    // 插入元素
    word_counts["apple"] = 5;
    word_counts.insert({"banana", 3});
    word_counts["apple"]++; // 更新现有元素

    // 访问元素
    std::cout << "Count of apple: " << word_counts["apple"] << std::endl;

    // 遍历unordered_map（元素顺序不确定）
    std::cout << "Unordered Map contents:" << std::endl;
    for (const auto& pair : word_counts) {
        std::cout << "Word: " << pair.first << ", Count: " << pair.second << std::endl;
    }

    // 查找元素
    auto it = word_counts.find("banana");
    if (it != word_counts.end()) {
        std::cout << "Found banana with count: " << it->second << std::endl;
    }

    // 删除元素
    word_counts.erase("apple");
    std::cout << "After deleting apple, map size: " << word_counts.size() << std::endl;
}

int main() {
    std::cout << "--- Demonstrating std::map ---" << std::endl;
    demonstrate_map();
    std::cout << "\n--- Demonstrating std::unordered_map ---" << std::endl;
    demonstrate_unordered_map();
    return 0;
}

登录后复制

map

登录后复制

和

unordered_map

登录后复制

到底该怎么选？性能差异真的那么大吗？

选择

map

登录后复制

还是

unordered_map

登录后复制

，这确实是C++开发中一个很常见的决策点，而且它往往不是一个非黑即白的问题。我个人在项目中遇到这种选择时，通常会先问自己几个问题：数据需要排序吗？性能瓶颈在哪里？键的类型复杂吗？

从底层机制来看，

map

登录后复制

基于红黑树（一种自平衡二叉搜索树），而

unordered_map

登录后复制

基于哈希表。这两种数据结构决定了它们各自的性能曲线和适用场景。

性能差异：

std::map
登录后复制
(红黑树):
- 时间复杂度: 插入、删除、查找操作的平均和最坏时间复杂度都是O(log N)。这里的N是容器中元素的数量。
- 优点: 性能非常稳定和可预测，不会出现哈希表在最坏情况下的性能骤降。键默认有序，可以直接进行范围查询和有序遍历。
- 缺点: 相比哈希表，
```
log N
```
  登录后复制
  操作在N很大时仍然比常数时间慢，而且每个节点通常需要额外的指针存储（比如父、左、右子节点），内存开销相对较大。
std::unordered_map
登录后复制
(哈希表):
- 时间复杂度: 插入、删除、查找操作的平均时间复杂度是O(1)。在理想的哈希函数和负载因子下，这几乎是瞬间完成的。但最坏情况下，如果所有键都哈希到同一个桶（哈希冲突），操作会退化到O(N)，因为此时它就变成了一个链表。
- 优点: 在大多数实际场景中，
```
unordered_map
```
  登录后复制
  的平均性能要远超
```
map
```
  登录后复制
  ，尤其是在需要频繁进行查找和插入操作时。
- 缺点: 性能波动性大，依赖于哈希函数的质量和负载因子。如果哈希函数设计不佳或数据分布特殊，可能导致大量冲突，从而使性能急剧下降。元素无序，不能直接进行有序遍历。内存开销也可能因为需要维护哈希桶数组而变大。

我的看法是，性能差异确实可能“非常大”，尤其是在处理大量数据时。一个O(1)的操作和O(log N)的操作，在N达到百万级别时，差距会是好几倍甚至几十倍。举个例子，如果N是100万，log₂(100万)大约是20。这意味着

map

登录后复制

可能需要20次比较，而

unordered_map

登录后复制

平均只需要1次。但是，这个“大”是平均意义上的，

unordered_map

登录后复制

的那个O(N)的“坑”一旦踩到，可能比

map

登录后复制

的O(log N)还要慢得多。

如何选择？

艺映AI

艺映AI - 免费AI视频创作工具

查看详情

需要键的顺序吗？ 这是最直接的判断标准。如果你需要按键排序遍历，或者需要查找某个范围内的键（比如
```
lower_bound
```
登录后复制
,
```
upper_bound
```
登录后复制
），那么
```
map
```
登录后复制
是唯一的选择。
性能是绝对优先吗？ 如果你的应用对速度极度敏感，并且你可以接受在极少数情况下可能出现的性能波动，或者你能确保键的哈希分布良好，那么
```
unordered_map
```
登录后复制
通常是更好的选择。
键的类型复杂吗？ 如果键是自定义类型，
```
unordered_map
```
登录后复制
需要你提供哈希函数和相等比较运算符，这可能会比
```
map
```
登录后复制
仅仅需要小于运算符更麻烦一些（后面会详细讲）。
内存消耗呢？ 尽管
```
map
```
登录后复制
每个节点有额外指针，但
```
unordered_map
```
登录后复制
在负载因子较低时也可能因为维护大量空桶而消耗更多内存。这需要具体分析。

我通常的经验是，如果对顺序没有特殊要求，我会倾向于先尝试

unordered_map

登录后复制

，因为它在平均情况下的表现确实令人惊艳。但如果遇到性能问题，或者键的类型难以提供高效哈希，又或者需要有序遍历，我就会毫不犹豫地切换到

map

登录后复制

。性能优化很多时候就是这样，在实际场景中不断权衡和调整。

自定义类型作为键，

map

登录后复制

和

unordered_map

登录后复制

各有什么“坑”？

当我们将自定义的结构体或类作为

map

登录后复制

或

unordered_map

登录后复制

的键时，会遇到一些需要特别处理的地方，否则程序可能无法编译，或者运行结果不符合预期。这些“坑”主要是因为两种容器对键的要求不同。

std::map

登录后复制

使用自定义类型作为键的“坑”：

std::map

登录后复制

的底层是红黑树，它需要知道如何对键进行排序。这意味着你的自定义类型必须提供一个严格弱序（Strict Weak Ordering）的比较方式。默认情况下，

map

登录后复制

会尝试使用键类型的

operator<

登录后复制

。

坑1：忘记或错误定义

operator<

登录后复制

。如果你的自定义类型没有定义

operator<

登录后复制

，或者定义的

operator<

登录后复制

不满足严格弱序的要求，编译器会报错。即使编译通过，如果

operator<

登录后复制

定义不正确（比如不满足传递性，或者

a < b

登录后复制

和

b < a

登录后复制

同时为false时

登录后复制

和

登录后复制

却不相等），

map

登录后复制

的内部结构可能会被破坏，导致查找失败或行为异常。 示例： 假设我们有一个

Point

登录后复制

结构体作为键。

struct Point {
    int x, y;
    // 错误的operator< 定义：只比较x，如果x相同则认为是相等，但y可能不同
    // 这样会导致 (1,5) 和 (1,10) 被认为是相等的，但它们实际不同
    // bool operator<(const Point& other) const {
    //     return x < other.x;
    // }

    // 正确的operator< 定义：先比较x，x相同再比较y
    bool operator<(const Point& other) const {
        if (x != other.x) {
            return x < other.x;
        }
        return y < other.y;
    }
};

// 或者，你可以提供一个自定义的比较器作为map的模板参数
struct PointCmp {
    bool operator()(const Point& a, const Point& b) const {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    }
};
// std::map<Point, std::string, PointCmp> myMap;

登录后复制

建议： 始终确保你的

operator<

登录后复制

是

const

登录后复制

成员函数，并且满足严格弱序的要求。对于复合类型，通常是按成员逐个比较。C++20引入的

operator<=>

登录后复制

（三向比较运算符）可以大大简化这个过程。

std::unordered_map

登录后复制

使用自定义类型作为键的“坑”：

std::unordered_map

登录后复制

依赖哈希表，它需要知道如何计算键的哈希值以及如何判断两个键是否相等。

坑1：忘记或错误定义哈希函数。

unordered_map

登录后复制

默认会尝试使用

std::hash<KeyType>

登录后复制

。如果你的自定义类型没有对应的

std::hash

登录后复制

特化，或者你没有提供一个自定义的哈希函数，编译器会报错。 示例： 继续使用

Point

登录后复制

结构体。

struct Point {
    int x, y;
    // unordered_map还需要这个来判断两个键是否真正相等
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 方式一：特化std::hash
namespace std {
    template <> struct hash<Point> {
        std::size_t operator()(const Point& p) const {
            // 一个简单的哈希组合方式，实际项目中可能需要更复杂的算法
            // 这里使用std::hash对int进行哈希，然后异或组合
            return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
        }
    };
}
// 此时可以直接：std::unordered_map<Point, std::string> myUnorderedMap;

// 方式二：提供一个自定义哈希函数对象作为模板参数
struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};
// std::unordered_map<Point, std::string, PointHash> myUnorderedMap;

登录后复制

建议： 确保哈希函数返回

std::size_t

登录后复制

。哈希函数的质量直接影响

unordered_map

登录后复制

的性能，一个好的哈希函数应该能将不同的键均匀地分布到不同的哈希值。

坑2：忘记或错误定义
```
operator==
```
登录后复制
。
```
unordered_map
```
登录后复制
在哈希冲突时，会使用
```
operator==
```
登录后复制
来判断桶中哪个元素才是我们要找的。如果你的自定义类型没有定义
```
operator==
```
登录后复制
，或者定义不正确，程序可能无法编译，或者在哈希冲突时找不到正确的元素。 建议：
```
operator==
```
登录后复制
也应该是
```
const
```
登录后复制
成员函数，并且要确保它能正确判断两个对象是否相等。
坑3：哈希函数与
```
operator==
```
登录后复制
不一致。 这是最隐蔽也最致命的“坑”。C++标准要求，如果两个键
```
a
```
登录后复制
和
```
b
```
登录后复制
通过
```
operator==
```
登录后复制
判断是相等的（即
```
a == b
```
登录后复制
为真），那么它们的哈希值也必须相等（即
```
std::hash<KeyType>()(a) == std::hash<KeyType>()(b)
```
登录后复制
）。如果这个要求不满足，
```
unordered_map
```
登录后复制
的行为将是未定义的，可能会导致元素丢失、查找失败等各种奇怪问题。 **示例