C++如何在STL中实现容器映射功能-C++-PHP中文网

C++ STL中实现容器映射主要依赖std::map和std::unordered_map，前者基于红黑树，保证按键有序，操作复杂度为O(log N)，适合需要顺序访问或范围查询的场景；后者基于哈希表，平均操作复杂度为O(1)，性能更高但不保证顺序，适用于对查询速度要求高且无需排序的场合。选择时需权衡有序性、性能和内存开销。自定义类型作键时，std::map需重载operator<或提供比较器，std::unordered_map则需特化std::hash并重载operator==以确保正确哈希和比较。此外，STL还提供std::multimap和std::unordered_multimap支持一对多映射，或可通过排序vector结合二分查找实现静态数据的高效映射。

c++如何在stl中实现容器映射功能

在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 <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> student_scores;

    // 插入元素
    student_scores["Alice"] = 95;
    student_scores["Bob"] = 88;
    student_scores.insert({"Charlie", 92}); // 另一种插入方式

    // 查找元素
    if (student_scores.count("Alice")) {
        std::cout << "Alice's score: " << student_scores["Alice"] << std::endl;
    }

    // 遍历元素 (按键排序)
    for (const auto& pair : student_scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 更新元素
    student_scores["Bob"] = 90;
    std::cout << "Bob's updated score: " << student_scores["Bob"] << std::endl;

    return 0;
}

登录后复制

而

std::unordered_map

登录后复制

则完全是另一番光景，它基于哈希表实现。它的优势在于，在理想情况下，查找、插入和删除操作的平均时间复杂度可以达到 O(1)，也就是常数时间。这对于需要极高性能查询的场景非常诱人。但它不保证元素的顺序，遍历结果是无序的。如果哈希函数设计不当，或者遇到大量哈希冲突，最坏情况下性能会退化到 O(N)。

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

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

int main() {
    std::unordered_map<std::string, int> 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: " << it->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<
登录后复制
作为类的成员函数或友元函数。

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

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

struct Point {
    int x;
    int y;

    // 重载小于运算符，实现严格弱序
    bool operator<(const Point& other) const {
        if (x != other.x) {
            return x < other.x;
        }
        return y < other.y;
    }

    // 为了方便打印
    friend std::ostream& operator<<(std::ostream& os, const Point& p) {
        return os << "(" << p.x << ", " << p.y << ")";
    }
};

int main() {
    std::map<Point, std::string> point_names;
    point_names[{1, 2}] = "Top-Left";
    point_names[{3, 1}] = "Bottom-Right";
    point_names[{1, 1}] = "Center";

    for (const auto& pair : point_names) {
        std::cout << "Point " << pair.first << " is " << pair.second << std::endl;
    }
    // 输出会按Point的定义顺序：(1,1), (1,2), (3,1)
    return 0;
}

登录后复制

如果没有重载

operator<

登录后复制

，也可以提供一个自定义的比较器作为

std::map

登录后复制

的模板参数，比如

std::map<Point, std::string, MyPointComparer>

登录后复制

。

对于

std::unordered_map

登录后复制

，它需要两样东西：

哈希函数 (Hash Function)：一个能够将自定义类型转换为
```
std::size_t
```
登录后复制
类型哈希值的函数。
相等比较器 (Equality Comparator)：一个能够判断两个自定义类型对象是否相等的函数。通常通过重载
operator==
登录后复制
来实现。

哈希函数通常通过特化

std::hash

登录后复制

模板或者提供一个自定义的哈希函数对象（functor）来实现。

#include <iostream>
#include <unordered_map>
#include <string>
#include <functional> // for std::hash

struct 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::hash
namespace std {
    template <>
    struct hash<CustomKey> {
        std::size_t operator()(const CustomKey& k) const {
            // 一个简单的哈希组合方法，通常会用 boost::hash_combine 或类似技术
            // 这里为了示例，简单组合
            std::size_t h1 = std::hash<int>{}(k.id);
            std::size_t h2 = std::hash<std::string>{}(k.name);
            return h1 ^ (h2 << 1); // 简单的哈希组合
        }
    };
}

int main() {
    std::unordered_map<CustomKey, double> 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 <iostream>
#include <map>
#include <string>

int main() {
    std::multimap<std::string, std::string> student_courses;
    student_courses.insert({"Alice", "Math"});
    student_courses.insert({"Bob", "Physics"});
    student_courses.insert({"Alice", "History"}); // Alice 有多门课
    student_courses.insert({"Charlie", "Chemistry"});

    // 查找 Alice 的所有课程
    auto range = student_courses.equal_range("Alice");
    std::cout << "Alice's courses:" << std::endl;
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "- " << it->second << std::endl;
    }

    // 遍历所有元素
    std::cout << "\nAll student courses:" << std::endl;
    for (const auto& pair : student_courses) {
        std::cout << pair.first << " -> " << pair.second << std::endl;
    }
    return 0;
}

登录后复制

另一种不太直接但有时有效的“映射”方式，特别是在键空间有限且连续、或者数据量相对较小但需要极高查询速度时，可以考虑使用

std::vector

登录后复制

配合
std::pair
登录后复制
或自定义结构体，然后进行排序和二分查找。这本质上是模拟

std::map

登录后复制

的底层机制，但少了红黑树的动态平衡开销。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // For std::sort and std::lower_bound

struct DataEntry {
    int id;
    std::string value;

    bool operator<(const DataEntry& other) const {
        return id < other.id;
    }
};

int main() {
    std::vector<DataEntry> 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 << ": " << it->value << std::endl;
    } else {
        std::cout << "ID " << target_id << " not found." << std::endl;
    }
    return 0;
}

登录后复制

这种方式在数据量固定且不常变动时，可以避免