> Interestingly, the C++ standard doesn't specify a cost for this, or an implementation.

Table 76 (page 797-798 of the C++20 draft [0]; page numbers read 789-790) specifies the sequence operations on containers that shall take amortized constant time. Among these includes push_back() for basic_string.

[0] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n48...

This was also the case in the C++11 draft, and quite possibly before then as well. (I don't have a copy of the C++03 spec handy)

Woops, thanks. Not sure how I missed that.

Yeah. It was only on page 797! How could you miss that?

;-)

The C++ standard requires:

  1. Both std::vector<T> and std::basic_string<T> support push_back(T) with amortized constant performance.
  2. Additionally, std::basic_string<T> has an operator+=(T) that behaves semantically identical to push_back(T), but does not have a complexity requirement imposed by the standard.

Logically that leads to every reasonable standard library implementation to simply dispatch std::basic_string<T>::operator+=(T) to std::basic_string<T>::push_back(T) (or vice versa, of course) and have both operations run in amortized constant time.

You're technically correct that the standard theoretically allows push_back(T) and operator+=(T) to have different time complexities, so you could make operator+=(T) run in linear time if you're trolling (but in that case, why stop at O(N) and not make it O(2^N) or something?), but since push_back(T) and +=(T) need to be equivalent and the former needs to run in O(1) amortized time, there is no reason to make the latter perform worse than the former.

Might an implementor use a specialised implementation for operator+= that performs better for practical-sized strings while not being O(1)?

Are there reasonable string implementations lacking 0(1) amortized append runtime?

No, because appending with push_back() which strings must also support is required to have O(1) amortized time.

See my comment here for details: https://news.ycombinator.com/item?id=38032949

Depends what you mean by reasonable I suppose. If you just implement it naively, either by growing by 1 or a constant amount each time, it'll be O(n) amortized.

I'd call those potentially reasonable, in that it works and it doesn't break the standard. I probably wouldn't be mad if a student did that impl, but I'd mention it.

I would be surprised if a well-supported, non-toy implementation without strange constraints (eg not for embedded and not trying to optimize solely for size or simplicity or something) did something other than amortized O(1).

No, but there was an unreasonable one. Microsoft Foundation Classes, which preceded the STL. Originally, Their CString class extended the capacity in such a way that appending one character at a time had quadratic cost.

It was just using the naive approach (grow by the exact size), the same idea as Google is now proposing. https://news.ycombinator.com/item?id=38033206