Menu
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?
749
The time complexity to find an element in std::vector by linear search is O(N). It is O(log N) for std::map and O(1) for std::unordered_map . However, the complexity notation ignores constant factors. Different containers have various traversal overheads to find an element.
clear is constant-time with the default allocator, as long as the elements are scalar (primitive arithmetic types or pointers).
vector::clear() clear() function is used to remove all the elements of the vector container, thus making it size 0.
There isn't really a need to call clear() unless you want to dump the contents and reuse the vector. However if you by any chance are using something like a vector then the destructor of the objects being pointed to will not be called as the vector destructor doesn't follow the indirections represented by the pointers.
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.
178
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
