Re: [boost] Offering sorted_vector for Boost, any interest?

Subject: Re: [boost] Offering sorted_vector for Boost, any interest?
From: Nevin Liber (nevin_at_[hidden])
Date: 2012-02-15 17:16:05

On 15 February 2012 15:27, Robert Ramey <ramey_at_[hidden]> wrote:

> I guess the issue is - what's trivial.  It seems to that something like:
>
> // some comments here
> template<class T, class A>
> class fast_set : public std::vector<T, A> {
>    const T & find(const T & t){
>        static bool sorted = false;
>        if(! sorted){
>            std::sort(begin(), end());
>            sorted = true;
>        }
>        std::vector<T, A>::find(t);
>    };
> };
>
> is pretty simple.

I really don't think you want to be making that claim...

A few problems off the top of my head:

1.  It doesn't return anything.
2.  std::vector doesn't have a find method.
3.  std::find() would be O(n), not O(log n).
4.  You probably want to do the "sort" on insert, not find, as you can
usually do much better performance-wise than std::sort when inserting
into an already sorted container.
5.  If you sort on insert, you don't need mutable members for const correctness.
6.  If you sort on insert, you can call find() from multiple threads
safely when no one is modifying the container.
7.  You want to default A so that it matches the other containers.

> Certainly simpler than documentation, header, tests
> etc required to make it a library.

I eagerly await you posting your revised version where that is true
(and doesn't just include flat_set).

> Some things are just to simple and obvious to need a library.

People keep telling me that... :-)
-- 
 Nevin ":-)" Liber  <mailto:nevin_at_[hidden]>  [phone]