Re: associative_vector: request for formal review

From: Dave Abrahams (abrahams_at_[hidden])
Date: 2000-06-01 15:58:59

--- In boost_at_[hidden], "John E. Potter" <jpotter_at_f...> wrote:
> 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.

To be honest, that's not my reading of the standard; it's my reading 
of everyone
else's reading of the standard (i.e. newsgroup lurking detritus). So 
you
probably have it right.

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

Yes, I understand you. I don't care which one we implement. I also 
don't care
whether we implement the standard guarantee. It's not a set<> after 
all, so it
needn't conform to set's requirements, especially if they're stupid. 
I have been
hoping someone would say there's no need to handle that case.
 
> Fair enough.  How about this?  Please excuse my lack of multiple
> returns.  This replaces your four functions.

It sure looks a lot cleaner, and there are fewer repeated tests. Does 
the
replacement pass the test code (I just love having test code!!!)?

I would make the following IMHO improvements to your improvements:
  
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)))
            return m_impl.insert(result, x);
    }
    // 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))))
            return m_impl.insert(result + 1, x);
    }
    // else we found it already there
    else
    {
        return result;
    }
    
    return insert_unique(x).first;
}
    
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))))
            return m_impl.insert(result, x);
    }
    // Try to insert after the hint position
    else
    {
        if (result + 1 == end()
            || !m_key_compare(KeyOfValue()(*(result + 1)), KeyOfValue
()(x)))
            return m_impl.insert(result + 1, x);
    }
    else
    {
        return result;
    }

    return insert_equal(x);
}