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

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

--- David Abrahams <david.abrahams_at_[hidden]> wrote:
> I'm really glad that someone is taking an active
> interest in this subject
> again!
> 
> Please have a look at
> 
> http://groups.yahoo.com/group/boost/message/3226
> http://groups.yahoo.com/group/boost/message/3777
>
http://groups.yahoo.com/group/boost/files/associative_vector/
> 
> Without having looked at your code, I'll surmise
> that iterator stability is
> acheived by embedding a reference to the vector and
> an offset in the
> iterator. I am not convinced that iterator stability
> is usually worth the
> cost, and I'd rather not pay for it if I wasn't
> going to use it. 

This is a valid concern.  The way we achieve iterator
stability is we hold a long that is the element number
in the vector + a version index, that we use to update
the position of the iterator if necessary.  In fact,
with our scheme you pay almost no penalty unless you
insert elements into the container after the first
lookup operation so we think we get about the minimum
overhead possible using a direct vector to hold the
data.

> My plan for
> implementing stability was to provide
> pointer/reference stability via an
> indirect_container adaptor which uses
> boost::indirect_iterator (In fact,
> this is the work that spawned the Boost Iterator
> Adaptors Library). This
> approach has several advantages, not least that
> reallocating the vector
> becomes very cheap because it just has to copy POD
> data.
> 
> -Dave

Well, the big concern we would have with this is
speed and efficiency.  It is true that you get
exception safety but the indirect approach has two
disadvantages:
1. More overhead have to keep an extra pointer around
versus just holding the data itself.

2. More seriously, the big problem would be that with
the indirect approach the elements are no longer held
contiguously in memory and you have to go through a
pointer to compare them.  The big advantage that our
benchmarks show for a vector is that because the
elements are held directly and contiguously in memory,
sorts are very fast on the resulting data giving the
final container a big advantage over multiset.  If you
give this up and hold the data via a container of
pointers it seems likely to me that you would take a
large performance hit as a result and perhaps not be
any faster than a multiset.  (Two reasons, memory
contiguity and a functor hit to compare the (data *)
items). Of course, the proof is in the pudding, Corwin
and I can do some simple benchmarks to see.

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.

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