3 ms·
An interesting side effect is that naive use of std::vector::reserve can turn an O(N) algorithm into O(N^2). If you just do push_back() N times, it's guarantee
by yongjik 6y ago
An interesting side effect is that naive use of std::vector::reserve can turn an O(N) algorithm into O(N^2). If you just do push_back() N times, it's guaranteed O(N). If you have a function that inserts 10 elements, and prefix it with reserve(v.size() + 10), then it will only reserve ten more slots - if you keep calling it, the result is O(N^2).
- xaedes 6y agoIndeed, good observation! The amortized runtime for N push_back will only be O(N) if the underlying array is resized to a constant factor > 1 times the required size (e.g. doubling it each time it's full). When prefixing with reserve of the actual required size, then, as you say, the amortized runtime for the N push_backs will be O(N^2). I once investing a particularly slow routine to import csv to numpy-array of a million lines or so. It read csv lines in a numpy array, calling hstack for each new line, resulting in huge runtimes. Since then I have seen similar misuses of hstack and the like. When you do similar, it is important to resize (by hstack or whatever) to a constant factor > 1 times the required size. Don't forget to remember the current size, as the size of the underlying array is now the capacity.