Nevin Liber wrote:
On 15 February 2012 15:27, Robert Ramey <ramey@rrsd.com> 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