This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofCD1 status.
Section: 23.2.7[associative.reqmts]Status:CD1Submitter: Andrew KoenigOpened: 2000-04-30Last modified: 2016-01-28
Priority:Not Prioritized
View otheractive issues in [associative.reqmts].
View all otherissues in [associative.reqmts].
View all issues withCD1 status.
Discussion:
Ifmm is a multimap andp is an iteratorinto the multimap, thenmm.insert(p, x) insertsx intomm withp as a hint asto where it should go. Table 69 claims that the execution time isamortized constant if the insert winds up taking place adjacent top, but does not say when, if ever, this is guaranteed tohappen. All it says it thatp is a hint as to where toinsert.
The question is whether there is any guarantee about the relationshipbetweenp and the insertion point, and, if so, what itis.
I believe the present state is that there is no guarantee: The usercan supplyp, and the implementation is allowed todisregard it entirely.
Additional comments from Nathan:
The vote [in Redmond] was on whether to elaborately specify the use ofthe hint, or to require behavior only if the value could be insertedadjacent to the hint. I would like to ensure that we have a chance tovote for a deterministic treatment: "before, if possible, otherwiseafter, otherwise anywhere appropriate", as an alternative to theproposed "before or after, if possible, otherwise [...]".
[Toronto: there was general agreement that this is a real defect:when inserting an element x into a multiset that already containsseveral copies of x, there is no way to know whether the hint will beused. The proposed resolution was that the new element should alwaysbe inserted as close to the hint as possible. So, for example, ifthere is a subsequence of equivalent values, then providing a.begin()as the hint means that the new element should be inserted before thesubsequence even if a.begin() is far away. JC van Winkel suppliedprecise wording for this proposed resolution, and also for analternative resolution in which hints are only used when they areadjacent to the insertion point.]
[Copenhagen: the LWG agreed to the original proposed resolution,in which an insertion hint would be used even when it is far from theinsertion point. This was contingent on seeing a exampleimplementation showing that it is possible to implement thisrequirement without loss of efficiency. John Potter provided such aexample implementation.]
[Redmond: The LWG was reluctant to adopt the proposal thatemerged from Copenhagen: it seemed excessively complicated, and wentbeyond fixing the defect that we identified in Toronto. PJP providedthe new wording described in this issue. Nathan agrees that weshouldn't adopt the more detailed semantics, and notes: "we know thatyou can do it efficiently enough with a red-black tree, but there areother (perhaps better) balanced tree techniques that might differenough to make the detailed semantics hard to satisfy."]
[Curaçao: Nathan should give us the alternative wording hesuggests so the LWG can decide between the two options.]
[Lillehammer: The LWG previously rejected the more detailed semantics, because it seemed more loike a new feature than like defect fixing. We're now more sympathetic to it, but we (especially Bill) are still worried about performance. N1780 describes a naive algorithm, but it's not clear whether there is a non-naive implementation. Is it possible to implement this as efficently as the current version of insert?]
[Post Lillehammer:N1780updated in post meeting mailing withfeedback from Lillehammer with more information regarding performance.]
[Batavia:1780accepted with minor wording changes in the proposed wording (reflected in theproposed resolution below). Concerns about the performance of the algorithmwere satisfactorily met by1780.371(i) already handles the stability of equal rangesand so that part of the resolution from1780is no longer needed (or reflected in the proposed wording below).]
Proposed resolution:
Change the indicated rows of the "Associative container requirements" Table in23.2.7[associative.reqmts] to:
| expression | return type | assertion/note pre/post-condition | complexity |
|---|---|---|---|
a_eq.insert(t) | iterator | insertst and returns the iterator pointing to the newly insertedelement.If a range containing elements equivalent tot exists ina_eq,t is inserted at the end of that range. | logarithmic |
a.insert(p,t) | iterator | insertst if and only if there is no element with key equivalent to thekey oft in containers with unique keys; always insertst in containerswith equivalent keys. always returns the iterator pointing to the element with keyequivalent to the key oft.p is a hint pointing to wherethe insert should start to search.t is inserted as close as possibleto the position just prior top. | logarithmic in general, but amortized constant ift is inserted rightp. |