3 ms·
Are there reasonable string implementations lacking 0(1) amortized append runtime?
by foota 3y ago
Are 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