Robert Ramey wrote:

Frank Birbacher wrote:

...

I've come across lots of code that uses std::set where I think a sorted vector would perform better. Those places a characterized by: 1. fills the set only once, 2. just wants to drop duplicates or 3. calls set::find very often. Facing such code I often wished there was a ready to use sorted_vector implementation.

how would this be different than just

a) using std::vector b) use std::sort to sort it c) use std::bsearch to find the element you're looking for

I see no library here.

You need to check your vision! Seriously, others have mentioned flat_set already, but the point is that using std::sort and the other algorithms is not reusable. You must use them, and use them correctly, every time you want the behavior, and you must be sure to use them at the right time. That's the essence of the need for a library: provide a reusable component for non-trivial functionality. _____ Rob Stewart robert.stewart@sig.com Software Engineer using std::disclaimer; Dev Tools & Components Susquehanna International Group, LLP http://www.sig.com ________________________________ IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

From: ramey@rrsd.com

Stewart, Robert wrote:

...

You need to check your vision! Seriously, others have mentioned flat_set already, but the point is that using std::sort and the other algorithms is not reusable. You must use them, and use them correctly, every time you want the behavior, and you must be sure to use them at the right time. That's the essence of the need for a library: provide a reusable component for non-trivial functionality.

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. Certainly simpler than documentation, header, tests etc required to make it a library. Any one who needs this as a package can easily make this as a 15 line header file.

Some things are just to simple and obvious to need a library.

Well, if you drop the requirement of having to work properly, I suppose anything can be written in 15 lines ;) Regards, Nate

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

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

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