Re:Appending to an std:string character-by-character: how do...
by sltkr on Thursday October 26, 2023 @07:26PM
(#38032949)
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.
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.