This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of CD1 status.
insert(i, j) complexity requirements are not feasible.Section: 23.2.7 [associative.reqmts] Status: CD1 Submitter: John Potter Opened: 2000-09-07 Last modified: 2016-01-28
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.
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.