C / C++ / 系统课时

用 unordered_map 建立编号索引

用 unordered_map 建立编号索引

当商品保存在 vector 中时,按编号查找若每次都从头遍历,商品越多成本越高。本节为商品列表额外建立 unordered_map 索引,把商品编号映射到其位置,使查询可以直接定位目标商品,同时理解索引与原始数据之间必须保持一致。

学习目标

  • 使用 unordered_map 建立商品编号到位置的映射
  • 通过哈希索引完成无需遍历整个列表的编号查询
  • 识别商品列表变化后索引失效的问题

为什么需要编号索引

假设商品主体仍保存在 vector<Product> 中。没有额外索引时,要查找编号为 1003 的商品,只能依次比较每个元素的 id。一次查询的最坏时间复杂度是 O(n)O(n);如果大量请求都按编号查询,相同的线性扫描会不断重复。

可以保留 vector 负责连续存储,再增加 unordered_map<int, std::size_t>。哈希表的键是商品编号,值是该商品在 vector 中的下标。查询编号时先访问哈希表,得到下标后再访问商品对象。平均情况下,哈希表查找接近 O(1)O(1)。

建立并使用索引

下面的完整程序先创建商品列表,再遍历一次建立编号索引,最后按编号查询商品。emplace 的返回结果还能帮助发现重复编号,避免后加入的商品静默覆盖已有索引。

cpp
#include <cstddef>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

struct Product {
    int id;
    std::string name;
    double price;
};

int main() {
    std::vector<Product> products{
        {1001, "Keyboard", 299.0},
        {1002, "Mouse", 129.0},
        {1003, "Monitor", 1599.0}
    };

    std::unordered_map<int, std::size_t> idIndex;

    // 索引只保存位置,商品数据仍由 vector 统一持有。
    for (std::size_t i = 0; i < products.size(); ++i) {
        auto [it, inserted] = idIndex.emplace(products[i].id, i);
        if (!inserted) {
            std::cerr << "duplicate product id: " << products[i].id << std::endl;
            return 1;
        }
    }

    const int targetId = 1003;
    auto it = idIndex.find(targetId);

    if (it == idIndex.end()) {
        std::cout << "product not found" << std::endl;
        return 0;
    }

    const Product& product = products[it->second];
    std::cout << product.id << " " << product.name << " " << product.price << std::endl;
}

预期输出

text
1003 Monitor 1599

find 不会在编号不存在时创建新元素,因此比使用 idIndex[targetId] 更适合查询。后者的 operator[] 在键不存在时会插入一个默认值,可能把一次纯查询意外变成修改操作。

索引必须和列表同步

编号索引并不是商品数据的副本,它依赖 vector 中当前位置的含义。如果删除了中间商品,后续元素会向前移动,旧下标就可能指向错误商品。例如删除下标 0 后,原本记录为下标 2 的商品可能已经移动到下标 1。

因此,只要执行会改变元素位置的操作,就必须同步维护或重新构建索引。对于规模不大的内存练习项目,修改商品列表后重新扫描并构建索引通常最简单,也最不容易产生隐藏错误。

什么时候适合 unordered_map

当系统频繁执行“已知唯一编号,查找一个商品”时,unordered_map 很合适。它不负责按照编号排序,遍历顺序也没有稳定保证;如果需求变成按编号范围查询或按编号有序输出,应考虑 map、排序后的 vector 等其他结构。

在这个内存商品系统中,vector 负责保存完整商品,unordered_map 负责从编号快速定位位置。两者承担不同职责,关键不是把数据重复保存两份,而是在修改商品集合时始终维护二者的一致性。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用 unordered_map 建立编号索引

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通