### 264. Associative container `insert(i, j)` complexity requirements are not feasible.

**Section:** 24.2.7 [associative.reqmts] **Status:** CD1
**Submitter:** John Potter **Opened:** 2000-09-07 **Last modified:** 2016-01-28 10:19:27 UTC

**Priority: **Not Prioritized

**View other** active issues in [associative.reqmts].

**View all other** issues in [associative.reqmts].

**View all issues with** CD1 status.

**Duplicate of:** 102

**Discussion:**

Table 69 requires linear time if [i, j) is sorted. Sorted is necessary but not sufficient.
Consider inserting a sorted range of even integers into a set<int> containing the odd
integers in the same range.

*Related issue: 102*

**Proposed resolution:**

In Table 69, in section 23.1.2, change the complexity clause for
insertion of a range from "N log(size() + N) (N is the distance
from i to j) in general; linear if [i, j) is sorted according to
value_comp()" to "N log(size() + N), where N is the distance
from i to j".

*[Copenhagen: Minor fix in proposed resolution: fixed unbalanced
parens in the revised wording.]*

**Rationale:**

Testing for valid insertions could be less efficient than simply
inserting the elements when the range is not both sorted and between
two adjacent existing elements; this could be a QOI issue.

The LWG considered two other options: (a) specifying that the
complexity was linear if [i, j) is sorted according to value_comp()
and between two adjacent existing elements; or (b) changing to
Klog(size() + N) + (N - K) (N is the distance from i to j and K is the
number of elements which do not insert immediately after the previous
element from [i, j) including the first). The LWG felt that, since
we can't guarantee linear time complexity whenever the range to be
inserted is sorted, it's more trouble than it's worth to say that it's
linear in some special cases.