C / C++ / 系统课时
用 unordered_map 建立编号索引
用 unordered_map 建立编号索引
当商品保存在 vector 中时,按编号查找若每次都从头遍历,商品越多成本越高。本节为商品列表额外建立 unordered_map 索引,把商品编号映射到其位置,使查询可以直接定位目标商品,同时理解索引与原始数据之间必须保持一致。
学习目标
- 使用
unordered_map建立商品编号到位置的映射 - 通过哈希索引完成无需遍历整个列表的编号查询
- 识别商品列表变化后索引失效的问题
为什么需要编号索引
假设商品主体仍保存在 vector<Product> 中。没有额外索引时,要查找编号为 1003 的商品,只能依次比较每个元素的 id。一次查询的最坏时间复杂度是 ;如果大量请求都按编号查询,相同的线性扫描会不断重复。
可以保留 vector 负责连续存储,再增加 unordered_map<int, std::size_t>。哈希表的键是商品编号,值是该商品在 vector 中的下标。查询编号时先访问哈希表,得到下标后再访问商品对象。平均情况下,哈希表查找接近 。
建立并使用索引
下面的完整程序先创建商品列表,再遍历一次建立编号索引,最后按编号查询商品。emplace 的返回结果还能帮助发现重复编号,避免后加入的商品静默覆盖已有索引。
#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;
}预期输出
1003 Monitor 1599find 不会在编号不存在时创建新元素,因此比使用 idIndex[targetId] 更适合查询。后者的 operator[] 在键不存在时会插入一个默认值,可能把一次纯查询意外变成修改操作。
索引必须和列表同步
编号索引并不是商品数据的副本,它依赖 vector 中当前位置的含义。如果删除了中间商品,后续元素会向前移动,旧下标就可能指向错误商品。例如删除下标 0 后,原本记录为下标 2 的商品可能已经移动到下标 1。
因此,只要执行会改变元素位置的操作,就必须同步维护或重新构建索引。对于规模不大的内存练习项目,修改商品列表后重新扫描并构建索引通常最简单,也最不容易产生隐藏错误。
什么时候适合 unordered_map
当系统频繁执行“已知唯一编号,查找一个商品”时,unordered_map 很合适。它不负责按照编号排序,遍历顺序也没有稳定保证;如果需求变成按编号范围查询或按编号有序输出,应考虑 map、排序后的 vector 等其他结构。
在这个内存商品系统中,vector 负责保存完整商品,unordered_map 负责从编号快速定位位置。两者承担不同职责,关键不是把数据重复保存两份,而是在修改商品集合时始终维护二者的一致性。