The problem with allocating is not the algorithm complexity, it's the fact it may need to allocate new pages from the operating system, which is a somewhat expe

The problem with allocating is not the algorithm complexity, it's the fact it may need to allocate new pages from the operating system, which is a somewhat expensive operation. If you use a global allocator, when this happens is entirely non-deterministic. If you use a local iterator, at least you control when that happens, and have guarantees on the asymptotical behaviour.