Re: [boost] Re: associative_vector: request for formal review

From: John E. Potter (jpotter_at_[hidden])
Date: 2000-06-01 18:20:01

On Thu, 1 Jun 2000, Dave Abrahams wrote:

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

There's no need to handle that case, it's stupid.  <g>

> 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!!!)?

Unfortunately, I don't have access to a compiler that will handle
it currently.  I had to settle for a proof of correctness and
experience fixing broken versions of these functions.  Two widely
used library versions do not even attempt to get it right.  Maybe
someone can test this newest version if it looks good.

> I would make the following IMHO improvements to your improvements:

Expected, it matches your style.  This old SESE has trouble writing
it, but I can read it.  There were some problems with your fix of 
insert_equal because that function must always insert.

Let's get rid of the stupid case and make something which is really
simple look simple.

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 pos = begin() + (position - begin());
    // Try to insert at the hint position
    if (pos == end() ||
            m_key_compare(KeyOfValue()(x), KeyOfValue()(*pos)))
    {
        if (pos == begin() ||
                m_key_compare(KeyOfValue()(*(pos - 1)), KeyOfValue()(x)))
            return m_impl.insert(pos, x);
    }
    // Keep Ed happy with one compare, it's a reasonable request.
    else if (! m_key_compare(KeyOfValue()(*(pos)), KeyOfValue()(x)))
    {
        return pos;
    }
    
    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 pos = begin() + (position - begin());
    // Try to insert at the hint position
    if ((pos == end()
            || ! m_key_compare(KeyOfValue()(*pos), KeyOfValue()(x)))
          && (pos == begin()
            || ! m_key_compare(KeyOfValue()(x),
            KeyOfValue()(*(pos - 1)))))
    {
        return m_impl.insert(pos, x);
    }
    return insert_equal(x);
}

BTW, I did notice your proof of concept use of const_iterator
parameters in non-const functions.  Nice.

Regards,
John