RE: [boost] Re: Proposal: Sorted Vector Container

From: Brey, Edward D (EdwardDBrey_at_[hidden])
Date: 2002-01-08 17:23:34

{Dave}
There should be an insert interface which inserts in-order.
There should also be one that inserts "with hint" at the closest in-order
position to the supplied iterator.

{Ed}
If I understand you correctly, you're saying that there should be a
validated and non-validated insertion, where the non-validated insertion has
a postcondition of an ordered (and hence acceptable for lookup) container if
the position argument be the correct insertion spot in a previously ordered
container.  If so, I agree with this.

However, the way you worded it sounds to me like a contradiction.  The
phrase "the closest in-order position" sounds deterministic, whereas "hint"
by its nature means that the implementation can ignore the request.  I
realize that this is probably not what you were getting at.  I just want to
stress the importance of precisely defining directed insertion, especially
if the container supports equivalence of keys.

The std associative containers are a mess in this regard.  This is a good
opportunity put forth sound semantics.  See library issue 192 for a
proposal.
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-closed.html#192

(BTW, issue 192 used to be marked [FUTURE], but I noticed a while back that
that indication quietly went away.  Does the committee have a long-term
solution in mind to the associative container insertion issue?)