You only end up copying O(N^2) elements if you copy elements at all. You need not copy: you just keep a vector of pointers to your fixed buffers, a la GCC's de

You only end up copying O(N^2) elements if you copy elements at all. You need not copy: you just keep a vector of pointers to your fixed buffers, a la GCC's deque implementation. That vector of pointers will be copied (and thus ought to grow by doubles), but each fixed buffer remains the same as the deque grows. I haven't looked at PHP's implementation, and I've long since learned not to expect intelligent, rational implementation decisions from that language community, but it's certainly possible to grow by a fixed amount and remain O(N) by never copying elements at all.