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

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-08 18:02:40

----- Original Message -----
From: "Brey, Edward D" <EdwardDBrey_at_[hidden]>

> {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.

Nope, I want to say instead that lookup has a precondition that the
container is sorted. IOW, I want to be able to say:

assoc_vec<int> x(make_counting_iterator(0), make_counting_iterator(25));
x.insert(make_counting_iterator(75), make_counting_iterator(100));
x.insert(x.lower_bound(30)
    , make_reverse_iterator(make_counting_iterator(70))
    , make_reverse_iterator(make_counting_iterator(30))); // legal!

x.lower_bound(42); // illegal

sort(x.begin(), x.end());
x.lower_bound(42); // legal

> 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,

Yes.

> whereas "hint"
> by its nature means that the implementation can ignore the request.

In this case it means that you're saying the insert position is "near here".
If you want to call it "nearest" instead of "hint" or something, it's OK
with me.

>  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.

I agree it's important.

> 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?)

My proposal was the original resolution to
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#233, though we
"chickened out" and opted not to invent new functionality at the last
minute.

-Dave