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

From: Brey, Edward D (EdwardDBrey_at_[hidden])
Date: 2002-01-08 18:22:39

{Dave}
	> {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

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.

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.

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