Complexity is linear in the size of the container? If size() is 10 and capacity() is 20 and I say resize(12,1234) then it is linear to the size() difference between the new and the old size.
Do we know about the allocation strategy when the requested size() is greater than capacity()?
And also. If the requested size is smaller than the previous size() then the complexity is the difference between the new and the old sizes (destructors called). If T is primitive type then the complexity is 1, I assume.
- For the case where resize shrinks, the standard sends off to erase() in C++11 and to pop_back() in C++14. Erase has complexity clause saying "The destructor of T is called the number of times equal to the number of the elements erased". For the case where resize grows, the standard describes the effect as "appending" which can only refer to the insert/push-back paragraph which has the requirement "The complexity is linear in the number of elements inserted". So yes, for a trivially-destructible T and optimizing compiler, the shrinking erase should take constant time, but it isn't a requirement. It would probably be more precise to say 'linear in the number of elements appended or erased' --Cubbi 06:56, 2 August 2013 (PDT)
- "linear in the number of elements appended or erased" sounds about right, at least for the case where capacity doesn't need to change. The complexity we list for resize is for the general case where a reallocation might happen, which requires time linear in the size of the vector. I don't think there is anything explicit about what allocation strategy is used when capacity increases, but the amortized O(1) requirements for push_back imply some kind of exponential-doubling strategy. --Nate 07:39, 2 August 2013 (PDT)
- Thread starter again. We can say that shrinking is linear in the number of elements deleted. There is no circumstance that I know of and can change that. It would be useful for the reader to articulate it. Also a note about growing inside the bounds of capacity() would be useful. I recommend to add them if it is possible to construct good references for them.
- After poking around a bit, I've noticed that there is a lot of contradictory advice about how resize works on the internet. I'd feel better about making more detailed claims if we could come up with specific parts of the standard that e.g. Cubbi mentioned above; specifically (a) resize shrinking, (b) resize growing, and (c) where "appending" is mentioned in reference to insert/push_back. --Nate 17:22, 5 August 2013 (PDT)