Boost logo

Boost :

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
> a postcondition of an ordered (and hence acceptable for lookup) container
> the position argument be the correct insertion spot in a previously
> 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));
    , 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,


> 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
> 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.
> (BTW, issue 192 used to be marked [FUTURE], but I noticed a while back
> 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, though we
"chickened out" and opted not to invent new functionality at the last


Boost list run by bdawes at, gregod at, cpdaniel at, john at