233. Insertion hints in associative containers

Section: 26.2.6 [associative.reqmts] Status: CD1 Submitter: Andrew Koenig Opened: 2000-04-30 Last modified: 2016-02-10

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: 192, 246

Discussion:

If mm is a multimap and p is an iterator into the multimap, then mm.insert(p, x) inserts x into mm with p as a hint as to where it should go. Table 69 claims that the execution time is amortized constant if the insert winds up taking place adjacent to p, but does not say when, if ever, this is guaranteed to happen. All it says it that p is a hint as to where to insert.

The question is whether there is any guarantee about the relationship between p and the insertion point, and, if so, what it is.

I believe the present state is that there is no guarantee: The user can supply p, and the implementation is allowed to disregard it entirely.

Additional comments from Nathan:
The vote [in Redmond] was on whether to elaborately specify the use of the hint, or to require behavior only if the value could be inserted adjacent to the hint. I would like to ensure that we have a chance to vote for a deterministic treatment: "before, if possible, otherwise after, otherwise anywhere appropriate", as an alternative to the proposed "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 contains several copies of x, there is no way to know whether the hint will be used. The proposed resolution was that the new element should always be inserted as close to the hint as possible. So, for example, if there is a subsequence of equivalent values, then providing a.begin() as the hint means that the new element should be inserted before the subsequence even if a.begin() is far away. JC van Winkel supplied precise wording for this proposed resolution, and also for an alternative resolution in which hints are only used when they are adjacent 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 the insertion point. This was contingent on seeing a example implementation showing that it is possible to implement this requirement without loss of efficiency. John Potter provided such a example implementation.]

[Redmond: The LWG was reluctant to adopt the proposal that emerged from Copenhagen: it seemed excessively complicated, and went beyond fixing the defect that we identified in Toronto. PJP provided the new wording described in this issue. Nathan agrees that we shouldn't adopt the more detailed semantics, and notes: "we know that you can do it efficiently enough with a red-black tree, but there are other (perhaps better) balanced tree techniques that might differ enough to make the detailed semantics hard to satisfy."]

[Curaçao: Nathan should give us the alternative wording he suggests 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: N1780 updated in post meeting mailing with feedback from Lillehammer with more information regarding performance. ]

[ Batavia: 1780 accepted with minor wording changes in the proposed wording (reflected in the proposed resolution below). Concerns about the performance of the algorithm were satisfactorily met by 1780. 371 already handles the stability of equal ranges and so that part of the resolution from 1780 is no longer needed (or reflected in the proposed wording below). ]

Proposed resolution:

Change the indicated rows of the "Associative container requirements" Table in 26.2.6 [associative.reqmts] to:

Associative container requirements
expression return type assertion/note
pre/post-condition
complexity
a_eq.insert(t) iterator inserts t and returns the iterator pointing to the newly inserted element. If a range containing elements equivalent to t exists in a_eq, t is inserted at the end of that range. logarithmic
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. t is inserted as close as possible to the position just prior to p. logarithmic in general, but amortized constant if t is inserted right after before p.