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

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

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

> 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
>
> OK.  It sounds like the we are saying the same thing in slightly different
> words.  I agree that lower_bound needs the precondition that the container
> is sorted?  So when is the container sorted?  When unsafe_insert's
> postcondition says that it is sorted.  When is that?  When unsafe_insert's
> position parameter happens to be the right location.

Sorry, I don't think I'm picking nits here. As I understand it, if an
operation's postcondition doesn't hold, an error has occurred.

> Your example makes the second lookup work by doing a sort.  My example
makes
> it work by inserting into the right location in the first place so that
the
> container is never unsorted in the first place.  Both methods should be
> allowed.

I agree with that part.

> {Dave}
> 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.
>
> My reading of this indicates that the plan is to continue to _not_ give
the
> programmer control over the insertion location.  This is too bad, since
that
> would comes in handy on occasion.  It would be nice if the vector
> associative containers provided the programmer control over precise
> insertion location.

That was the point of my proposal. It also lets you say

v.insert_with_hint(v.begin(), x); // insert at first valid location
v.insert_with_hint(v.end(),x);  // insert at last valid location

-Dave