a.insert(p,t) is incorrectly specifiedSection: 23.2.7 [associative.reqmts] Status: Dup Submitter: Mark Rodgers Opened: 2000-05-19 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 Dup status.
Duplicate of: 233
Discussion:
Closed issue 192 raised several problems with the specification of this function, but was rejected as Not A Defect because it was too big a change with unacceptable impacts on existing implementations. However, issues remain that could be addressed with a smaller change and with little or no consequent impact.
The specification is inconsistent with the original proposal and with several implementations.
The initial implementation by Hewlett Packard only ever looked immediately before p, and I do not believe there was any intention to standardize anything other than this behavior. Consequently, current implementations by several leading implementors also look immediately before p, and will only insert after p in logarithmic time. I am only aware of one implementation that does actually look after p, and it looks before p as well. It is therefore doubtful that existing code would be relying on the behavior defined in the standard, and it would seem that fixing this defect as proposed below would standardize existing practice.
The specification is inconsistent with insertion for sequence containers.
This is difficult and confusing to teach to newcomers. All insert operations that specify an iterator as an insertion location should have a consistent meaning for the location represented by that iterator.
As specified, there is no way to hint that the insertion should occur at the beginning of the container, and the way to hint that it should occur at the end is long winded and unnatural.
For a container containing n elements, there are n+1 possible insertion locations and n+1 valid iterators. For there to be a one-to-one mapping between iterators and insertion locations, the iterator must represent an insertion location immediately before the iterator.
When appending sorted ranges using insert_iterators, insertions are guaranteed to be sub-optimal.
In such a situation, the optimum location for insertion is always immediately after the element previously inserted. The mechanics of the insert iterator guarantee that it will try and insert after the element after that, which will never be correct. However, if the container first tried to insert before the hint, all insertions would be performed in amortized constant time.
Proposed resolution:
In 23.1.2 [lib.associative.reqmts] paragraph 7, table 69, make the following changes in the row for a.insert(p,t):
assertion/note pre/post condition:
Change the last sentence from
"iterator p is a hint pointing to where the insert should start to search."
to
"iterator p is a hint indicating that immediately before p may be a correct location where the insertion could occur."
complexity:
Change the words "right after" to "immediately before".
Rationale: