Menu
Calling clear() on a vector will call the destructors of whatever is stored in the vector, which is a linear time operation. But is this the case when the vector contains primitive types like int or double?
325
@shiplu.mokadd.im, inserting in a vector is constant time if the reserved size is larger than the number of elements, so it does depend on two variables. Clearing, on the other hand, doesn't depend on either the actual size or reserved size of the vector. It's a linear-time operation if you have to call destructors.
Erasing an element in a vector is O(n) as we have to remove the element and still need to shift all successive elements to fill the gap created. If a vector has n elements, then in the worst case we will need to shift n-1 elemets, hence the complexity is O(n).
vector::clear() clear() function is used to remove all the elements of the vector container, thus making it size 0.
Removes all elements from the vector, calling their respective destructors, leaving the container with a size of 0. The vector capacity does not change, and no reallocations happen due to calling this function.
I believe the answer is implementation dependent. It takes at most linear time, but some implementations may choose to optimize this.
Per 'Does clearing a vector affect its capacity?', neither MSVC nor G++ decrease the capacity of their vectors, even when .clear is called. Looking at the G++ headers, it is evident that .clear is constant-time with the default allocator, as long as the elements are scalar (primitive arithmetic types or pointers).
78
Think about this from the POV of how a vector is likely implemented. When you invoke:
delete [] internalPtr;
What happens?
The former must still happen for primitive types, but destructors don't exist for them. So delete[] will execute based entirely on how fast the heap can delete a block of memory
32
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
