comp.lang.c++.moderated removed, doesn't everyone that read that read clc++ also?
Donovan Rebbechi wrote: > Another place where I wouldn't use vector is to implement large matrices. > In this case, memory waste is the main concern.
Exactly; that's the sort of thing that valarray is perfect for. Especially when combined with the power of slice and gslice, well, it's really slick and only as much overhead as a single vector (if that)...
> > doesn't know them for my special, optimized class. (This isn't 100% > > true; valarray is standard, but neither I nor any of my collegues have > > ever used one:-).)
> valarray is a fairly specialised class, it's not a general purpose, unlike > <vector>
valarray, in my experience, can trivially be used as a fixed-size vector. Reinventing the wheel doesn't save time for anyone. :)
-tom!
-- Tom Plunket to...@fancy.org PlayStation2/3D Studio geek
Few people realize that pieces of coral, when painted brown and attached to the skull with wood screws, can make a child look like a deer.
Gerry Quinn wrote: > A strategy game with a map based on vectors could end up suffering > badly from slow pathfinding, if the classes are inefficient.
What if the map was based on some other structure and the classes were inefficient? What if the map was based on vectors but the classes were terribly efficient?
> It could also cause problems during development in debug mode, > even if a lot of function calls are optimised out in the release > version.
MFC might cause problems during development in debug mode, but the Standard Library acts exactly the same way.
> I know this from painful experience with the MFC CArray > collection class in the game I'm working on now. Not STL, but > the same considerations would apply.
If we all agreed that the Standard Library were the same sort of crap that MS is peddling as "Foundation Classes," you're right. We'd be in trouble. Fortunately, we aren't. :)
-tom!
-- Tom Plunket to...@fancy.org PlayStation2/3D Studio geek
Few people realize that pieces of coral, when painted brown and attached to the skull with wood screws, can make a child look like a deer.
John Potter wrote: > The guarantee that makes sense is stable. That means that equal items > retain their relative order after sorting. See stable_sort and > list::sort. Remember that the order relation used for sorting by a > key field induces an equivalence relation which need not be the > equivalence relation (operator==) for the items.
If they have a "relative order" then they aren't equal.
DS
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
Mike Wahler wrote: > > There is no guarantee one could possibly make in that case. If they > > compare equal, they are indisinguishable. Give me an example of what > > might be a guarantee that would make sense. > The comparison might be against a struct member, the > other members of which might be 'unequal', moving > data that perhaps wasn't meant to be moved.
First of all, your comparison function compares the structures, not "a struct member". If two objects are unequal and you returned an equal indication from your comparison function, then your comparison function is broken.
If two structures are not equal and your comparison function says they are equal, you are lying to the sorter. If they really are equal, they are indistinguishable, and there's no difference whether you move one or not.
DS
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
> > We often compare complex objects for equality on the basis of a single > > attribute
> This is inappropriate if you want a stable sort. So if you want a > stable sort, don't do that.
I would say, if you want a stable sort, use a stable sorting algorithm. There are sorts that by their very nature provide stability. When using such a sort, you can rely on this property, and it is often easier to formulate the comparison predicate. This is not a minus.
If you insist on using an unstable sort, this is your choice. This is fine, and may be a choice that I might make similarly. You have to weigh the pros and cons of a perhaps less than ideal (but often asymptotically comparable) sort with a potentially ugly comparison function (especially if there's nothing in the object that indicates its relative ordering in the list). There are pros and cons, and weighing these is part of any software engineer's job.
Just like many other types of algorithms, sorting algorithms have mathematical properties that when using them you can count on. Examples of such properties are: expected time complexity, worst case time complexity, expected/worst case number of exchanges/moves/compares, stability, etc. You choose an algorithm that has the properties that your design calls for. (This is as true for sorting as it is for any other class of algorithms.) Or, in the case of the language standard, you chose the algorithm or function that provides the guarantees that your design calls for. You can either design so that stability is not an issue, or you can choose an algorithm/function where stability is guaranteed.
Perhaps I don't understand your objection to stability.
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
In article <3C3FC979.D5E69...@webmaster.com>, David Schwartz wrote: > Adam Peterson wrote: > Another way to do this is to write the comparison function
correctly.
What do you mean by "correctly" ? There's nothing "incorrect" about an order that cannot distinguish between all elements of a given set. Not only does your definition of "correct" make little sense, it's also not terribly useful. To require this makes code more confusing, because it obscures intent (maybe I only *want* to sort by name, and simply don't care about other fields), and forces the code to do more work.
> I think it's elegant that if you never want to consider two objects > as equal, you never compare them as equal.
The notion of "compare them as equal" is bogus, and it appears that you are using loaded language upfront to jump to your conclusion (that "all orders should be anti-symmetric"). They are not "compared as equal", they are merely indistinguishable to the chosen order.
The property of anti-symmetry is certainly useful in some settings (indeed, it's part of the definition of a partial order), but it is not necessary to perform a sort, or even a stable sort.
-- Donovan
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
In article <3C408D55.A678D...@webmaster.com>, David Schwartz wrote: > Pete Becker wrote: >> A stable sort is one in which elements that compare equal in the sort >> come out in the same relative order after the sort as they were before >> it. For elements like ints this doesn't matter. For more complex types >> it makes a difference, because elements that differ can still compare >> equal for purposes of sorting. E-mail programs, for example, should use >> stable sorts. That way you can sort by date, then sort by name, and >> messages from the same person will be in order by date.
> I think you're missing my point. If you want a stable sort, then when > you might return equal,
Again, this notion of "return equal" only makes sense if you assume anti-symmetry. Since the merits of anti-symmetry are the topic of discussion, your persistent use of this misleading terminology strikes me as a transparent attempt to manipulate the debate with linguistic sophistry.
Why you consider it necessary that all comparisons be anti-symmetric escapes reason.
> return a value based upon which is currently > before the other.
But that's an intrusive design, because it requires the class designer to "build in" an order parameter.
> There should be no such thing as "elements that compare equal" in a
There is no such thing as "elements that compare equal", unless you have an anti-symmetric comparison.
-- Donovan
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
In article <3C408E1C.CF364...@webmaster.com>, David Schwartz wrote: > Francis Glassborow wrote: > You are assuming the existence of a comparison function and you are > assuming that the comparison function doesn't have the semantics you > need.
It's a hypothetical. He's allowed to assume that.
> So you make the sort function more complex to work around the > limitations of a comparison function that exists only because you > assumed it. Why not assume the existence of a comparison function that > is stable and a that way you can have a faster, more efficient sort > because it doesn't try to provide stability to programs that don't need > it.
This is where pragmatism kicks in. The fact is that it's easier to write a generic sort function than it is to write a generic comparison function. You can't just assume comparison functions into existence, they need to be written on a case by case basis. In contrast, the sorting algorithm only needs to be implemented once. It simply makes more sense to put *more* work into the code that is more likely to be reused.
>> We often compare complex objects for equality on the basis of a single >> attribute
> This is inappropriate if you want a stable sort. So if you want a > stable sort, don't do that.
It's easier to do it that way. That in itself strikes me as being a perfectly good reason to do that.
> I would not describe two different records as "comparing equal" unless > I considered them interchangeable. This is a very bad choice of > language.
This I agree with.
-- Donovan
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
> > > There is no guarantee one could possibly make in that case. If they > > > compare equal, they are indisinguishable. Give me an example of what > > > might be a guarantee that would make sense.
> > A stable sort is one in which elements that compare equal in the sort > > come out in the same relative order after the sort as they were before > > it. For elements like ints this doesn't matter. For more complex types > > it makes a difference, because elements that differ can still compare > > equal for purposes of sorting. E-mail programs, for example, should use > > stable sorts. That way you can sort by date, then sort by name, and > > messages from the same person will be in order by date.
> I think you're missing my point. If you want a stable sort, then when > you might return equal, return a value based upon which is currently > before the other.
That wouldn't prevent a non-stable sort from getting the elements out of order. Take a typical quicksort that uses "median of three" to determine the pivot. The implementation looks at the first, last, and middle elements, and chooses the median of the three for the pivot. It then swaps this median element with the last element. Now, suppose the first two elements before the sort had been equal on the sort key. Let's call the two elements A and B respctively. Before the sort they are in order "AB". Suppose the first pivot chosen is the first element. After swapping with the last element, the relative order of these two elements is "BA". Your comparison algorithm would not have changed the result.
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
David Schwartz wrote: > You are assuming the existence of a comparison function and you are > assuming that the comparison function doesn't have the semantics you > need. So you make the sort function more complex to work around the > limitations of a comparison function that exists only because you > assumed it. Why not assume the existence of a comparison function that > is stable and a that way you can have a faster, more efficient sort > because it doesn't try to provide stability to programs that don't need > it.
Why not? What is equality? What does it mean to sort things?
Maybe what it means to sort names in the phone book is to sort them based on Last Name, First Name. That two names compare equal does not imply that the records are themselves equivalent, it just means that in the sort that you are currently doing that the order of the two (or more) items that compare equal is indeterminant.
It just seems naive to me to say, "why would you ever need that?" Who cares if *you* can see a need for something? The fact remains that other people have perfectly valid reasons for wanting something, and often coming up with a comparison function to guarantee stability is considerably more work (for the programmer and the computer) than just having an easy comparison function and knowing that the sort algorithm is stable.
> > We often compare complex objects for equality on the basis of a > > single attribute
> This is inappropriate if you want a stable sort. So if > you want a stable sort, don't do that.
Oh, the words came down from on high, they must be true!
> I would not describe two different records as "comparing > equal" unless I considered them interchangeable.
You'd be correct in that statement. Where you are wholly off target is by asserting that people shouldn't ever need some facility that has been researched and used for many years simply because it doesn't live up to some golden standards. Hey- I live in the real world. If I come up to legacy data and need to write software to do a sort, and if I need the sort to be stable but there's nothing in the record data that I can use to guarantee that during the sort stability is maintained, I'm not going to tell the client that I won't work on the problem- I'll just whip up a solution using the tools at my disposal.
-tom!
-- Tom Plunket to...@fancy.org PlayStation2/3D Studio geek
Few people realize that pieces of coral, when painted brown and attached to the skull with wood screws, can make a child look like a deer.
David Schwartz wrote: > There should be no such thing as "elements that compare > equal" in a stable sort. In a stable sort, no two elements are > ever equal.
Ahh- now you understand. Good show. I'm glad that "the point" of stable sorts is now fully understood.
-tom!
-- Tom Plunket to...@fancy.org PlayStation2/3D Studio geek
Few people realize that pieces of coral, when painted brown and attached to the skull with wood screws, can make a child look like a deer.
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
In article <3C408C75.AB76E...@webmaster.com>, David Schwartz wrote: > John Potter wrote:
>> The guarantee that makes sense is stable. That means that equal items >> retain their relative order after sorting. See stable_sort and >> list::sort. Remember that the order relation used for sorting by a >> key field induces an equivalence relation which need not be the >> equivalence relation (operator==) for the items.
> If they have a "relative order" then they aren't equal.
Relative order is a property of the state of the container, not the items it contains.
-- Donovan
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
In article <3C408CEB.ED14A...@webmaster.com>, David Schwartz wrote: > Mike Wahler wrote:
>> > There is no guarantee one could possibly make in that case. If they >> > compare equal, they are indisinguishable. Give me an example of what >> > might be a guarantee that would make sense.
>> The comparison might be against a struct member, the >> other members of which might be 'unequal', moving >> data that perhaps wasn't meant to be moved.
> First of all, your comparison function compares the structures, not "a > struct member". If two objects are unequal and you returned an equal > indication from your comparison function, then your comparison function > is broken.
It is not broken. You assume without justification that all comparisons must be antisymmetric.
Here, I will attempt to explain why I think we should allow asymmetry.
> If two structures are not equal and your comparison function says they > are equal, you are lying to the sorter.
No you are not. The sorter does not require the comparison function to decide whether two elements are equal.
Here is a practical reason why one might want stable sorts.
Suppose you have a structure with several fields, say 10. I can write 10 comparison operators, for example:
in fact if I'm smart about it, I could use mem_fun_ref to get comparisons with any fields (if it's a class)
template <class obj, class member_function> struct compare_field { ..... }
and client code can then easily sort by any criteria.
But to do it your way, you would need to write 10 factorial different comparisons, and each of those would be 10 times as long.
The advantage of separating these sorts is that when you take the stable approach, you are factoring code into operations that are in a sense more atomic. This leads to functions that have a clearer purpose (ie don't try to do too much), and it offers more flexibility. For example, my way, I could sort be age and weight, age only, or height, then weight, then age without doing any more than calling sort functions in different orders.
-- Donovan
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
Homer Meyer wrote: > That wouldn't prevent a non-stable sort from getting the elements out of > order. Take a typical quicksort that uses "median of three" to determine > the pivot. The implementation looks at the first, last, and middle > elements, and chooses the median of the three for the pivot. It then swaps > this median element with the last element. Now, suppose the first two > elements before the sort had been equal on the sort key. Let's call the two > elements A and B respctively. Before the sort they are in order "AB". > Suppose the first pivot chosen is the first element. After swapping with > the last element, the relative order of these two elements is "BA". Your > comparison algorithm would not have changed the result.
There's the point that demolishes my argument! Thank you. I now see the error of my ways.
One could, hypothetically, write a comparison function that, where it would normally return equal will return which one came first before the sort began. But that is definitely too much work to expect in a comparison function.
I still think that if you're only going to have one sort function built generically, it should be a non-stable sort. Stability is not required often enough to justify the overhead. Of course, if you can make a sort stable without compromising performance, then you certainly should.
DS
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
> > It has one other potentially fatal flaw, it is not a stable sort (i.e. > > it makes no guarantees as to the ordering of elements that compare > > equal).
> There is no guarantee one could possibly make in that case. If they > compare equal, they are indisinguishable. Give me an example of what > might be a guarantee that would make sense.
That their relative order within the container is not changed by the sort. If A is equivalent to B and if A preceeded B before the sort, A must preceed B after the sort. That is what is meant by a stable sort.
You're still overlooking the fact that the comparison being performed may not examine the entirety of the objects being compared - it may examine only a single field.
struct person { std::string m_name; long m_birthdate;
> Nonetheless, the basic fact of the matter is that to know you're > choosing the ideal pivot, the collection has to already be sorted.
Technically, this is not quite true. To know you're choosing the ideal pivot, you have to have some information about the ordering of the data in the container that allows you to locate the ideal pivot. Likewise, to know you're choosing a "reasonable" pivot, you have to have some information that allows you to guarantee that you always pick a reasonable pivot.
Pragmatically, however, you can almost never get such information unless the collection is already sorted or nearly so. Other distributions that grant such guarantees are almost never encountered, and almost purely of academic interest.
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
Carl Daniel wrote: > > > It has one other potentially fatal flaw, it is not a stable sort (i.e. > > > it makes no guarantees as to the ordering of elements that compare > > > equal). > > There is no guarantee one could possibly make in that case. If they > > compare equal, they are indisinguishable. Give me an example of what > > might be a guarantee that would make sense. > That their relative order within the container is not changed by the sort.
If they have a "relative order within the container" then they are not equivalent and so should not compare equivalent.
> You're still overlooking the fact that the comparison being performed may > not examine the entirety of the objects being compared - it may examine only > a single field.
If that's so, and you want a stable sort, your comparison is broken. However, this argument is now academic.
> I still think that if you're only going to have one sort function built > generically, it should be a non-stable sort. Stability is not required > often enough to justify the overhead. Of course, if you can make a sort > stable without compromising performance, then you certainly should.
I would probably agree with this. Those that care about stability can always implement their own sort from any number of known good stable sorting algorithms available. This allows those who need fewer guarantees to potentially have no impairment on performance, where the hit would only occur to those who need it.
However, I think the C++ standard made the correct choice in providing both functions. Note that if the best known sort also happens to be stable, a vendor can simply implement sort inline in terms of stable sort. Thus we are provided with both speed and flexibility.
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
In article <3C40FC70.2CD68...@webmaster.com>, David Schwartz <dav...@webmaster.com> wrote: >Carl Daniel wrote:
>> > > It has one other potentially fatal flaw, it is not a stable sort (i.e. >> > > it makes no guarantees as to the ordering of elements that compare >> > > equal).
>> > There is no guarantee one could possibly make in that case. If they >> > compare equal, they are indisinguishable. Give me an example of what >> > might be a guarantee that would make sense.
>> That their relative order within the container is not changed by the sort.
> If they have a "relative order within the container" then they are not >equivalent and so should not compare equivalent.
A sort algorithm requiring an explicit comparison function that returns a result based on the order before the sort would be quite useless in most situations, irrespective of whether this comparison allowed it to achieve stability.
In article <c6c14u0ig7us1jhqk291j1r01b8i277...@4ax.com>, Tom Plunket <to...@fancy.org> wrote: >Gerry Quinn wrote:
>> A strategy game with a map based on vectors could end up suffering >> badly from slow pathfinding, if the classes are inefficient.
>What if the map was based on some other structure and the classes >were inefficient? What if the map was based on vectors but the >classes were terribly efficient?
What, indeed. Then something other than Fast STL would make a difference, and we would be discussing it in a different thread.
>> It could also cause problems during development in debug mode, >> even if a lot of function calls are optimised out in the release >> version.
>MFC might cause problems during development in debug mode, but >the Standard Library acts exactly the same way.
The STL runs almost as fast in debug mode as in release mode? The 'problem' I alluded to is that debug mode was over twenty times slower than release. I could have lived with the usual factor of 2 or 3.
My guess is that STL would have been no better, and that this is a generic vectors thing.
>> I know this from painful experience with the MFC CArray >> collection class in the game I'm working on now. Not STL, but >> the same considerations would apply.
>If we all agreed that the Standard Library were the same sort of >crap that MS is peddling as "Foundation Classes," you're right. >We'd be in trouble. Fortunately, we aren't. :)
Vectors are vectors.
Gerry Quinn -- http://bindweed.com Puzzles, Arcade, Strategy, Kaleidoscope Screensaver Download evaluation versions free - no time limits Check out our new arcade-puzzler "Bubbler"!
> > > There is no guarantee one could possibly make in that case. If they > > > compare equal, they are indisinguishable. Give me an example of what > > > might be a guarantee that would make sense.
> > A stable sort is one in which elements that compare equal in the sort > > come out in the same relative order after the sort as they were before > > it. For elements like ints this doesn't matter. For more complex types > > it makes a difference, because elements that differ can still compare > > equal for purposes of sorting. E-mail programs, for example, should use > > stable sorts. That way you can sort by date, then sort by name, and > > messages from the same person will be in order by date.
> I think you're missing my point.
Nope.
> If you want a stable sort, then when > you might return equal, return a value based upon which is currently > before the other.
Fine, if you want to build knowledge of the underlying container into a comparison function. Most folks would rather not limit comparison functions in this way, so they only have to write it once.
> > There is no guarantee one could possibly make in that case. If they > > compare equal, they are indisinguishable. Give me an example of what > > might be a guarantee that would make sense.
> The comparison might be against a struct member, the > other members of which might be 'unequal', moving > data that perhaps wasn't meant to be moved.
> -Mike
Add these other members to the sorting criteria iff they sort to be equal. It won't cost any CPU cycles, unless they are equal.
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
> The guarantee that makes sense is stable. That means that equal items > retain their relative order after sorting. See stable_sort and > list::sort. Remember that the order relation used for sorting by a > key field induces an equivalence relation which need not be the > equivalence relation (operator==) for the items.
> John
Its trivial to add this, merely put the pointer address as the last item of the sorting criteria.
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
> >Quick sort only really has problems when the data is > >already sorted or nearly sorted, right ? Is there a > >C++ version of quick sort that will be able to inline > >its code, and my comparison code ?
> Rather than trying to guess what to use why don't you benchmark the > code using qsort with a comparison function vs using std::sort with a > comparison functor?
> Tom
I could do this but you still did not answer my direct question. Does C++ have a non "C" Quick Sort() ? I am sold on the inlining of the sort and comparison function.
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
In article <q6Y%7.350520$W8.13312...@bgtnsc04-news.ops.worldnet.att.net>, Peter Olcott <olc...@worldnet.att.net> writes
>I could do this but you still did not answer my direct question. >Does C++ have a non "C" Quick Sort() ? >I am sold on the inlining of the sort and comparison function.
The answer to that is exactly the same as that for C, which does not have any guarantee as to what algorithm will be used by qsort (despite its name).
Unlike C, C++ place certain performance requirements on its various sorts (even then it does not specify the algorithm, nor should it)
-- Francis Glassborow The Seasons best wishes to you and yours. May 2002 be better for all of us than 2001 was for some.
[ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ] [ about comp.lang.c++.moderated. First time posters: do this! ]
