Joh*_*0te 10 c++ stl data-structures
我正在阅读:
"C++标准库:Nicolai M. Josuttis的教程和参考"
我在关于集合和多重集的部分.我遇到了关于插入和删除元素的一行:
"如果在使用多个元素时,对所有元素使用单个调用而不是多个调用,则插入和删除的速度会更快."
我远不是数据结构大师,但我知道它们是用红黑树实现的.我不明白的是,STL实现者如何编写算法以更快的方式一次插入多个元素？
任何人都可以解释为什么这句话对我来说是真的吗？
我的第一个想法是,只有在插入/擦除整个范围后才可以重新平衡树.由于整个操作在实践中都是内联的,这似乎比函数调用的数量更多.
检查我本地计算机上的GCC标头,似乎并非如此 - 无论如何,我不知道减少的重新平衡活动与可能增加的中间插入到不平衡树的搜索时间之间的权衡如何工作出.
也许它被认为是一个QoI问题,但无论如何,使用最具表现力的方法可能是最好的,不仅仅是因为它可以节省你编写for循环并最清楚地显示你的意图,而且因为它让图书馆编写者有更大的优势进行优化.未来,无需了解和更改代码.