Boost logo

Boost :

From: Dave Abrahams (abrahams_at_[hidden])
Date: 2000-06-01 06:56:00


on 5/31/00 5:45 PM, John E. Potter at jpotter_at_[hidden] wrote:

> I finally convinced myself that the two aux functions work. The
> negative logic is rather confusing. I think you have the standard
> case backwards. We would all like insert at (before) pos and the
> standard requires after to be linear. You are testing before
> first and then before pred rather than after pos == before succ.

It took me a long time to figure out what you were saying above, but I think
I have it now. AFAIK, the standard says that if you provide a hint which
points to the position *after* the place where the element should go, it
will be inserted in O(1). Then to be compatible with the standard, I need to
check the position *before* the hint to see if it is the correct one. What
am I missing?

> Using positive logic and pseudocode, this seems simpler:
>
> Equal
> // What we want, before
> if ((pos == end || x <= *pos) && (pos == begin || *(pos-1) <= x))
> return m_impl.insert(pos, x);
> // What the standard says, after
> if (pos != end && *pos <= x && (pos+1 == end || x <= *(pos+1))
> return m_impl.insert(pos+1, x);
> // Bad hint
> return insert_equal(x);
>
> Unique
> // What we want, before
> if ((pos == end) || x < *pos) && (pos == begin || *(pos-1) < x))
> return m_impl.insert(pos, x);
> // What the standard says, after
> if (pos != end && *pos < x && (pos+1 == end || x < *(pos+1))
> return m_impl.insert(pos+1, x);
> // What Ed Brey wants
> if (pos != end && x <= *pos && x >= *pos)
> return pos;
> // Bad hint
> return insert_unique(x).first;
>
> There are some repeated tests, but the expected to pass tests
> come first. It could be factored to remove the repeated tests
> at the expense of slightly more complex code. Since the insert
> to the vector will be linear, it likely outweighs all of the
> tests.

Why gamble? An element may be defined such that the comparisons are much
more expensive than copying.

-Dave


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk