c++ - std::map 插入顺序和性能

Question

如果我想加载相对较大的对文件并使用std::map来存储数据。当我逐一加载每个条目并将其插入到映射中时，插入操作将花费 O(log N)。我想通过对文件中的条目进行排序来改进这一点，以确保当我从文件中逐一加载每个条目时，插入将精确地进行单次迭代。这可以通过在文件中提供正确的条目组织来实现。问题是顺序是什么？假设与 map 排序相同的顺序是正确的吗？我使用标准的字符串比较方法，就像 std::map 默认情况下那样。

Answer 1

是的，如果您有一系列按 value_comp() 顺序排列的对，则可以使用 the 4th overload

template< class InputIt >
map(InputIt first, InputIt last);

如果序列按 value_comp() 顺序排序，则需要花费线性时间。