C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  c++ standard library sort          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Robert Harris Guest Posted: Sat Aug 21, 2004 3:26 am    Post subject: c++ standard library sort I'm look Josuttis book - The C++ Stanard Library Page 400 (13th printing) or the source code from http://www.josuttis.com/libbook/index.html for sort2.cpp example. the part where is says: with sort() 17 2x 3x 4x 16 15 13 12 11 9xx 7xx 5xx 8xxx 14xx 1xxx 10xxx 6xxxx Linux gcc 3.3.3 outputs this, however on windows I get 2x 3x 4x 11 12 13 15 16 17 5xx 7xx 9xx 1xxx 8xxx 14xx 6xxxx 10xxx I thought it might be a problem in the book, but it worked with g++, I searched the web look for the reason why it's different, but couldn't find one. I was going to compare the sort source from windows and gcc, but thought I ask first. thanks [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Bo Persson Guest Posted: Sat Aug 21, 2004 4:06 pm    Post subject: Re: c++ standard library sort "Robert Harris" <robertdharris (AT) hotmail (DOT) com> skrev i meddelandet news:b28bf1dc.0408200720.2cf8b342 (AT) posting (DOT) google.com... Quote: I'm look Josuttis book - The C++ Stanard Library Page 400 (13th printing) or the source code from http://www.josuttis.com/libbook/index.html for sort2.cpp example. the part where is says: with sort() 17 2x 3x 4x 16 15 13 12 11 9xx 7xx 5xx 8xxx 14xx 1xxx 10xxx 6xxxx Linux gcc 3.3.3 outputs this, however on windows I get 2x 3x 4x 11 12 13 15 16 17 5xx 7xx 9xx 1xxx 8xxx 14xx 6xxxx 10xxx I thought it might be a problem in the book, but it worked with g++, I searched the web look for the reason why it's different, but couldn't find one. This is exactly what the example is supposed to show: std::stable_sort preserves the initial order of elements that compare equal (in this case, elements of the same length). std::sort does not have this requirement, so it might possibly run faster. Note that both sequences have their elements in the order length==2, 3, 4 ,5 There is no problem - both results are correct! Bo Persson [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Daniel R. James Guest Posted: Sat Aug 21, 2004 4:07 pm    Post subject: Re: c++ standard library sort [email]robertdharris (AT) hotmail (DOT) com[/email] (Robert Harris) wrote in message news:<b28bf1dc.0408200720.2cf8b342 (AT) posting (DOT) google.com>... Quote: with sort() 17 2x 3x 4x 16 15 13 12 11 9xx 7xx 5xx 8xxx 14xx 1xxx 10xxx 6xxxx Linux gcc 3.3.3 outputs this, however on windows I get 2x 3x 4x 11 12 13 15 16 17 5xx 7xx 9xx 1xxx 8xxx 14xx 6xxxx 10xxx I thought it might be a problem in the book, but it worked with g++, Both results are correct, which is the point of the example. With sort(), the order of elements which are considered equal by the sort criteria (in the example, strings with equal length) is not guaranteed, so you can get different results with different libraries. Note that even though the two results are different, both are correctly ordered by length. The ouput from stable_sort() is always the same - the order of equal elements is preserved. Your Windows library seems to have done this for sort() as well, but you shouldn't rely on that. Daniel [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top John Potter Guest Posted: Sun Aug 22, 2004 3:12 am    Post subject: Re: c++ standard library sort On 20 Aug 2004 23:26:12 -0400, [email]robertdharris (AT) hotmail (DOT) com[/email] (Robert Harris) wrote: Quote: the part where is says: with sort() 17 2x 3x 4x 16 15 13 12 11 9xx 7xx 5xx 8xxx 14xx 1xxx 10xxx 6xxxx Linux gcc 3.3.3 outputs this, however on windows I get 2x 3x 4x 11 12 13 15 16 17 5xx 7xx 9xx 1xxx 8xxx 14xx 6xxxx 10xxx Which matches the result with stable_sort for both, I assume. Since sort is not required to be stable, both results are valid. You are sorting by length of string only. Any permutation which has all length2, all length3, all length4, all length5 is valid. Note that an implementation of sort may call stable_sort. That may be the case for the library you are using with sone compiler on windows. John [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top M Jared Finder Guest Posted: Sun Aug 22, 2004 3:13 am    Post subject: Re: c++ standard library sort Robert Harris wrote: Quote: I'm look Josuttis book - The C++ Stanard Library Page 400 (13th printing) or the source code from http://www.josuttis.com/libbook/index.html for sort2.cpp example. For people who do not have /The C++ Standard Library/, the page in section is an example where the collection 1xxx 2x 3x 4x 5xx 6xxxx 7xx 8xxx 9xx 10xxx 11 12 13 14xx 15 16 17 is being sorted according to string length. Quote: the part where is says: with sort() 17 2x 3x 4x 16 15 13 12 11 9xx 7xx 5xx 8xxx 14xx 1xxx 10xxx 6xxxx Linux gcc 3.3.3 outputs this, however on windows I get What compiler under Windows? GCC? Microsoft C++? Something else? Quote: 2x 3x 4x 11 12 13 15 16 17 5xx 7xx 9xx 1xxx 8xxx 14xx 6xxxx 10xxx I thought it might be a problem in the book, but it worked with g++, I searched the web look for the reason why it's different, but couldn't find one. I was going to compare the sort source from windows and gcc, but thought I ask first. This isn't a problem with the book or with either compiler, but with the differences between a stable sort and an unstable sort. You should have noticed that stable_sort() produced the same output under GCC and whatever compiler you used in Windows. This is because a stable_sort() has a stronger guarantee than sort() -- In addition to the elements being sorted such that collection[i] <= collection[i + 1], elements that are equal must appear in the same order they appeared in the original container. sort() has no such restriction, so elements that are equal are allowed to appear in any order relative to each other. 11 12 13 15 16 17 2x 3x 4x 9xx 7xx 5xx 8xxx 14xx 1xxx 10xxx 6xxxx 4x 3x 2x 17 16 15 13 12 11 9xx 7xx 5xx 8xxx 14xx 1xxx 10xxx 6xxxx would also both be legal results after sort. -- MJF [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top news Guest Posted: Sun Aug 22, 2004 3:16 am    Post subject: Re: c++ standard library sort "Robert Harris" <robertdharris (AT) hotmail (DOT) com> wrote in message Quote: one. I was going to compare the sort source from windows and gcc, but thought I ask first. Which output line are you talking about. If you're talking about the first one (sort()) the fact that there is a difference between the two implementations just demonstrates the point he is trying to make. With an "unstable" sort, there is no preservation of the order of equivalent comparison values. The second stable line MUST be the same between the two implementations if they are working correctly (because the ambiguity of the order of equivalent items must be preserved from the input). -Ron [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.