Rationale:

This is a real defect, and proposed resolution fixes it: some complexities aren't specified that should be. This proposed resolution does constrain deque implementations (it rules out the most naive possible implementations), but the LWG doesn't see a reason to permit that implementation.

[ For input iterators, one may achieve this complexity by first inserting at the end of the vector, and then using rotate. ]

Change [deque.modifiers], paragraph 3, to:

Complexity: The complexity is linear in the number of elements inserted plus the shorter of the distances to the beginning and end of the deque. Inserting a single element at either the beginning or the end of a deque causes a single call to the copy constructor of T.

Proposed resolution:

Change Paragraph 2 of [vector.modifiers] to

Complexity: The complexity is linear in the number of elements inserted plus the distance to the end of the vector.

Paragraph 2 of [vector.modifiers] describes the complexity of vector::insert:

Complexity: If first and last are forward iterators, bidirectional iterators, or random access iterators, the complexity is linear in the number of elements in the range [first, last) plus the distance to the end of the vector. If they are input iterators, the complexity is proportional to the number of elements in the range [first, last) times the distance to the end of the vector.

First, this fails to address the non-iterator forms of insert.

Second, the complexity for input iterators misses an edge case -- it requires that an arbitrary number of elements can be added at the end of a vector in constant time.

I looked to see if deque had a similar problem, and was surprised to find that deque places no requirement on the complexity of inserting multiple elements ([deque.modifiers], paragraph 3):

Complexity: In the worst case, inserting a single element into a deque takes time linear in the minimum of the distance from the insertion point to the beginning of the deque and the distance from the insertion point to the end of the deque. Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to the copy constructor of T.