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

Printable View

- 09-23-2007matsp
- 09-23-2007VirtualAce
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. - 09-23-2007robatino
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 - 09-23-2007laserlightQuote:

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.

- 09-23-2007robatino
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?

- 09-23-2007laserlightQuote:

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.

Quote:

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.

Quote:

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?