C++：当所有条目都保证唯一时，std::map的替代方案

Question

我有一个简单的使用案例：解析头文件。我必须解析许多这些头文件，并且我保证有一个头文件不会重复任何字段。

当我解析这些头文件时，我会将它们组织在一个std :: map 中，

// pseudo code
std::map<std::string,std::string> x;
x[key] = value;

// etc. 

我已经精简了我的代码，但最慢的地方是这些头文件的映射插入。具体来说，当将项目插入到映射中时调用std::_Rb_tree_iterator内部方法。使用gprof进行基准测试表明，当仅在读取这些标题时调用此单个方法（而不在任何可能插入或删除映射项的其他操作期间）时，它大约占据了我的运行时间的50%。

问题在于：假设我可以保证映射中所有条目的唯一性，是否有办法禁用std::_Rb_tree_iterator以实现流畅的映射插入？

我更喜欢运行缓慢的代码而不是使用除std::map之外的其他内容，除非替代品具有等效的api（即迭代器产生std::pair<std::string，std::string>）。

- Chris

---

不，您不能禁用此检查。但是您可以尝试使用不同的数据结构。如果您使用具有 O(1) 插入时间复杂度的 std::unordered_map，会发生什么呢？ - NathanOliver

这段代码是C++中的std::vector<std::pair</*const*/ std::string, std::string>>，表示了一个存储了两个字符串元素的向量容器。其中第一个字符串键是常量(const)，第二个字符串值没有限制。 - Jarod42

Answer 1

std::map的插入速度较慢，因为它试图平衡二叉搜索树。使用std::unordered_map来使用哈希表；虽然它不会保持元素排序，但插入元素将快得多，并且如果您不需要元素排序，则强烈建议使用。

此外，请尝试使用insert调用进行插入；[]会首先创建一个空元素，然后将您自己的元素覆盖它。

- Dorin Lazăr