How does resizing unordered_set impact performance?

Question

As far as I'm aware, resizing an array (like push_back on a vector that requires resizing the array) is O(n) complexity. If this is the case, does this hold for insert in unordered_set? Does resizing the internal array make insert O(n)? Does resizing previous to inserting the elements decrease this time complexity because none of the data has to be copied? Finally, I believe that resizing does not require a rehash. Is this correct? If so, how?

Answer 1

According to cppreference about std::unordered_set<>::insert():

If after the operation the new number of elements is greater than old max_load_factor() * bucket_count() a rehashing takes place.
If rehashing occurs (due to the insertion), all iterators and references are invalidated. Otherwise (no rehashing), iterators and references are not invalidated. If the insertion is successful, pointers and references to the element obtained while it is held in the node handle are invalidated, and pointers and references obtained to that element before it was extracted become valid. (since C++17)

^{emphasis mine}

So yes, a rehash may occur when you insert a new element.

For the complexity, the documentation also answers the question:

Complexity

1-4) Average case: O(1), worst case O(size())
5-6) Average case: O(N), where N is the number of elements to insert. Worst case: O(N*size()+N)
7-8) Average case: O(1), worst case O(size())

^{emphasis mine}

When you have some doubts, always refer to a proper documentation, it often provide the answers we need.