11

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?

braX
  • 11,506
  • 5
  • 20
  • 33
user2020792
  • 239
  • 1
  • 11
  • 2
    possible duplicate of [What is the complexity of std::vector::clear() when T is a primitive type?](http://stackoverflow.com/questions/11235975/what-is-the-complexity-of-stdvectortclear-when-t-is-a-primitive-type) – nneonneo Feb 20 '13 at 02:14
  • possible duplicate of [std::vector::clear, constant time?](http://stackoverflow.com/questions/14094302/stdvectorintclear-constant-time) – jogojapan Feb 20 '13 at 02:15
  • What's the big-O of `N` repetitions of `O(0)`? – Caleth Jul 02 '20 at 09:47

4 Answers4

5

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

Community
  • 1
  • 1
nneonneo
  • 171,345
  • 36
  • 312
  • 383
  • That seems consistent with the fact I cannot find anything about `vector::clear()` (or sequence containers' clear() for that matter) in the standard. Of course, it could be down to me not searching properly... – juanchopanza Feb 20 '13 at 01:09
  • @juanchopanza: I have looked in the spec, and it really does seem to [be missing](http://stackoverflow.com/questions/14970747/is-the-complexity-of-vectorclear-unspecified). Note, though, that `erase(begin(), end())` is specified to take time equal to the amount of time needed to call every destructor. – nneonneo Feb 20 '13 at 01:27
2

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

Doug T.
  • 64,223
  • 27
  • 138
  • 202
0

In this link:

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

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

Barney
  • 2,355
  • 3
  • 22
  • 37
0

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

El Hocko
  • 2,581
  • 1
  • 13
  • 22