0

Item 13 in Herb Sutter's More Exceptional C++ book talks about std::string and the different growth strategies during resizing. It mentions how growing the buffer size exponentially will lead to O(LogN) memory allocation and O(1) copy operations per character.

I don't understand how the memory allocations and copy operations have different time complexity here. If on every re-sizing we allocate a new buffer and copy the chars from the old buffer to the new one, shouldn't the complexity of copies and memory allocations be the same?

Aykhan Hagverdili
  • 28,141
  • 6
  • 41
  • 93
Kareem Aboughazala
  • 535
  • 1
  • 6
  • 15
  • I think you missed an important word. It should talk about *amortized* complexity. – spectras Sep 29 '22 at 14:06
  • That's the number/cost of allocation itself, not including anything else like copying over data. Allocation itself does not require touching each byte in the allocated memory range. Each allocation is presumed constant time. – user17732522 Sep 29 '22 at 14:15

0 Answers0