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.
Section: 23.2.7 [associative.reqmts] Status: CD1 Submitter: Andrew Koenig Opened: 2000-04-30 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.
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(i) 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 23.2.7 [associative.reqmts] to:
| 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. 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 p.
|