I have tried looking for it on my own but I am unable to find it. Can anyone link me to or post the source code of std::sort?
Printable View
I have tried looking for it on my own but I am unable to find it. Can anyone link me to or post the source code of std::sort?
The source code will vary from implementation to implementation, the only thing that is guaranteed is that the complexity should be O(n log n).
sort (C++) - Wikipedia, the free encyclopedia
The wiki linked in post #2 does point to one implementation if you just want to see an example, though.
My bad, how about the GNU version? I know wikipedia mentions the algorithms used but I just really wanna see the code in the flesh.
As I said, check Wiki's references; it actually points to the GNU std::sort implementation.
So start by downloading gcc source code and looking through it...
Lol if I was on Linux, where would that be? /usr/lib/algorithm? I am on my Nook at the moment.
For visual studio, it's in ...\include\algorithm in the program file directory for visual studio. For VS2005, it's a bit past 1/2 into the file.
The definition of std::sort() will be found via the header <algorithm> for a lot of implementations (aka compilers/library/head file bundle) since std::sort() is a template.
Since implementations often can't compile templates without the template definition inline, there is a pretty good chance the source for std::sort() will be in the header file <algorithm>, or some file #include'd by that header.
Whether the source code is useful, that's another question. There is no requirement that the definition of standard library functions be portable between compilers.
O_oQuote:
Can anyone link me to or post the source code of std::sort?
Why do you want the source for `std::sort' in particular?
Soma
phantom, I've been reading Addison and Wesley's Accelerated C++ book and I'm doing the student grading assignment and they used the sort() function. It seems to work pretty well and I was just curious how the pros would sort something out.
I think it's fascinating that they took a hybrid approach, using introsort into insertion sort. I've been reading up on introsort and it's definitely something that I didn't code when I was taking underdivision CS. If anything, I think all we did was the basics. I think we did insertion sort, Idk. The only thing I really remember from that class was using a doubly linked list to make a text editor and then making a dictionary/spell-checker using a hashing algorithm which I thought was so cool because during development, I wrote a non-hash version and then a hash version and wow, the speed-up time was absolutely astounding.
That being said, I'm always interested in algorithms and I wanted to see what true C++ looked like and holy poop, it is so confusing. I mean, wow. I'm gonna look at it some more and then post back with all the questions I have. I also figure that this is a fantastic way to learn advanced C++ and extend my knowledge of algorithms. I really do wanna code for a living someday and this is something that I feel will help me get there and even if it doesn't, it's really fun to learn. :)
Another idea:
Create a program with only a single sort statement (and required lines to get it to compile), then step through the source and, at least in visual studio, you can step through std::sort.
You can even look at how it works when sorting your dummy input.
For VS2005 <algorithm>, based on the comment, sort() is // divide and conquer by quicksort.
In algorithm, sort() is the user called function. _sort() and the other functions that begin with _ are internal functions. The user called sort() has this header:
I'm not sure if you're familiar with templates. The class<...> is just use to allow generic typing for the parameters. In this case there's only one type, and microsoft / hp named it _RanIt which stands for random access iterator, which means it's some type of iterator for an array or vector of some type of element that can be compared using < (including an overloaded < operator) (otherwise the sort() with a pointer to a user specified compare function is used).Code:template<class _RanIt> inline
void sort(_RanIt _First, _RanIt _Last)
Lol I am on Linux so no VS for me but I found the file in my /include/ directory, which, ironically enough, makes a lot of sense. I have been looking at the code and will post my dissection of it here for review.