Re: [boost] associative_vector: request for formal review

From: John E. Potter (jpotter_at_[hidden])
Date: 2000-06-01 12:34:08

On Thu, 1 Jun 2000, Dave Abrahams wrote:

> on 5/31/00 5:45 PM, John E. Potter at jpotter_at_[hidden] wrote:
> 
> > 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?

That sure is a different reading of the standard than I have heard.  No
wonder that part has caused so much confusion.  I read the standard as
saying O(1) if the insertion is "after" the hint.  It says t after p
not p after t.

Let v = 1 3 5 7 and p point to the 5.
I think everyone wants insert 4 to be O(1) compares.
I think the standard demands insert 6 to be O(1) compares.
You are testing for insert 2 to be O(1).

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

Fair enough.  How about this?  Please excuse my lack of multiple
returns.  This replaces your four functions.

John

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
associative_vector<Key, Value, KeyOfValue, Compare, Alloc>::iterator
associative_vector<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(
    const_iterator position, const value_type& x)
{
    iterator result = begin() + (position - begin());
    // Try to insert at the hint position
    if (result == end() ||
            m_key_compare(KeyOfValue()(x), KeyOfValue()(*result)))
        if (result == begin() ||
                m_key_compare(KeyOfValue()(*(result - 1)), KeyOfValue()(x)))
            result = m_impl.insert(result, x);
        else
            result = insert_unique(x).first;
    // Try to insert after the hint position
    else if (m_key_compare(KeyOfValue()(*(result)), KeyOfValue()(x)))
        if (result + 1 == end() ||
                m_key_compare(KeyOfValue()(x), KeyOfValue()(*(result + 1))))
            result = m_impl.insert(result + 1, x);
        else
            result = insert_unique(x).first;
    // else we found it already there
    return result;
}
    
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
associative_vector<Key, Value, KeyOfValue, Compare, Alloc>::iterator
associative_vector<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(
    const_iterator position, const value_type& x)
{
    iterator result = begin() + (position - begin());
    // Try to insert at the hint position
    if (result == end() ||
            ! m_key_compare(KeyOfValue()(*result), KeyOfValue()(x)))
        if (result == begin() || ! m_key_compare(KeyOfValue()(x),
                KeyOfValue()(*(result - 1))))
            result = m_impl.insert(result, x);
        else
            result = insert_equal(x);
    // Try to insert after the hint position
    else
        if (result + 1 == end() ||
                ! m_key_compare(KeyOfValue()(*(result + 1)),
                KeyOfValue()(x)))
            result = m_impl.insert(result + 1, x);
        else
            result = insert_equal(x);
    return result;
}