Source code of std::sort()?

This is a discussion on Source code of std::sort()? within the C++ Programming forums, part of the General Programming Boards category; I have tried looking for it on my own but I am unable to find it. Can anyone link me ...

  1. #1
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,206

    Source code of std::sort()?

    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?

  2. #2
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    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
    How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics.

  3. #3
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,744
    The wiki linked in post #2 does point to one implementation if you just want to see an example, though.

  4. #4
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,206
    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.

  5. #5
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,744
    As I said, check Wiki's references; it actually points to the GNU std::sort implementation.

  6. #6
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    So start by downloading gcc source code and looking through it...
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  7. #7
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,206
    Lol if I was on Linux, where would that be? /usr/lib/algorithm? I am on my Nook at the moment.

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    1,314
    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.

  9. #9
    Registered User
    Join Date
    Jun 2005
    Posts
    6,452
    Quote Originally Posted by rcgldr View Post
    For visual studio, it's in ...\include\algorithm in the program file directory for visual studio.
    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.
    Right 98% of the time, and don't care about the other 3%.

  10. #10
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by grumpy View Post
    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.
    ...or even remotely readable.
    How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics.

  11. #11
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,344
    Can anyone link me to or post the source code of std::sort?
    O_o

    Why do you want the source for `std::sort' in particular?

    Soma
    “Often out of periods of losing come the greatest strivings toward a new winning streak.” -- Fred Rogers
    “Salem Was Wrong!” -- Pedant Necromancer

  12. #12
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,206
    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.

  13. #13
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,820
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #14
    Registered User
    Join Date
    Apr 2013
    Posts
    1,314
    Quote Originally Posted by rcgldr View Post
    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.
    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:

    Code:
    template<class _RanIt> inline
        void sort(_RanIt _First, _RanIt _Last)
    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).

  15. #15
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,206
    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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. is object code the same as assembly source code?
    By c_weed in forum Tech Board
    Replies: 3
    Last Post: 01-05-2012, 06:25 PM
  2. a C++ source code..
    By Nora in forum C++ Programming
    Replies: 9
    Last Post: 12-16-2006, 05:15 AM
  3. source code
    By volk in forum Tech Board
    Replies: 6
    Last Post: 03-22-2003, 10:31 AM
  4. Help with my source code
    By duty11694 in forum C Programming
    Replies: 10
    Last Post: 11-20-2002, 12:37 PM
  5. C source code for int25 or code help
    By Unregistered in forum C Programming
    Replies: 0
    Last Post: 09-26-2001, 02:04 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21