1246. vector::resize() missing efficiency guarantee

Section: 23.3.11.3 [vector.capacity] Status: NAD Submitter: David Abrahams Opened: 2009-10-24 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [vector.capacity].

View all other issues in [vector.capacity].

View all issues with NAD status.

Discussion:

If v is a vector, I think repeated calls to v.resize( v.size() + 1 ) should be amortized O(1), but it's not clear that's true from the text of the standard:

void resize(size_type sz);

Effects: If sz < size(), equivalent to erase(begin() + sz, end());. If size() < sz, appends sz - size() default constructed elements to the sequence.

Seems to me if we used push_back instead of appends, we might be giving the guarantee I'd like. Thoughts?

[ 2009-11-10 Howard adds: ]

Moved to Tentatively NAD after 5 positive votes on c++std-lib. Rationale added below.

Proposed resolution:

In 23.3.11.3 [vector.capacity]/10, change

void resize(size_type sz);

Effects: If sz < size(), equivalent to erase(begin() + sz, end());. If size() < sz, appends sz - size() default constructed elements to the sequence equivalent to sz - size() consecutive evaluations of push_back(T()).

Rationale:

The description in terms of push_back led some to believe that one could expect the exact same growth pattern from both resize and push_back (e.g.) which could lead to sub-optimal implementations. Additionally, 23.3.11 [vector], p1 includes a statement that this container "supports (amortized) constant time insert and erase operations at the end;", therefore addressing the concern of this issue.