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

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-08 16:52:54

----- Original Message -----
From: "corwinjoy" <cjoy_at_[hidden]>

> 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?

I want to at least have an interface available which lets me say, "I know
what I'm doing; put this /here/, and don't waste any time
verifying/re-sorting".

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

Disagree strongly, unless you have a degenerate view of exception-safety
(see
http://groups.google.com/groups?selm=a1dbu1%24p1g%241%40bob.news.rcn.net).

> 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.

There should be an insert interface which inserts in-order.
There should also be one that inserts "with hint" at the closest in-order
position to the supplied iterator.

> - Iterator invariants not maintianed after deletes.

No, the iterators are invalidated by deletes. That's markedly different.

> - Not exception safe for objects whose copy operations can throw.

Disagree, again.

> - Fast iterators.
>
> 2. Sorted vector by value with smart iterators.
> - Fast sort/lookup for small objects.
> - Maintains sort after inserts.

There should be an interface which inserts "here", and another which inserts
"with hint" as above.

> - Maintains iterator invariants after deletes.

Of course.

> - Not exception safe for objects whose copy operations can throw.

Disagree again.

> - 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.

There should be an interface which inserts "here", and another which inserts
"with hint" as above.

> - Maintains iterator invariants after deletes.

Of course.

> - Can give exception safety.

Of course.

> - Iterators very nearly as fast as 1.
> - Can give multiple sorts versus the same data set.

Interesting application. It should have an ownership policy.

> 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.

Agreed.

-Dave