std::set::insert, how bad can I hint?
<p>I'm doing lots and lots of inserts of <code>std::pair&lt;int, int&gt;</code> into a <code>std::set</code>, and it's taking longer than I'd like. When I wrote the code I figured I'd look at using the hint iterator form of insert later if it turned out to be a bottleneck; well, now it's profiled and it <strong>is</strong> a bottleneck. So I want to use the iterator hint. </p>

<p>However, I'm not always going to know a good position to insert my pairs. I typically insert them in batches (a batch in this case is on the order of 0.01% of the total input size, duplicates included) of increasing set-order, but when a batch is inserted, I do not know where the next one should start. How is the hint used? Does insert do something like a binary search from the suggested position? How bad would it be to use a bad hint, typically?</p>
