具有可预测键的关联容器：使用哪一个？

Question

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

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

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

换句话说：如果我提前知道项目的键是什么，甚至知道插入时键的显示顺序，我是否可以提高性能？（不过我不知道项目总数。）

Answer 1

如果您确实使用了stl::map- 即使只是为了进行分析以与散列进行比较 - 您可以利用您的知识“使用升序键值插入项目”，通过stl::map向插入提供提示来大大提高插入操作的效率称呼：

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

...其中position_hint，例如，将是插入的上一个项目的迭代器。