Tim Peters wrote:
Hm. An idea: don't bother overallocating when inserting in the front, but do keep the free space in the front if possible.
I'm not clear on what that means, and the devil's in the details.
I interpret it as: when doing an insert in the middle or at the beginning, continue doing what we do today. I.e. never overallocate extra space in the front, unless the extra space is already there (so realloc would just copy it/leave it as-is). When appending, you would then first check whether there is space at the beginning, and move items if there is. Otherwise reallocate, with the overallocation-to-the-right formula.
Then recommend that queues are implemented using append(x) and pop(0), rather than using insert(0, x) and pop().
Given the way realloc() works, I expect that add-at-the-right will always be favored.
Indeed, I would always implement lists as .append/.pop(0) - it would not have occurred to my mind to write them as insert(0, x)/.pop(), as I consider .insert on a list unintuitive. Regards, Martin