[New-bugs-announce] [issue26194] Undefined behavior for deque.insert() when len(d) == maxlen

[Raymond Hettinger]

New submission from Raymond Hettinger:

The behavior of deque.insert() in a bounded deque is a bit odd:

>>> from collections import deque
>>> d = deque(range(20), maxlen=10)
>>> d
deque([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], maxlen=10)
>>> d.insert(3, 'New')
>>> d
deque([19, 10, 11, 'New', 13, 14, 15, 16, 17, 18], maxlen=10)
#       ^   ^        ^--- The 12 got replaced
#       |   \--- The elements before the insertion point got rotated
#       \--- The final element got rotated to first position

With append/appendleft/extend/extendleft, the intended and useful behavior for maxlen is to pop from the opposite end.  But for deque.insert(), the best and most useful behavior invariants are less obvious.

Ideally, the effect of d.insert(0, item) would be the same as d.appendleft(item), and the effect of d.insert(len(d), item) would be the same as d.append(item).  

Also, d.insert(i, newitem) should have the post-condition:

  assert d[i] == newitem if i < len(d) else d[-1] == newitem

Having decided where to put the newitem, the question turns to deciding which element should be popped-off to maintain the size invariant.

I'm thinking that it should always be the rightmost element that gets popped, so that items before the inserted element never get moved.  This matches what insert() does for unbounded deques, making it the least surprising choice.

----------
assignee: rhettinger
components: Extension Modules
messages: 258893
nosy: rhettinger
priority: normal
severity: normal
status: open
title: Undefined behavior for deque.insert() when len(d) == maxlen
type: behavior
versions: Python 3.5, Python 3.6

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue26194>
_______________________________________