PAYATHON 2026

文件管理器应直接填充 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 更新都可能影响首次显示时间。

建议比较以下三种方案,并保持它们最终提供相同功能:

  1. 直接填充 std::unordered_map,不预留容量。
  2. 直接填充 std::unordered_map,提前预留合理容量。
  3. 先填充 std::vector,再预留容量并转存到 std::unordered_map。

分别记录目录读取、容器构建和列表显示的耗时。比较时统一复制与移动策略;如果测试会移动输入对象,每轮应重新准备等价输入,避免后续轮次使用已经被移动过的数据。

std::unordered_map 按元素数量计的查找平均复杂度为 O(1),最坏情况下为 O(n),字符串哈希本身还需要处理文件名字符。它适合当前的按文件名查找需求,但是否能明显改善列表显示时间,仍取决于实际耗时分布。

建议先实现直接填充并按需 reserve 的版本。只有列表本身需要 std::vector,或测量证明分阶段处理确实有收益时,再增加中间容器。

备注:内容仅供参考。