Re: Proposal: Sorted Vector Container

From: corwinjoy (cjoy_at_[hidden])
Date: 2002-01-08 16:37:50

--- In boost_at_y..., "dave_abrahams" <david.abrahams_at_r...> wrote:
> Reviving an old thread:
> 
> Despite my arguments with the completeness of testing here, I think 
> the design approach is valuable for many problems. I find myself 
> AGAIN with the need for an associative vector in Boost.Python, and 
> I'm considering sticking my associative vector in the detail 
> namespace... but I'd really rather see something officially in 
Boost.
> 
> Can we make progress on this? Any framework for associative vectors 
> should allow both of these approaches, in addition to the 
> straightforward one which has no stability across modifications.
> 
> -Dave
> 

I think it would be nice to try to come to some agreement on a family 
of solutions for this.  In an ideal world perhaps this could even be 
done via some kind of policy trait(s).  To me, it seems like the 
design decision points are something like this:

1. After the container is first sorted, is it the container's job or 
the user's job to sort it if elements are later added or removed?

2. Do you need it to be exception safe for inserts/erases? (If so, 
you are likely looking at a pointer implementation).

3. How large are your objects?  If they are small, holding them 
directly by value will likely give the fastest sorts/lookups because 
comparisons don't have to go through a pointer.  If they are large, 
holding them by pointer may be faster for sorting because of swap 
time.  (Yes, I know, this statement about speed would need to be 
verified by benchmarking.  Still sort time is a function of time for 
comparison + time for swaps, so I expect that benchmarks will bear 
this out).

So I guess the proposals out there are something like this:

1. Simple sorted vector by value.  
- Fast sort/lookup for small objects.
- Not sorted if inserts are made after the initial sort.
- Iterator invariants not maintianed after deletes.
- Not exception safe for objects whose copy operations can throw.
- Fast iterators.

2. Sorted vector by value with smart iterators.
- Fast sort/lookup for small objects.
- Maintains sort after inserts.  
- Maintains iterator invariants after deletes.
- Not exception safe for objects whose copy operations can throw.
- Slightly slower iterators than case 1.

3. Sorted vector of pointers to values.
- Slower sort than 1 or 2 for small objects.  Likely faster sort than 
1 or 2 as the object size gets bigger because swaps are faster.  
Lookup speed will still be slower than 1 or 2.
- More memory overhead than 1 or 2 because of extra pointers.
- Maintains sort after inserts.  
- Maintains iterator invariants after deletes.
- Can give exception safety.
- Iterators very nearly as fast as 1.
- Can give multiple sorts versus the same data set.

That's my feeling for how the different designs stack up.  To me, it 
is not obvious that any one of these designs is "best" in all 
situations so that having some ability to choose based on the 
application / object size makes sense.