[Python-Dev] collections module

[Martin v. Loewis]

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