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

Subject: Re: [boost] Offering sorted_vector for Boost, any interest?
From: Robert Ramey (ramey_at_[hidden])
Date: 2012-02-15 17:59:46

Nevin Liber wrote:
> 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).

well, I wrote the above in about a minute to illustrate that the
job is trivial.  Of course I'd have to spend a little more time to
get it exactly right.  So after another minute I came up with this
which does compile without error on my MSVC system.
admiitadly, I haven't actually tested it though so it could still
have an error, but I don't think that's the point here.

note that
2) std::set DOES have a find method - which seemed to me
to be a better conceptual match.
3) it is O(log n) for loook up - assuming std::bsearch is
4) I presumed sorting on insert would be a non starter
since it would resort every time one added an item..
6) It has the the same thread guarentees as std::vector
7) I would expect it to closely match std::vector - excepting
the addition of find

But my real point is that adding one more level to hide
the details doesn't always get anything. In this case you
would have to describe an interface which more work.
I submit that these 15 lines of code is easier to understand
than some new library documenation page.

#include <vector>
#include <algorithm>

// 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;
        }
        return std::bsearch(begin(), end(), t);
    };
};

>
>> Some things are just to simple and obvious to need a library.
>
> People keep telling me that... :-)

And they're right!!!

Robert Ramey