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