
Boost : 
From: John E. Potter (jpotter_at_[hidden])
Date: 20000601 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;
}
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk