insert in unordered_set a new element: should the hint be end()?

Question

If I am sure that a certain value is not yet into an unordered_set, and I am going to insert such value, is it correct to pass this set end() iterator as a hint?

EDIT:

Code:

#include <unordered_set>
using namespace std;

unordered_set<int> someset;

int main(){
    auto it=someset.find(0);
    if(it==someset.end()) someset.insert(it, 0);    //correct? possible performance boost if the set is actually populated?
}

Answer 1

I think, you can simply call insert function and the returned value will tell you whether value is inserted, or it is already present in the set.

auto p = someset.insert(value);
if (!p.second) 
{
   std::cout << "value was already present in the set" << std::endl;
}

Actually p is of type std::pair<iterator,bool>, so p.second tells you whether value is inserted, or it is already present in the set, and p.first is the iterator which tells you the position of the value.

Remember that this is faster than your approach, because my solution reduces the overall work.

Answer 2

I assume you are referring to iterator insert ( const_iterator hint, value_type&& val ); which is a member of C++11's unordered_set. As described here the hint is used for performance optimization when inserting new elements. The insertion / position of the new element is based on hashes. So if you know how the hash is generated for your value_type you can pre-generate it and give a hint to the container.

However, the compiler may decide not to use it. So my hypothesis is: using end() may be used but it may not have any effect.

Answer 3

I believe the hint is of no use to unordered_set, the same way it is of no use to unordered_map. These methods exist to maintain these containers' interface compatible with their ordered versions (set and map, respectively).

Read more here: std::unordered_map insert with hint