用于在稀疏域中设置位的快速容器,并迭代(C++)？

我需要一个只有两个操作的快速容器.从非常稀疏的域插入键(所有32位整数,在给定时间设置大约100),并迭代插入的键.它应该处理很多插入相同条目的插入(例如,500k,但只有100个不同的插入).

目前,我正在使用std :: set(仅插入和迭代接口),这很不错,但仍然不够快.std :: unordered_set的速度是Google Hash Maps的两倍.我想知道为这种情况优化了什么数据结构？

根据输入的分布,您可以在不更改结构的情况下获得一些改进.

如果您倾向于获得大量单个值的运行,那么您可以通过保留您插入的最后一个值的记录来加速插入,并且如果匹配则不要打扰插入.每次输入需要额外的比较,但是在第一次运行之后的运行中保存每个元素的查找.因此,无论您使用何种数据结构,它都可以改善事物,具体取决于重复的频率以及比较与插入的相对成本.

如果你没有运行,但是你倾向于发现值不均匀分布,那么splay树使得访问最常用的元素更便宜.它的工作原理是创建一个故意不平衡的树,其中频繁的元素靠近顶部,就像霍夫曼代码一样.