Re: [boost] associative_vector: request for formal review

From: John E. Potter (jpotter_at_[hidden])
Date: 2000-05-31 16:45:54

On Tue, 30 May 2000, Dave Abrahams wrote:

> The associative_vector, vector_set, and vector_multiset templates are 
> available in the associative_vector folder in the Files section. 

Looking at associative_vector only.

insert(pos, value)

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.
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);
// Bad hint
   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;
// Bad hint
   return insert_unique(x).first;

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.

John