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

From: Mike Gradman (windryder1_at_[hidden])
Date: 2002-01-08 10:42:10

The nice thing about a sorted vector is the simplicity
of the iterators ... you do have to perform extra
bookkeeping if you wish to guarantee iterator validity
as the standard associative containers do.  

The vec_multiset implementation that Corwin and I
proposed here recently (it deserves another look
probably with this renewed interest in the topic) does
just that: the vector gets sorted with the first
lookup operation (vec_multiset::find(),
vec_multiset::equal_range(), etc.) or on a call to
vec_multiset::begin() or vec_multiset::end().  

The vec_multiset just has to keep track of
inserts/erases that take place after that first lookup
operation. 

Each iterator keeps a pointer back to the vec_multiset
it is iterating over and an index into that change
log.  

It then updates the index of the element its referring
to just in time in order to still logically refer to
the same element since the last time the referred to
element was needed from the iterator.  

This scheme works well if you are inserting many
elements into the container followed by mainly just
doing lookups.  After you start performing lookup
operations on the vec_multiset, you should do very few
insert() or erase() calls.  See Item 23 in Meyers'
Effective STL for more details on the motivation
behind this.

Mike

__________________________________________________
Do You Yahoo!?
Send FREE video emails in Yahoo! Mail!
http://promo.yahoo.com/videomail/