c++ - 我可以在 map 不执行任何旋转的情况下预加载 STL map 吗？

Question

我已经对来自数据库的数据进行了排序以初始化 STL map 。只有 5% 的数据稍后会在 map 内部更改。

据我了解，每次插入都会产生轮换开销。是否可以绕过排序数据的开销？例如有没有跳过旋转的选项，还有另一个 STL 算法来创建一个具有排序数据的平衡树？

PS:我知道最多只有 2 个旋转，但想知道我是否可以进一步提高性能。

Answer 1

我假设您只对高效加载初始排序数据感兴趣？

标准map :: map (InputIterator first, InputIterator last) constructor似乎在做正确的事。

“对于迭代器构造函数，如果元素已经根据 comp 排序，则迭代器(复制构造)之间的距离为线性。对于未排序的序列，该距离为线性对数 (N*logN) (排序、复制结构)。”