**Section:** 24.3.11.5 [vector.modifiers] **Status:** CD1
**Submitter:** Lisa Lippincott **Opened:** 2000-06-06 **Last modified:** 2016-01-28 10:19:27 UTC

**Priority: **Not Prioritized

**View all other** issues in [vector.modifiers].

**View all issues with** CD1 status.

**Discussion:**

Paragraph 2 of 24.3.11.5 [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 (24.3.8.4 [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.

**Proposed resolution:**

Change Paragraph 2 of 24.3.11.5 [vector.modifiers] to

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

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

Change 24.3.8.4 [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.

**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.