Section: 23.2.7 [associative.reqmts] Status: NAD Submitter: Ed Brey Opened: 1999-06-06 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 NAD status.
Duplicate of: 233
Discussion:
As defined in 23.1.2, paragraph 7 (table 69), a.insert(p,t) suffers from several problems:
| expression | return type | pre/post-condition | complexity |
a.insert(p,t) |
iterator |
inserts t if and only if there is no element with key equivalent to the key of t in containers with unique keys; always inserts t in containers with equivalent keys. always returns the iterator pointing to the element with key equivalent to the key of t . iterator p is a hint pointing to where the insert should start to search. | logarithmic in general, but amortized constant if t is inserted right after p . |
1. For a container with unique keys, only logarithmic complexity is guaranteed if no element is inserted, even though constant complexity is always possible if p points to an element equivalent to t.
2. For a container with equivalent keys, the amortized constant complexity guarantee is only useful if no key equivalent to t exists in the container. Otherwise, the insertion could occur in one of multiple locations, at least one of which would not be right after p.
3. By guaranteeing amortized constant complexity only when t is inserted after p, it is impossible to guarantee constant complexity if t is inserted at the beginning of the container. Such a problem would not exist if amortized constant complexity was guaranteed if t is inserted before p, since there is always some p immediately before which an insert can take place.
4. For a container with equivalent keys, p does not allow specification of where to insert the element, but rather only acts as a hint for improving performance. This negates the added functionality that p would provide if it specified where within a sequence of equivalent keys the insertion should occur. Specifying the insert location provides more control to the user, while providing no disadvantage to the container implementation.
Proposed resolution:
In 23.2.7 [associative.reqmts] paragraph 7, replace the row in table 69 for a.insert(p,t) with the following two rows:
| expression | return type | pre/post-condition | complexity |
a_uniq.insert(p,t) |
iterator |
inserts t if and only if there is no element with key equivalent to the key of t. returns the iterator pointing to the element with key equivalent to the key of t. | logarithmic in general, but amortized constant if t is inserted right before p or p points to an element with key equivalent to t. |
a_eq.insert(p,t) |
iterator |
inserts t and returns the iterator pointing to the newly inserted element. t is inserted right before p if doing so preserves the container ordering. | logarithmic in general, but amortized constant if t is inserted right before p. |
Rationale:
Too big a change. Furthermore, implementors report checking both before p and after p, and don't want to change this behavior.