> 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)

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.

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