This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofCD1 status.
insert(i, j) complexity requirements are not feasible.Section: 23.2.7[associative.reqmts]Status:CD1Submitter: John PotterOpened: 2000-09-07Last modified: 2016-01-28
Priority:Not Prioritized
View otheractive issues in [associative.reqmts].
View all otherissues in [associative.reqmts].
View all issues withCD1 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 oddintegers in the same range.
Proposed resolution:
In Table 69, in section 23.1.2, change the complexity clause forinsertion of a range from "N log(size() + N) (N is the distancefrom i to j) in general; linear if [i, j) is sorted according tovalue_comp()" to "N log(size() + N), where N is the distancefrom i to j".
[Copenhagen: Minor fix in proposed resolution: fixed unbalancedparens in the revised wording.]
Rationale:
Testing for valid insertions could be less efficient than simplyinserting the elements when the range is not both sorted and betweentwo adjacent existing elements; this could be a QOI issue.
The LWG considered two other options: (a) specifying that thecomplexity was linear if [i, j) is sorted according to value_comp()and between two adjacent existing elements; or (b) changing toKlog(size() + N) + (N - K) (N is the distance from i to j and K is thenumber of elements which do not insert immediately after the previouselement from [i, j) including the first). The LWG felt that, sincewe can't guarantee linear time complexity whenever the range to beinserted is sorted, it's more trouble than it's worth to say that it'slinear in some special cases.