Std :: set :: insert, how bad can I hint?

Question

I make many, many attachments to std::pair<int, int> in std::set , and it takes longer than I would like. When I wrote the code, I decided that I would see how to use the form of the insert hint iterator later if it turned out to be a bottleneck; well, now he's profiled, and is the bottleneck. So I want to use an iterator hint.

However, I will not always know a good position to insert my pairs. Usually I insert them into lots (the lot in this case is about 0.01% of the total input size, including duplicates) of the increase in the given order, but when the lot is inserted, I don’t know where the next Start is. How is this hint used? Does something like binary search insert from a suggested position? How bad would it be to use a bad hint, usually?

Answer 1

I suggest just reading what the compiler reads: the header file for #include <set> . On my system (GNU libstdc ++ 4.5.1) I can read the following explanatory text:

  /** * @brief Attempts to insert an element into the %set. * @param position An iterator that serves as a hint as to where the * element should be inserted. * @param x Element to be inserted. * @return An iterator that points to the element with key of @ax (may * or may not be the element passed in). * * This function is not concerned about whether the insertion took place, * and thus does not return a boolean like the single-argument insert() * does. Note that the first parameter is only a hint and can * potentially improve the performance of the insertion process. A bad * hint would cause no gains in efficiency. * * For more on @a hinting, see: * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html * * Insertion requires logarithmic time (if the hint is not taken). */ iterator insert(iterator __position, const value_type& __x) { return _M_t._M_insert_unique_(__position, __x); } 

Takeaway Food:

• Bad hint will not increase efficiency
• Box O(log n)
• You can learn more about inserts in the GNU libstdC ++ manual .

Answer 2

If you check the bits/stl_tree.h (in GNU libstdc ++), you will find that the _M_insert_unique member _M_insert_unique with the prompt argument looks like one node to the left of the prompt, then one node to the right, and then by default invokes the regular insertion procedure .

It calls key_compare at least once (if the set is not empty) and no more than three times. Moving from one node to the next or previous refers to the next pointer, because (IIRC) std::set and friends of threaded trees .

So, how bad a bad hint depends on the comparison procedure and on whether your package distribution nodes std::set are closed in memory.

Answer 3

The hint is good if it's the right hint - the position you need to use to insert. It works if you insert objects sequentially, for example.

If the prompt is incorrect, it does not work, and you get an unintended insert.

Answer 4

If you create a set immediately before using it, you can use the vector and sort it before using it. You can use binary_search , lower_bound , upper_bound and equal_range for a sorted vector for quick searches. You can also use merge or inplace_merge to combine sorted vectors and set_difference , set_intersection and set_union to perform other general set operations.