The Qsort challenge

Quote:

---

For example you may have a thread object, each has a unique thread ID, priority and all other related information. Each thread object is certainly unique so you never ever want to duplicate it at any moment. Now, the operating system need to sort these thread objects by priority. How do you do it? It must be sorted without making duplications at any given moment.

---

Sort an array of indices. Sort an array of pointers.

Quote:

---

And under this situation Qsort would work better than std::sort, because it swaps objects without actually making any copies.

---

Ridiculous. You ARE copying the object. Bit by bit. One object's data ends up in a different memory location from where it was instantiated. That data is a copy of the original object. It is NOT the original object.

Wow, deja-vu!

Quote:

---

There will be cases you are not satisfied with an indirect index array, but you want to sort the objects themselves directly.

---

If you need to make copies of the class, then the class should not be designed with copying prohibited, in which case, std::sort will work perfectly.

Quote:

---

std::sort can only sort objects that an appropriate copy operation can be carried out, and is not prohibited to carry out. Qsort does not have such limitation.

---

It is not a limitation. QSort is a poor tool because it does not respect my class design decisions.

Regards,
Bassman

Quote:

---

Originally posted by jfaust ... and must not be used on non-POD types.

---

Which is where the focus of this should be. If Mai could, at the very least, admit this, there is progress. If he fails to admit this, this is clearly evident that he believes that moving objects without calling the appropriate copy constructor is valid. We have the ANSI standards, failed QSort runs on various compilers, and the C++ experts to back us up. There is no need for further debate on this aspect -- QSort is not guaranteed to work on non-POD objects. Period.

Having said this. I'm trying to pin down exactly what is the point of QSort. Others may want to take the technical approach and debate with Mai, but this really has gone beyond technical reasons for QSort and into another realm.

Is QSort posted to one-up the ANSI standard and state that the standard is invalid? Is it to prove that Mai is better than C++ programmers who developed std::sort? Is it to show that 'C' programmers are superior to C++ programmers including Josuttis, Stroustrup, Plauger, et. al.? Is it just to plain old show off and have everyone raise Mai up on their shoulders as a "hero" or a programming "god"? Is it a combination of these things? One really has to question the possibility of psychological reasons as to why this QSort debate continues.

A reasonable man would have acknowledged that QSort didn't hold up against the standard, and would state that this can only be used for 'C' structs and not for non-trivial C++ objects. There is nothing wrong with developing 'C' code for 'C' issues. There is a big problem when you develop 'C' code for C++ issues that violate ANSI standards.

Regards,

Paul McKenzie

Hey, if nothing else, I think he improved on the times for
Microsoft's original qsort(). Granted, those were with his tests
and more comprehensive tests might find a weakness in QSort(),
but from what I've seen so far, QSort() seems to perform as well
as qsort() and sometimes better. That's great and all and I think
that was his main point with QSort() ... and then he realized that
his QSort() was faster than std::sort() too! That's where the
trouble started.

It's just like when you define a new and delete for your own
class; because you're using it for a specific example, it's going to
be faster so by all means, do it. His QSort() probably works
faster for all the times he needs it, but I'm guessing that there
will be some instances where it's slower than qsort(). Sometimes
you have to pick the generic approach to make things easier,
even if there are some tradeoffs. That's why it's good to have the
skills to know where and how to make performance increases if
you need to. Kudos to you for that, Mai ... but I have to agree
with the rest and say that QSort() probably isn't as useful for
sorting non-POD data types....

--Paul

Paul Wendt, you are right, his Qsort is much better than the qsort that comes with MSVC. But std::sort uses introsort, which is even better, as I've "shown" in Philip's thread for sorting doubles.

I think the important point of this discussion is that copy constructors (or assignments) can be costly, so avoid them. It's not an "inherent flaw" in std::sort that it uses copy constructors, but it's a decision.

The point that using std::sort for sorting the types of classes that Mai used in his example is extremely slow is entirely valid. I don't think that qsort or Qsort is the answer though, but rather sorting an array of pointers. This is a very important point that many STL beginners (including me ;) ) get wrong. If your classes are non-trivial than it's much better to put pointers to them inside the container rather than the full class. As an added benefit you will be able to use polymorphism on them.

Quote:

---

Originally posted by Paul McKenzie
I'm trying to pin down exactly what is the point of QSort.

---

Well, I think it's just a starting point for argument. I give Anthony enough credit that I don't think even he'd use the thing.

Jeff

Yves, I think your summary is the most reasoned I've heard yet on this issue. I know how easy it is to get lost in the frustration (I've already been warned once about that myself, and I've only been around a few months), but you have made the most important point about this whole discussion. Time-wise, the program does not compare with std::sort, which is the point of it (as I follow the conversation), as an order of complexity issue. And as to the point used for creating it in the first place (which I take to be avoiding the copy calls -- assignment and ctor), the whole c++ world would agree that pointers (or some smarter indirection, as one's tastes go) is the proper idiom that they even teach in many college courses and standard books on data structure management!

Not that I disagree with the more passionate stands. I love a good fight. But I wanted to thank Yves for the clarity in the mist...

Look! It's a bird; it's a plane! It's Super Moderator!

Hi to All!
I want to add some notes to Yves reply.
Really, the estimation of any sorting algorithm on any concrete sequence always normally based on :
- count of made comparisons operations;
- count of made swapping operations.
So, time of working the some sorting algorithm on some sequence is based on these two counts and how effective you realize the compare and exchange operations :) (that's why, of course, if you want to sort the sequence of object with significant size - better build its index array and sort it :)).
By the way, why the most people so like quick-sort algorithm? Statistically, it's not the best algoritms, at least it lose to heap-sort, for example (under "better" or "worther" I mean the estimation as I said before - based on counts of operation made during working).

regards, SD

Two quick comments...

1) AnthonyMai's statement....

"Basically std::sort is broken whenever you have some class where appropriate copy constructors can not be written."

If you mean the compiler can not write them the point is meaningless. good design requires the 5 "auto" functions should ALWAYS be implemented for EVERY class. If the statement was meant that a programmer could not write a copy constructor for a class, I would surely like to see a sample.

2)Gabriel's Sample...

It has been stated that this implementation is "poor" because an invalid object can be copied and become value. A quick tweak (also for the assignment operator)

SomeClass(const SomeClass& src)
{
if (src.self_ != src)
throw "someException"
}
self_=this; val_=src.val_;
}

takes care of the problem. Of course Gabriel may have INTENDED to write a self repairing class. On a more serious note, I have found tht is is ALMOST always better to implement both the copy constructor and assignment operator in terms of a comment protected/private utility method, the same goes for (= and !=) (> and <).

Quote:

---

Originally posted by TheCPUWizard
...
good design requires the 5 "auto" functions should ALWAYS be implemented for EVERY class.
...

---

What are the 5 "auto" functions? contructor, destructor, copy, assignment, ???

Thanks,
John Flegert

Quote:

---

Originally posted by TheCPUWizard
2)Gabriel's Sample...

It has been stated that this implementation is "poor" because an invalid object can be copied and become value. A quick tweak (also for the assignment operator)


takes care of the problem. Of course Gabriel may have INTENDED to write a self repairing class.

---

I was asked to write a class that breaks Qsort but works with std::sort. My point was to demonstrate the existence of such a class -- and not to demonstrate good style, good taste or the usefulness of such a class.

John,

The last one is the equality operator [==].

Gabriel,

I was NOT intending to knock your sample in ANY way. You provided exactly what was asked for (a class that would break qsort). My comments were directed more at those who were implying that there was something wrong with your class and that is WHY it would break QSort. The tweaks I added would enhance your class so that it would be beyond these criticisms.


David.

Quote:

---

Originally posted by TheCPUWizard
Two quick comments...

...
good design requires the 5 "auto" functions should ALWAYS be implemented for EVERY class.
...

---

I would disagree with this. Why implement any of the 5 "auto" functions if they are not meant to be used or if the default implementation is sufficient?

Thanks,
John Flegert

John, My reasoning for implementing all 5 is simple. It is my experience [10 years C++ development] that it is easier in the long run. Why?

1) When setting policy to get consistent results from a team of programmers a fixed policy which does not involve "judgment calls" is easier to define, implement and maintain.

2) Any class which contains a pointer (almost) always need custom a copy constructor and assignment operator. Those which want to have the same pointer value should be explicitly documented in any case.

3) Any class which does internal reference counting, needs a copy constructor.

4) A class that today does not "need" a copy constructor will often be "upgraded" to contain a new data member that requires a copy constructor. As a (contrived example), consider a class with starts with 5 data members all built-in non-pointer types. This does not need a copy constructor or assignment operator to behave correctly. Over time additional members are added, they are all either build in types or well behaved classes, this goes on until there are 50 data members. THEN IT HAPPENS, a pointer data member is required. At this point the copy constructor and assignment operator are needed. The programmer now has to write the code for alll 51 members!!!!. Much better to amortize the cost (time) since day 1. It is hard to justify (to boss or client) why addding one "little pointer" requires a week of testing to insure that all 50 of the other members are being properly copied!!!.

5) Some classes which consist of just built in types and well behaved classes STILL require a (user written)copy constructor. Consider a simple object that counts the number of times a certain method has been called FOR THAT INSTANCE. This is often the type of item added for debugging and code coverage testing. Should a copy constructor be written (again having to implement and test ALL of the members) when this is added and then deleted when this is removed????

6) Many programmers never intend for their objects to be copied or assigned. They just dont think about it. If you REQUIRE them to write these functions, they must think. Either write a valid public method, or write an empty private method (explicitly stating that "you cant to this").


The above covered mainly the copy constructor and assignment operator....

Default Constructor : All members should ALWAYS be initialized so this is required.

Equality operator : A great many classes contain private data members that are not pertinent to equality testing [lazy evaluation patterns, item #5 above, etc.)

In short liefe is EASIER for everybody (in the long run) if these routines are ALWAYS implemented.


David.