Talk:cpp/container/vector/resize

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)

Incorrect type requirements for C++11

For vector::resize C++11 standard states: "T shall be MoveInsertable and DefaultInsertable into *this." for overload (1) and "T shall be MoveInsertable into *this and CopyInsertable into *this." for overload (2). Same for deque::resize. For list and forward_list there is no MoveInsertable requirements - only DefaultInsertable is needed in first overload. Wiki structure seems to complex for me to correct this myself though.

Many thanks! I've made the correction. --D41D8CD98F (talk) 05:38, 2 November 2014 (PST)

Hi! The error is still there. Descriptions for vector::resize and deque::resize from the standard: "T shall be MoveInsertable and DefaultInsertable into *this." for overload (1) and "T shall be MoveInsertable into *this and CopyInsertable into *this." for overload (2).

Same for std::deque

Replaced DefaultConstructible with DefaultInsertable (you're right and this is the same for all four containers that share this template). There is no MoveInsertable requirement for overload 2 in C++14 or the current C++17 WP (it would be redundant anyway). Back in C++11, vector::resize was defined in terms of insert/erase and did not formally require CopyInsertable for overload 2 and only required CopyInsertable (not DefaultInsertable or MoveInsertable) for overload 1. DefaultInsertable didn't even exist in C++11. We could mention C++11 in a note, but I find it hard to do meaningfully. --Cubbi (talk) 07:35, 9 December 2014 (PST)

resize()

The documentation says "Vector capacity is never reduced when resizing to smaller size". Shouldn't it be more generally: "Vector capacity is only changed when the new size is greater than the old capacity"?