Why does cppreference.com list an amortized time complexity for vectors' push_back() but average and worst time complexities for the unordered containers' insert()? Is there an implementation that doesn't need to rehash?
1 Answers
Amortised complexity doesn't make sense for unordered associative containers.
For vectors, the complexity of a particular insertion does not depend on the value of the element being inserted, but only on the history of previous insertions and deletions. Thus it is possible to calculate amortised complexity: insert N elements, take the overall complexity and divide by N. Some of these insertions are very fast and some require reallocation which is O(size()). The amortised complexity is the average of them all, and does not depend on the distribution of inserted values.
For unordered containers, the complexity may depend on the value of the element being inserted and on the values of elements already present in the container. As an edge case, consider a n unordered set where hashes of all elements are equal, and another one with the same hash is being added. The operation is O(size()) and will always remain O(size()), however many elements you add. OTOH if the element being inserted falls into an empty bucket, the complexity is O(1). You cannot take the average of these cases without knowing the distribution of inserted values.
Related