12

Per a discussion from Is `std::vector<primitive>::clear()` a constant time operation?, it was noted that the C++ standard does not appear to specify the running time of vector::clear.

It specifies the running time of list::clear (linear; §23.3.5.4.5), .clear for both ordered (table 102) and unordered associative containers (table 103) (both linear). However, vector::clear appears to be missing (though other vector members, like .data and .swap appear to have specified complexity).

Is it really unspecified, or did I miss something?

Community
  • 1
  • 1
nneonneo
  • 171,345
  • 36
  • 312
  • 383
  • 1
    Oversight or not, if it's not in there, doesn't that make it unspecified? – Collin Feb 20 '13 at 01:32
  • Yeah, that last statement didn't quite come out right. Thanks for noticing. – nneonneo Feb 20 '13 at 01:36
  • I remember tracing through the code of the standard library implementation supplied with my compiler, and figured out that the operation is, indeed, a no-op. I couldn't find anything in the standard, though, to indicate that the operation *must* be a no-op, though. – Sergey Kalinichenko Feb 20 '13 at 01:41
  • 2
    Well, `vector::clear` is no-op for my G++ (which I checked as part of answering the linked question), but obviously `vector::clear` cannot be a no-op since it must call destructors. Also, if you have a custom allocator then I think it cannot be a no-op either, though I'm not sure if that's mandated by the spec. – nneonneo Feb 20 '13 at 01:42
  • 2
    @dasblinkenlight: clear() is *not* a no-op... at the very least it needs to ensure size is 0 (typically by setting a pointer to the last-used element (corresponding to `end()`), even for POD data types. For non-POD and size > 0, it needs to invoke in-place destructors on all the in-use elements: which will be linear complexity with their number. This complexity is mentioned at http://www.cplusplus.com/reference/vector/vector/clear/ - but I guess that's a common-sense deduction as I can't find anything in the Standard either. – Tony Delroy Feb 20 '13 at 01:52
  • Related SO post: http://stackoverflow.com/a/14094336/777186 – jogojapan Feb 20 '13 at 02:16
  • @nneonneo I knew I researched it at some point, and figured out that they did something clever! Here is [a link to that question](http://stackoverflow.com/q/11235975/335858). – Sergey Kalinichenko Feb 20 '13 at 02:53

1 Answers1

7

Is it really unspecified, or did I miss something?

Yes. At the moment, it is really unspecified.

There is an open library issue for this, whose text contains a link to a relevant Q&A on StackOverflow. The answer by Jonathan Wakely to that question clarifies what has been going on.

According to the linked proposal, the complexity requirement of clear() should be made linear for all sequence containers. However, one must keep in mind that complexity requirements are just upper bounds. Per Paragraph 17.5.1.4/7 of the C++11 Standard:

Complexity requirements specified in the library clauses are upper bounds, and implementations that provide better complexity guarantees satisfy the requirements.

This allows for possible optimizations, but does not mandate them.

Even when the linked proposal will be accepted, we will not be allowed to assume that clear() has O(1) complexity for sequence containers of non-class elements, even though this seems to be a natural and common optimization strategy (and the answer by dasblinkenlight to this question on SO confirms it).

Implementations will be allowed to adopt this strategy (per 17.5.1.4/7), but they won't be required to do so, because nowhere in the Standard such a constraint is (nor is it proposed to be) specified.

Community
  • 1
  • 1
Andy Prowl
  • 124,023
  • 23
  • 387
  • 451