4 ms·
This is, of course, the same mechanism that allows appending to an ArrayList in Java to be O (1), or at least amortized too such
by pacaro 3y ago
This is, of course, the same mechanism that allows appending to an ArrayList in Java to be O (1), or at least amortized too such
- kadoban 3y agoEdit: the following is wrong, sorry about that. Interestingly, the C++ standard doesn't specify a cost for this, or an implementation. So there could be some C++ implementation out there somewhere that just copies the whole string on each append. This is in contrast to std::vector, where the cost of adding one element to the end _is_ specified to be amortized O(1).
- foota 3y agoAre there reasonable string implementations lacking 0(1) amortized append runtime?
- deleted 3y ago[deleted]
- sltkr 3y agoNo, 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 https://news.ycombinator.com/item?id=38032949
- not2b 3y agoNo, 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.
- rurban 3y agoIt 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 https://news.ycombinator.com/item?id=38033206
- sltkr 3y agoThe 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.
- lmm 3y agoMight an implementor use a specialised implementation for operator+= that performs better for practical-sized strings while not being O(1)?
- vitus 3y ago> 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/n4849.pdf 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)
- kadoban 3y agoWoops, thanks. Not sure how I missed that.
- AnimalMuppet 3y agoYeah. It was only on page 797! How could you miss that? ;-)
- deleted 3y ago[deleted]