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 18:28:47

Nathan Ridge wrote:
>> From: ramey_at_[hidden]
>>
>> #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);
>> };
>> };
>
> I'm still not entirely sure whether you're being serious, but
> in the event that you are:

why would you think I'm not serious?

> 1. A 'static' variable declared inside a method is shared
> by all class instances. What you want is a class member variable.

obviously you're correct on this.

> 2. Mutating operations like push_back() do not preserve the
> invariant "'sorted' is true iff. the elements are sorted".
> So, if you find() and then push_back() and then find() again,
> the second find() may return an incorrect result.
>
> To get this approach to work properly, you'd have to override
> every mutating operation and have it clear the 'sorted' flag.

hmmm - I was go on the initial post which specified

1. fills the set only once,
2. just wants to drop duplicates or
3. calls set::find very often.

and I think that's what my example does.  I think it illustrates
also that its easier just to compose standard elements than
to write a new library.

Of course, maybe I didn't get what the poster really wanted
- a common occurence.

In any case, I'll concede that I've failed to convince everyone
that this thing is too trivial to merit a library.

Robert Ramey