为什么将多个元素同时插入std :: set更快？ [英] Why is inserting multiple elements into a std::set simultaneously faster?

问题描述

我正在阅读：

C ++标准库：Nicolai M的教程和参考。
Josuttis

"The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis"

，而我在有关Sets&多集。我碰到了有关插入和删除元素的一行：

and I'm in the section about Sets & Multisets. I came across a line regarding Inserting and Removing elements:

如果使用多个
元素，则插入和删除的速度更快，则对所有元素使用单个调用，而不是对多个
调用。

"Inserting and removing happens faster if, when working with multiple elements, you use a single call for all elements rather than multiple calls."

我离数据结构很远大师，但我知道它们是用红黑树实现的。我不明白的是，STL实现者将如何编写一种算法，以更快的方式一次插入多个元素？

I'm far from a data structures master, but I'm aware that they're implemented with red-black trees. What I don't understand from that is how would the STL implementers write an algorithm to insert multiple elements at once in a faster manner?

有人可以阐明为什么吗

推荐答案

我的第一个想法是，只有在插入/擦除整个范围之后，它才能重新平衡树。由于实际上整个操作都是内联的，因此看起来似乎比函数调用的次数要多。

My first thought was that it might rebalance the tree only after inserting/erasing the whole range. Since the whole operation is inlined in practice, that seems more likely than the number of function calls.

检查本地计算机上的GCC标头，这似乎并没有确实是这样-无论如何，我不知道如何减少重新平衡活动与可能增加对不平衡树的中间插入物的搜索时间之间的折衷。

Checking the GCC headers on my local machine, this doesn't seem to be the case - and anyway, I don't know how the tradeoff between reduced rebalancing activity, and potentially increased search times for intermediate inserts to an unbalanced tree, would work out.

也许这被认为是QoI问题，但是在任何情况下，使用最具表现力的方法可能是最好的方法，不仅仅是因为这样可以节省您为<$ c $编写 c>循环并最清楚地显示您的意图，但这是因为它使图书馆编写者可以自由地在将来更积极地进行优化，而无需了解和更改代码。

Maybe it's considered a QoI issue, but in any case, using the most expressive method is probably best, not just because it saves you writing a for loop and shows your intention most clearly, but because it leaves library writers latitude to optimise more aggressively in the future, without you needing to know and change your code.

这篇关于为什么将多个元素同时插入std :: set更快？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！