From: ramey@rrsd.com
Nathan Ridge wrote:
From: ramey@rrsd.com
#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