 # 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);
> 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;