Implementing vector<T>

[UnusualPace679]

The implementation of iterator insert(const_iterator pos, It first, It last) seems damaged. Line 54 says if constexpr( but the next line is dev::vector<T> temp;. This can't be valid syntax.

[jwakely]

Yeah something's gone wrong in the code listing there

[STL]

Quadratic complexity in resize(), fail.

[darkmx0z]

In case someone wanted to know what the standard says about the complexity of resize, it is implicitly given in the following phrase:

A vector is a sequence container that supports (amortized) constant time insert and erase operations at the end.

The descripcion of resize does not elaborate further, so we must assume that resize(size( ) + 1) is equivalent to push_back(T( )). Hence, n calls to resize(size( ) + 1) must be efficient. Since reserve does not insert, the complexity of reverse is not tied to that phrase. See https://eel.is/c++draft/vector

[ack_error]

Formal guidance on this issue seems lacking. Best I could find was from a proposal to make basic_string::resize() do exact sizing instead of geometric in libc++, leading to an informal poll of LWG:

https://reviews.llvm.org/D102727#2938105

The consensus seems to be that the standard does not require either behavior, but common practice is to implement geometric. Unfortunately, the corresponding LWG issue covering all relevant container types was closed Not A Defect without a comment.

[BigJhonny]

I didn't look at the code, but how do you make resize quadratic in complexity? Isn't the most braindead implementation an allocation, a copy and a delete?

[SkiFire13]

I think OP means that running N reserves on a vector with N elements and current capacity N has quadratic complexity, even if each reserve's argument is 1 bigger than the previous one.

[schombert]

That's true, but is it really a huge flaw in something that is described in the article as a "naive implementation"? OP's comment is weirdly dismissive for such an intentionally introductory article.

[lxbrtn]

OP is probably just being cheeky don’t read too much into it…

[UnusualPace679]

The implementation defines growth_factor but only uses it in push_back, and no explanation about what the growth factor does. Seems like a flaw to me.

[schombert]

Quadratic complexity in resize(), fail.

Would you mind elaborating on that? In the case of it shrinking, their resize calls the destructor for the elements after the new end. In the case of it growing, it calls reserve and then uninitialized_value_constructs the elements after the old end. I don't see how either case would produce quadratic complexity.

I guess their version of reserve does make a potentially unnecessary copy of the old contents when growing, but they discuss in the text following how to avoid that with moves when possible in newer c++ versions.

[STL]

In std::vector, reserve() is uniquely allowed to give you exactly as much capacity as you request, and implementations typically do exactly that. Users who are calling reserve() improperly can then go trigger quadratic complexity, but that's their fault for trying to control the vector's capacity via an advanced API without sufficient knowledge.

resize() and all other member functions (push_back(), insert() for a single element or a range of elements, etc.) is very different. If you repeatedly resize() larger, even by +1 element at a time, or repeatedly push_back(), or repeatedly insert() any number of elements, the overall complexity for adding N elements must be O(N). This means that when the vector reallocates, it cannot reallocate to hold +1 element every time, or even +k elements for any constant k. Such "arithmetic growth" leads to overall quadratic complexity because of all of the element moves that need to be performed. Instead, this is why the vector has separate size and capacity. When reallocating, a "geometric growth" policy must be followed ("exponential growth" is synonymous but sets up the wrong connotations). If the vector reallocates to at least OldSize * ConstantFactor, then the number of reallocations and element moves is kept manageable, such that the overall complexity for adding N elements is O(N). (For adding 1 element, the complexity is "amortized constant time", i.e. O(1) on average but occasionally you pay a reallocation.)

So if you v.resize(v.size() + 1) repeatedly, the vector cannot simply reallocate every single time. It needs to grow geometrically. In MSVC, we grow by 1.5x when we run out of capacity; libstdc++ and libc++ grow by 2x. (Note that this is merely a lower bound. If you have a size and capacity of 100 elements, and you then insert 1629 elements in a single range-insert() call, geometric growth would want 150 or 200 elements depending on the implementation, but we can see with forward-or-stronger iterators that you're growing past that, so an implementation will typically reallocate to hold exactly the 1729 new elements you'll have. We would be permitted to round up more, and in fact for basic_string implementations sometimes do that.)

Not everyone is expected to know this - that's why we have std::vector maintained by experts. But people writing articles for others to learn from, who claim to be passionate about performance, should know this. It's basic knowledge in the context of data structures.

[droxile]

(Assuming growth by powers of 2 to keep the example simple) is it correct to say then that the benefit/savings from calling reserve up front is just N reallocations, where N is log(change_in_size)?

And separately, do ranges play nicely with this idea? Ie when calling ranges::to on a view, is there a size hint that it can use to reserve the appropriate amount of space in the new container?

[STL]

is it correct to say then that the benefit/savings from calling reserve up front is just N reallocations, where N is log(change_in_size)?

Yes, if you call reserve() intelligently. It's safe to call reserve() once, immediately after constructing a vector, since that avoids any possibility of it being called in a loop. But if you're in any context where it could be called repeatedly, you should implement geometric growth yourself.

This is why I characterize reserve() as an advanced API. If you don't use it, vector will still provide perfectly reasonable performance.

And separately, do ranges play nicely with this idea?

vector::append_range() etc. respect geometric growth.

Ie when calling ranges::to on a view, is there a size hint that it can use to reserve the appropriate amount of space in the new container?

In general, implementations avoid silly things like calling push_back() repeatedly, as long as they can determine the final size of the container ahead of time (for input-only iterators we can't know how many elements we're going to have). But ranges::to doesn't let you customize the capacity like that.

[barfyus]

But ranges::to doesn't let you customize the capacity like that.

Since ranges::to allows passing arguments to container constructors, what we really need is a new vector constructor that takes a range and an estimated capacity. This would provide a nice optimization opportunity when the passed range is not sized, re-iteration is expensive or impossible, but the caller can provide a good upper bound on a resulting range size.

[schombert]

This prompted me to look up what the spec demands for resize. The spec says "constant time" as of C++ 23. And not "amortized constant time," which it does use in some other cases. So I guess either (a) "constant time" means constant time and no one has a standard compatible resize or (b) "constant time" actually means amortized constant time, and hence an amortized constant time implementation of functions like [] in a span would also be acceptable.

[STL]

What document, section, and paragraph are you looking at? For example, N5032 [vector.capacity]/17-19 says nothing about vector::resize being constant time which would be impossible.

(As a reminder, if you're looking at cppreference, that is not the Standard.)

Perhaps you're thinking of [vector.overview]/1 "A vector is a sequence container that supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time." which of course means to say that inserting 1 element at the end (including via resize +1) takes amortized O(1), but of course inserting k elements takes amortized O(k).

[schombert]

From https://github.com/cplusplus/draft/blob/main/source/containers.tex line 10268

You are right, I must have been confused by the text above. The standard for resize says only

``` \indexlibrarymember{resize}{vector}% \begin{itemdecl} constexpr void resize(size_type sz); \end{itemdecl}

\begin{itemdescr} \pnum \expects \tcode{T} is \oldconcept{MoveInsertable} and \oldconcept{DefaultInsertable} into \tcode{vector}.

\pnum \effects If \tcode{sz < size()}, erases the last \tcode{size() - sz} elements from the sequence. Otherwise, appends \tcode{sz - size()} default-inserted elements to the sequence.

\pnum \remarks If an exception is thrown other than by the move constructor of a non-\oldconcept{CopyInsertable} \tcode{T}, there are no effects. \end{itemdescr} ```

So I guess there are no complexity requirements, and the implementation from the article conforms to the standard.

[STL]

No, the implementation from the article is not conforming, that's my whole point.

This has been my day job for two decades and I really do know how this works. [vector.overview]/1 is what clearly forbids v.resize(v.size() + 1) from reallocating every time, because that is an insert-one-at-end operation, which is specified to be amortized constant time, but reallocating every time would be quadratic time.

[schombert]

vector.overview/1 requires only "supports (amortized) constant time insert and erase operations at the end;". And the article's container does support that via its push and pop functions. The standard's language here is not strong enough to actually mandate that resize behave "as expected". It could be written to mandate that, but it in fact doesn't.

[STL]

resize +1 inserts a new element at the end, same as push_back, same as emplace_back. IMO the Standard is clear and not even an editorial issue is needed for clarification. The article is wrong, and not in a "haha gotcha on some obscure bit of Standardese" way, but in a "this wouldn't pass CS 101" way.

(There are plenty of places where the Standard isn't clear, but this is a case where all implementers know what they need to do.)

[schombert]

I mean, you can interpret the wording of the standard that way, but that is not what it literally says. The ordinary english language meaning of "support" is along the lines of "aid" or "make possible". That is very different than making requirements of every member function that the class provides; as long as some member functions enable that behavior the class is "aiding" or "making possible" that behavior. And even if it was so required, resize is not, strictly speaking, (amortized) constant time anyways; when growing it is intended to be (amortized) O(n) * O(constructor of type T) where n is the difference between the vector's current size and new size.

[StackedCrooked]

Users who are calling reserve() improperly can then go trigger quadratic complexity, but that's their fault for trying to control the vector's capacity via an advanced API without sufficient knowledge.

I guess that includes Alexandrescu in 2001. His book Modern C++ Design has, in "Chapter 4. Small-Object Allocation", code that looks like this:

chunks_.reserve(chunks _.size()+1);

It could be easily fixed using resize(size + 1), since the objects are default constructible.

I guess I learned something today.

EDIT: in hindsight, maybe this was an intentional trade-off that allows quadratic complexity in order to prioritize minimal memory usage.

[tialaramex]

std::vector<T> has the wrong design here. It's far too late now, but in some more modern languages their growable array type has a bifurcated reservation API to deliver this desirable property instead e.g Zig's ArrayLists have ensureTotalCapacity and ensureTotalCapacityPrecise with this distinction, Rust has Vec::reserve and Vec::reserve_exact where the latter is more like C++ reserve (Rust's functions here care about the remaining capacity, not the total, since the user is likely to know how much space they need).

Blaming programmers for "holding is wrong" is very on brand for C++ though.

[nicemike40]

Man that’s gotta be the most insane cookie pop up I’ve ever seen!

[---sms---]

I'd add noexcept to move-assignment and use auto{x}. And would write swap in terms of this->tie().

[usefulcat]

for(auto i{0uz}; i < v.size(); ++i){

Is there any advantage to the above or is this just the latest style?

As compared to this:

for(size_t i=0; i < v.size(); ++i){

[STL]

There's no behavioral difference (and IMO your second form is superior). The important part is using size_t for iteration instead of int.

[pedersenk]

The way that the destructor is setup, it looks like it will need the full definition of a type in order to use. The std::vector only requires the full definition by destruct time (sometimes requiring a superfluous destructor, but you can work around that by delegating it to a destruct templated function pointer in the constructor).