Yes, it is technically impossible to teach things you don't know, right? This does, of course, not make the teacher any more right.Originally Posted by swgh
--
Mats
Yes, it is technically impossible to teach things you don't know, right? This does, of course, not make the teacher any more right.
--
Mats
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
The problem here is that you will be 'programming' your brain to use incorrect programming practices. It is very hard to remove that bad programming at will and so I would not mess with the class. Your best bet may be to wait until a different teacher teaches it or buy a good book on C++ programming and go from there.
I highly recommend The C++ Programming Language by Bjarne Stroustrup. I have about 7 different books on C++ and Bjarne's by far takes C++ to the next level far beyond what the other books show. Bjarne's book explains everything about the language and you can be sure that what is mentioned in the book is accurate and standardized. Some say the book is difficult to read and understand but I've had no issues with it.
Last edited by VirtualAce; 09-23-2007 at 02:09 PM.
There are a few minor issues with Stroustrup's book that I've noticed, but they're probably covered in a short errata list somewhere. One is that he talks about the export keyword without mentioning that very few compilers actually implement it, so in practice you end up putting whole template definitions in header files, not just the declarations. To be fair, this was written in 1997, and he apparently thought it would be implemented soon. He also says that the worst-case performance of sort() is O(N*N), which was true at the time, but shortly after the implementation was changed from quicksort to introsort which is O(N*log(N)) worst-case.
http://www.sgi.com/tech/stl/sort.html
From what I see the C++ standard only mandates a N log N comparisons in the average case, so perhaps the choice of introsort over the other O(n log n) sorts is implementation specific, and thus an O(n*n) worst case would be acceptable.He also says that the worst-case performance of sort() is O(N*N), which was true at the time, but shortly after the implementation was changed from quicksort to introsort which is O(N*log(N)) worst-case.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
I hope this will be changed in C++09. According to the link, introsort is at least as fast as quicksort on average, so it shouldn't cost anything to make the stronger guarantee - and one can always take any fast average-case algorithm and turn it into a hybrid with something like mergesort to also get O(n log n) worst-case. I have code with several stages including a sort operation, none of the others being worse than O(n log n) worst-case, and if I can't count on the sorting to be the same, it throws a wrench into the works. There must be others in the same boat. Stroustrup does say that stable_sort() is supposed to be O(n log n) worst-case (with sufficient memory) - do you know if the current standard guarantees that?
If I remember correctly, introsort is precisely such a hybrid, being a variant of quick sort that switches to heap sort if a possible worst case is detected.According to the link, introsort is at least as fast as quicksort on average, so it shouldn't cost anything to make the stronger guarantee - and one can always take any fast average-case algorithm and turn it into a hybrid with something like mergesort to also get O(n log n) worst-case.
I suppose there is the option of make_heap() followed by sort_heap(), if you really want to guarantee average and worst case of O(n log n) regardless of whether there is sufficient additional memory.I have code with several stages including a sort operation, none of the others being worse than O(n log n) worst-case, and if I can't count on the sorting to be the same, it throws a wrench into the works.
Yes, but then merge sort is the obvious choice for stable_sort()Stroustrup does say that stable_sort() is supposed to be O(n log n) worst-case (with sufficient memory) - do you know if the current standard guarantees that?
Look up a C++ Reference and learn How To Ask Questions The Smart Way
