c++ - 具有可预测键的关联容器 : which one to use?

Question

一个简单的问题，但答案对我来说并不明显:出于性能原因，从性能的角度来看，我应该在以下场景中最好地使用哪种 map 类型(或非 map 类型？)容器:

• 键是无符号整数，
• 插入很频繁，
• 读取访问更加频繁和随机访问，
• 项目以升序键值插入(第一个插入的项目具有键 0，下一个键为 1，依此类推)，
• 项目是随机删除的(所以迟早键列表会有“漏洞”，因为相应的项目已被删除)。删除几乎与插入一样频繁。

我对使用 std::map 犹豫不决，因为升序键顺序和频繁删除似乎意味着搜索树的不断重新平衡，对我来说这似乎是对性能的浪费。

换句话说:如果我事先知道项的键是什么，甚至键在插入时出现的顺序，我能否获得性能提升？ (虽然我不知道项目的总数。)

Answer 1

如果您确实使用了 STL::map——即使只是为了分析以与哈希进行比较——您也可以利用“项目是使用升序键值插入”的知识来极大地通过提示插入调用来提高 STL::map 插入操作的效率:

iterator insert ( iterator position_hint, const value_type& x );

...例如，position_hint 将是指向上一个插入项的迭代器。