Why is inserting multiple elements into a std::set simultaneously faster?

Question

I'm reading through:

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

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."

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?

Can anyone shed some light on why this quote is true for me?

Answer 1

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.

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.

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.

Answer 2

There are two reasons:

1) Making a single call for multiple elements instead of N times more calls.

2) The insertion operation checks for each element inserted whether another element exists already in the container with the same value. This can be optimized when insterting multiple elements together.