Re: [boost] Re: Proposal: Sorted Vector Container

From: Mike Gradman (windryder1_at_[hidden])
Date: 2001-11-20 17:20:21

--- David Abrahams <david.abrahams_at_[hidden]> wrote:

> Sorry, I'm having trouble envisioning this. What
> does the iterator
> dereference operation do? How does it find the
> element without a reference
> to the vector?

We do store a pointer to the vector in our iterators. 
However, the data needed to maintain the iterator is
very minimal, just containing the pointer to the
"vector" it refers to, the index of the element, and
the index version which is used to update the iterator
position if necessary.  Here's the relevant part of
our
const_iterator:

// in vec_multiset
class const_iterator // ...
{
// ...
protected:
 size_type index; // index of the element in 
                  // *pContainer we're pointing to
 bool bValid;	 // is this iterator pointing to a 
                 // valid element
                 // (invalidate erased elements)
 my_type *pvec_ms; // pointer to the vec_multiset
                   // iterating over
 size_t idxVersion; // index into change log of 
                    // insertions and erasures
                    // since first sort after setup
                   // phase ... note: no penalty
                   // in vec_multiset if no 
                   // modifications made
                   // after first lookup
// ...
};

The logic when you dereference an iterator is
basically:

(for const_iterator::operator*() for example)
1.  Update the iterator index from the change log
if needed.
2.  Return vec[index].

Its cousins, operator->(), ++, --, etc., are similar.
Note that the application of the change log happens
in a lazy/just-in-time fashion.  So, in other words
we only take the time to update an iterator's position
if it is really being used.  This keeps the work we
do in maintaining iterator invariants to a minimum.

> > Anyway, so we think that our container offers some
> > nicer performance advantages over the previous
> > submissions while retaining iterator stability.
> > Anyway, Corwin and I will do some more benchmarks
> > to show this.

> I'm interested.

We're getting on the benchmarking!

Cheers,
Mike

__________________________________________________
Do You Yahoo!?
Yahoo! GeoCities - quick and easy web site hosting, just $8.95/month.
http://geocities.yahoo.com/ps/info1