文件管理器应直接填充 std::unordered_map,还是先用 std::vector?
先将数据存入 std::vector,再转存到 std::unordered_map,通常不能仅凭这一步加快整个构建过程。既然最终需要按文件名查找,可以直接填充 std::unordered_map;如果能合理估计元素数量,就调用 reserve,不再需要原对象时则移动 FileInfo。
如果 std::vector 还用于文件列表排序、按行访问等操作,保留它就有实际用途。哪种方案更快,需要结合 FileInfo 的结构和目录读取过程测量,不能只比较两种容器的插入速度。
为什么先存入 vector 不一定更快?
std::vector::push_back 的追加成本通常较低,但第二种方案最终仍需将每个文件插入 Hash Map,包括计算文件名哈希、处理桶内查找和构造元素。
与直接插入相比,中间的 std::vector 增加了自身的内存分配、元素构造和一次遍历。std::move 可以减少部分复制成本,但目标容器仍需要计算哈希、管理桶和存储元素。
第二种方案的一个便利是,收集完数据后可以准确知道元素数量,从而执行:
contents.reserve(fileInfos.size());
这有助于减少插入期间因容量不足引发的 rehash。不过,如果直接插入时也能提前预留合理容量,这项优势就不是第二种方案独有的。
原示例的性能比较还混入了复制与移动的差异
直接插入的代码是:
contents.emplace(fileInfo.filename, fileInfo);
这里的 fileInfo 是左值,插入成功时会用它复制构造映射中的 FileInfo。第二种方案则使用:
map.try_emplace(fileInfo.filename, std::move(fileInfo));
它在插入成功时尝试移动构造 FileInfo。因此,即使测得第二种写法更快,也不能直接归因于先使用了 std::vector。
另外,原来的:
vector.push_back(fileInfo);
本身也会复制 fileInfo。比较两种存储流程前,应先统一复制和移动的使用方式。
直接填充 unordered_map 的写法
下面是使用 C++17 try_emplace 的示意代码。假设 FileInfo 已定义,fileInfo 是当前读取到的文件信息:
std::unordered_map<std::wstring, FileInfo> contents;
// 如果已有合理的数量估计,可以在插入前执行:
// contents.reserve(expectedCount);
// 在目录遍历过程中,对每个已填充的 fileInfo 执行:
std::wstring key = fileInfo.filename;
contents.try_emplace(std::move(key), std::move(fileInfo));
这里先取得独立的键,再将键和 FileInfo 分别移动到容器中,所有权比较清楚。如果 FileInfo 内部也保留 filename,最终仍会同时保存键和对象内部的文件名;移动整个对象不会消除这份重复存储。
需要注意:
std::move本身只是类型转换。实际能否避免深复制,取决于FileInfo及其成员的移动构造行为。- 插入成功后,不应继续依赖原
fileInfo中尚未重新赋值的字段内容。 - 如果键已经存在,
try_emplace不会替换已有值,也不会为了构造映射值而移动传入的fileInfo。刷新已有记录时,需要另行定义更新逻辑。 reserve主要预留桶容量,不等于提前完成所有元素存储所需的分配。
目录数量未知时,不必仅为取得精确数量而额外遍历一次目录。可以使用合理估计,也可以先不预留,等测量确认 rehash 是实际开销后再调整。
如果列表需要排序,可以让 vector 保存数据、map 保存索引
文件管理器通常还需要按名称、大小或时间排序。std::unordered_map 不提供这种显示顺序,这时可以考虑:
std::vector<FileInfo> fileInfos;
std::unordered_map<std::wstring, std::size_t> indexByName;
fileInfos 保存文件信息和显示顺序,indexByName 保存文件名到下标的映射。数据收集、排序完成后,可以构建索引:
indexByName.reserve(fileInfos.size());
for (std::size_t i = 0; i < fileInfos.size(); ++i) {
indexByName.try_emplace(fileInfos[i].filename, i);
}
选中文件后,通过索引访问对应数据:
auto it = indexByName.find(selectedFilename);
if (it != indexByName.end()) {
const FileInfo& info = fileInfos[it->second];
// 使用 info 中的文件大小等字段。
}
这种结构既能连续存储数据,也能按文件名查找。重新排序、删除或插入导致元素位置变化后,必须更新相应索引。单纯的 vector 重新分配不会改变已有元素的下标,但会使指向元素的指针和引用失效。
如果 UI 可以直接保存有效的行标识或下标,选择操作也可能不需要再次按文件名查找。这取决于 UI 与数据模型的关联方式。
怎样判断是否值得优化?
对于通常有 100~1000 个、最多约 10,000 个条目的目录,不能仅凭数量断言容器构建就是瓶颈。目录枚举、元数据读取、FileInfo 构造、排序和 UI 更新都可能影响首次显示时间。
建议比较以下三种方案,并保持它们最终提供相同功能:
- 直接填充
std::unordered_map,不预留容量。 - 直接填充
std::unordered_map,提前预留合理容量。 - 先填充
std::vector,再预留容量并转存到std::unordered_map。
分别记录目录读取、容器构建和列表显示的耗时。比较时统一复制与移动策略;如果测试会移动输入对象,每轮应重新准备等价输入,避免后续轮次使用已经被移动过的数据。
std::unordered_map 按元素数量计的查找平均复杂度为 O(1),最坏情况下为 O(n),字符串哈希本身还需要处理文件名字符。它适合当前的按文件名查找需求,但是否能明显改善列表显示时间,仍取决于实际耗时分布。
建议先实现直接填充并按需 reserve 的版本。只有列表本身需要 std::vector,或测量证明分阶段处理确实有收益时,再增加中间容器。
备注:内容仅供参考。
