CODEWITHSUNDEEP
c++vectorstl
user2020792
user2020792

Reputation: 239

Is `std::vector<primitive>::clear()` a constant time operation?

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?

Upvotes: 11

Views: 888

Answers (4)

El Hocko
El Hocko

Reputation: 2606

Well.. it says that clear() is linear, but we also know that it calls the destructor of every item...

http://www.cplusplus.com/reference/vector/vector/clear/

What if the destructor call ist not linear?

However, on primitives the destructor-call is linear (or constant, this is not important unless it is not more than linear)

so yes, on primitives is clear() always a linear operation

Upvotes: 0

nneonneo
nneonneo

Reputation: 179422

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).

Upvotes: 5

Barney
Barney

Reputation: 2373

In this link:

http://www.cplusplus.com/reference/vector/vector/clear/

It says complexity of clear() is linear in size (destructions).

Upvotes: 0

Doug T.
Doug T.

Reputation: 65619

Think about this from the POV of how a vector is likely implemented. When you invoke:

 delete [] internalPtr;

What happens?

  • The heap must reclaim a contiguous block of space
  • destructors must fire or each object in internalPtr

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

Upvotes: 2

Related Questions