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

Subject: Re: [boost] Offering sorted_vector for Boost, any interest?
From: Nathan Ridge (zeratul976_at_[hidden])
Date: 2012-02-15 18:58:44

> From: ramey_at_[hidden]
>
> 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?

Well, given the number of problems with that code, I thought
perhaps you were trying to make the opposite point by
illustration (that people *shouldn't* roll their own even if 
it seems simple, because of the capacity for making mistakes). 
My mistake, and my apologies.

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

In that case, the class should prevent users from calling mutating
operations (for example by inheriting privately, and then bringing
the nonmutating operations into scope via using declarations).
Leaving the mutating operations accessible while using them can
break the invariants of the class, causing silent runtime errors,
is definitely a no-no.

> I think it illustrates
> also that its easier just to compose standard elements than
> to write a new library.

I think what it illustrated, intentionally or not, is that it's
easy to compose standard elements badly and think you've done it
right :) A carefully designed and well thought-out library, on
the other hand, can serve many different related use cases.

Regards,
Nate