doc/stdlibref/stable-sort.html - stdcxx - Git at Google

 <HTML>
 <HEAD>
 <TITLE>stable_sort()</TITLE>
 <LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD>
 <BODY BGCOLOR=#FFFFFF>
 <A HREF="stable-partition.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="stack-h.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library Reference Guide</B></DIV>
 <H2>stable_sort()</H2>
 <P><B>Library:</B>&nbsp;&nbsp;<A HREF="2-9.html">Algorithms</A></P>

 <PRE><HR><B><I>Function</I></B><HR></PRE>

 <UL>
 <LI><A HREF="#sec1">Local Index</A></LI>
 <LI><A HREF="#sec2">Summary</A></LI>
 <LI><A HREF="#sec3">Synopsis</A></LI>
 <LI><A HREF="#sec4">Description</A></LI>
 <LI><A HREF="#sec5">Complexity</A></LI>
 <LI><A HREF="#sec6">Example</A></LI>
 <LI><A HREF="#sec7">See Also</A></LI>
 <LI><A HREF="#sec8">Standards Conformance</A></LI>
 </UL>
 <A NAME="sec1"><H3>Local Index</H3></A>
 No Entries
 <A NAME="sec2"><H3>Summary</H3></A>
 <P>Generic algorithm for sorting collections of entities</P>
 <A NAME="sec3"><H3>Synopsis</H3></A>

 <PRE>#include &lt;algorithm&gt;

 namespace std {
   template &lt;class RandomAccessIterator&gt;
   void stable_sort(RandomAccessIterator start,
                    RandomAccessIterator finish);

   template &lt;class RandomAccessIterator, class Compare&gt;
   void stable_sort(RandomAccessIterator start,
                    RandomAccessIterator finish, Compare comp);
 }
 </PRE>
 <A NAME="sec4"><H3>Description</H3></A>
 <P>The <SAMP>stable_sort()</SAMP> algorithm sorts the elements in the range <SAMP>[start, finish)</SAMP> in ascending order. The first version of the algorithm uses <SAMP>operator&lt;()</SAMP> for the sort. The second version uses the function object <SAMP>comp.</SAMP></P>
 <P>The <SAMP>stable_sort()</SAMP> algorithm is considered stable because the relative order of equivalent elements is maintained. </P>
 <A NAME="sec5"><H3>Complexity</H3></A>
 <P><SAMP>stable_sort()</SAMP> does approximately <SAMP>N * (log(N))2</SAMP> comparisons, where <SAMP>N</SAMP> equals <SAMP>finish - start</SAMP>. The algorithm calls <SAMP>std::get_temporary_buffer&lt;&gt;()</SAMP> to obtain extra memory. If enough extra memory is available, it does at most <SAMP>N * log(N)</SAMP> comparisons (i.e., the same as <SAMP><A HREF="sort.html">sort()</A></SAMP>).</P>
 <A NAME="sec6"><H3>Example</H3></A>

 <UL><PRE>//
 //  sort.cpp
 //

 #include &lt;vector&gt;
 #include &lt;algorithm&gt;
 #include &lt;functional&gt;
 #include &lt;iostream&gt;


 struct associate
 {
     int num;
     char chr;
     associate (int n, char c) : num (n), chr (c){};
     associate () : num (0), chr ('\0'){};
 };


 inline bool operator&lt; (const associate &amp;x, const associate &amp;y)
 {
     return x.num &lt; y.num;
 }


 inline std::ostream&amp; operator&lt;&lt; (std::ostream &amp;s,
                                  const associate &amp;x)
 {
     return s &lt;&lt; '&lt;' &lt;&lt; x.num &lt;&lt; ';' &lt;&lt; x.chr &lt;&lt; '&gt;';
 }


 int main ()
 {
     const associate arr [20] = {
         associate (-4, ' '), associate (16, ' '),
         associate (17, ' '), associate (-3, 's'),
         associate (14, ' '), associate (-6, ' '),
         associate (-1, ' '), associate (-3, 't'),
         associate (23, ' '), associate (-3, 'a'),
         associate (-2, ' '), associate (-7, ' '),
         associate (-3, 'b'), associate (-8, ' '),
         associate (11, ' '), associate (-3, 'l'),
         associate (15, ' '), associate (-5, ' '),
         associate (-3, 'e'), associate (15, ' ')};

     typedef std::vector&lt;associate, std::allocator&lt;associate&gt; &gt;
             Vector;

     // Set up vectors.
     Vector v (arr, arr + sizeof arr / sizeof *arr);
     Vector v1 (sizeof arr / sizeof *arr);
     Vector v2 (sizeof arr / sizeof *arr);

     // Copy original vector to vectors #1 and #2.
     std::copy (v.begin (), v.end (), v1.begin ());
     std::copy (v.begin (), v.end (), v2.begin ());

     // Sort vector #1.
     std::sort (v1.begin (), v1.end ());

     // Stable sort vector #2.
     std::stable_sort (v2.begin (), v2.end ());

     // Display the results.
     std::cout &lt;&lt; "Original    sort      stable_sort"
               &lt;&lt; std::endl;
     for (Vector::iterator i = v.begin (), j = v1.begin (),
                           k = v2.begin ();
          i != v.end (); i++, j++, k++)
         std::cout &lt;&lt; *i &lt;&lt; "     " &lt;&lt; *j &lt;&lt; "     "
                   &lt;&lt; *k &lt;&lt; std::endl;

     return 0;
 }


 Program Output:
 </PRE></UL>
 <UL><PRE>Original    sort      stable_sort
 &lt;-4; &gt;     &lt;-8; &gt;     &lt;-8; &gt;
 &lt;16; &gt;     &lt;-7; &gt;     &lt;-7; &gt;
 &lt;17; &gt;     &lt;-6; &gt;     &lt;-6; &gt;
 &lt;-3;s&gt;     &lt;-5; &gt;     &lt;-5; &gt;
 &lt;14; &gt;     &lt;-4; &gt;     &lt;-4; &gt;
 &lt;-6; &gt;     &lt;-3;e&gt;     &lt;-3;s&gt;
 &lt;-1; &gt;     &lt;-3;s&gt;     &lt;-3;t&gt;
 &lt;-3;t&gt;     &lt;-3;l&gt;     &lt;-3;a&gt;
 &lt;23; &gt;     &lt;-3;t&gt;     &lt;-3;b&gt;
 &lt;-3;a&gt;     &lt;-3;b&gt;     &lt;-3;l&gt;
 &lt;-2; &gt;     &lt;-3;a&gt;     &lt;-3;e&gt;
 &lt;-7; &gt;     &lt;-2; &gt;     &lt;-2; &gt;
 &lt;-3;b&gt;     &lt;-1; &gt;     &lt;-1; &gt;
 &lt;-8; &gt;     &lt;11; &gt;     &lt;11; &gt;
 &lt;11; &gt;     &lt;14; &gt;     &lt;14; &gt;
 &lt;-3;l&gt;     &lt;15; &gt;     &lt;15; &gt;
 &lt;15; &gt;     &lt;15; &gt;     &lt;15; &gt;
 &lt;-5; &gt;     &lt;16; &gt;     &lt;16; &gt;
 &lt;-3;e&gt;     &lt;17; &gt;     &lt;17; &gt;
 &lt;15; &gt;     &lt;23; &gt;     &lt;23; &gt;
 </PRE></UL>
 <A NAME="sec7"><H3>See Also</H3></A>
 <P><SAMP><A HREF="sort.html">sort()</A></SAMP>, <SAMP><A HREF="partial-sort.html">partial_sort()</A></SAMP>, <SAMP><A HREF="partial-sort-copy.html">partial_sort_copy()</A></SAMP>, <SAMP><A HREF="get-temporary-buffer.html">get_temporary_buffer()</A></SAMP></P>
 <A NAME="sec8"><H3>Standards Conformance</H3></A>
 <P><I>ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.1.2</I></P>

 <BR>
 <HR>
 <A HREF="stable-partition.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="stack-h.html"><IMG SRC="images/bnext.gif" WIDTH=20 HEIGHT=21 ALT="Next file" BORDER=O></A>

 <!-- Google Analytics tracking code -->
 <script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
 </script>
 <script type="text/javascript">
     _uacct = "UA-1775151-1";
     urchinTracker();
 </script>
 <!-- end of Google Analytics tracking code -->

 </BODY>
 </HTML>
	<HTML>
	<HEAD>
	<TITLE>stable_sort()</TITLE>
	<LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD>
	<BODY BGCOLOR=#FFFFFF>
	<A HREF="stable-partition.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="stack-h.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library Reference Guide</B></DIV>
	<H2>stable_sort()</H2>
	<P><B>Library:</B>  <A HREF="2-9.html">Algorithms</A></P>

	<PRE><HR><B><I>Function</I></B><HR></PRE>

	<UL>
	<LI><A HREF="#sec1">Local Index</A></LI>
	<LI><A HREF="#sec2">Summary</A></LI>
	<LI><A HREF="#sec3">Synopsis</A></LI>
	<LI><A HREF="#sec4">Description</A></LI>
	<LI><A HREF="#sec5">Complexity</A></LI>
	<LI><A HREF="#sec6">Example</A></LI>
	<LI><A HREF="#sec7">See Also</A></LI>
	<LI><A HREF="#sec8">Standards Conformance</A></LI>
	</UL>
	<A NAME="sec1"><H3>Local Index</H3></A>
	No Entries
	<A NAME="sec2"><H3>Summary</H3></A>
	<P>Generic algorithm for sorting collections of entities</P>
	<A NAME="sec3"><H3>Synopsis</H3></A>

	<PRE>#include <algorithm>

	namespace std {
	template <class RandomAccessIterator>
	void stable_sort(RandomAccessIterator start,
	RandomAccessIterator finish);

	template <class RandomAccessIterator, class Compare>
	void stable_sort(RandomAccessIterator start,
	RandomAccessIterator finish, Compare comp);
	}
	</PRE>
	<A NAME="sec4"><H3>Description</H3></A>
	<P>The <SAMP>stable_sort()</SAMP> algorithm sorts the elements in the range <SAMP>[start, finish)</SAMP> in ascending order. The first version of the algorithm uses <SAMP>operator<()</SAMP> for the sort. The second version uses the function object <SAMP>comp.</SAMP></P>
	<P>The <SAMP>stable_sort()</SAMP> algorithm is considered stable because the relative order of equivalent elements is maintained. </P>
	<A NAME="sec5"><H3>Complexity</H3></A>
	<P><SAMP>stable_sort()</SAMP> does approximately <SAMP>N * (log(N))2</SAMP> comparisons, where <SAMP>N</SAMP> equals <SAMP>finish - start</SAMP>. The algorithm calls <SAMP>std::get_temporary_buffer<>()</SAMP> to obtain extra memory. If enough extra memory is available, it does at most <SAMP>N * log(N)</SAMP> comparisons (i.e., the same as <SAMP><A HREF="sort.html">sort()</A></SAMP>).</P>
	<A NAME="sec6"><H3>Example</H3></A>

	<UL><PRE>//
	// sort.cpp
	//

	#include <vector>
	#include <algorithm>
	#include <functional>
	#include <iostream>


	struct associate
	{
	int num;
	char chr;
	associate (int n, char c) : num (n), chr (c){};
	associate () : num (0), chr ('\0'){};
	};


	inline bool operator< (const associate &x, const associate &y)
	{
	return x.num < y.num;
	}


	inline std::ostream& operator<< (std::ostream &s,
	const associate &x)
	{
	return s << '<' << x.num << ';' << x.chr << '>';
	}


	int main ()
	{
	const associate arr [20] = {
	associate (-4, ' '), associate (16, ' '),
	associate (17, ' '), associate (-3, 's'),
	associate (14, ' '), associate (-6, ' '),
	associate (-1, ' '), associate (-3, 't'),
	associate (23, ' '), associate (-3, 'a'),
	associate (-2, ' '), associate (-7, ' '),
	associate (-3, 'b'), associate (-8, ' '),
	associate (11, ' '), associate (-3, 'l'),
	associate (15, ' '), associate (-5, ' '),
	associate (-3, 'e'), associate (15, ' ')};

	typedef std::vector<associate, std::allocator<associate> >
	Vector;

	// Set up vectors.
	Vector v (arr, arr + sizeof arr / sizeof *arr);
	Vector v1 (sizeof arr / sizeof *arr);
	Vector v2 (sizeof arr / sizeof *arr);

	// Copy original vector to vectors #1 and #2.
	std::copy (v.begin (), v.end (), v1.begin ());
	std::copy (v.begin (), v.end (), v2.begin ());

	// Sort vector #1.
	std::sort (v1.begin (), v1.end ());

	// Stable sort vector #2.
	std::stable_sort (v2.begin (), v2.end ());

	// Display the results.
	std::cout << "Original sort stable_sort"
	<< std::endl;
	for (Vector::iterator i = v.begin (), j = v1.begin (),
	k = v2.begin ();
	i != v.end (); i++, j++, k++)
	std::cout << i << " " << j << " "
	<< *k << std::endl;

	return 0;
	}


	Program Output:
	</PRE></UL>
	<UL><PRE>Original sort stable_sort
	<-4; > <-8; > <-8; >
	<16; > <-7; > <-7; >
	<17; > <-6; > <-6; >
	<-3;s> <-5; > <-5; >
	<14; > <-4; > <-4; >
	<-6; > <-3;e> <-3;s>
	<-1; > <-3;s> <-3;t>
	<-3;t> <-3;l> <-3;a>
	<23; > <-3;t> <-3;b>
	<-3;a> <-3;b> <-3;l>
	<-2; > <-3;a> <-3;e>
	<-7; > <-2; > <-2; >
	<-3;b> <-1; > <-1; >
	<-8; > <11; > <11; >
	<11; > <14; > <14; >
	<-3;l> <15; > <15; >
	<15; > <15; > <15; >
	<-5; > <16; > <16; >
	<-3;e> <17; > <17; >
	<15; > <23; > <23; >
	</PRE></UL>
	<A NAME="sec7"><H3>See Also</H3></A>
	<P><SAMP><A HREF="sort.html">sort()</A></SAMP>, <SAMP><A HREF="partial-sort.html">partial_sort()</A></SAMP>, <SAMP><A HREF="partial-sort-copy.html">partial_sort_copy()</A></SAMP>, <SAMP><A HREF="get-temporary-buffer.html">get_temporary_buffer()</A></SAMP></P>
	<A NAME="sec8"><H3>Standards Conformance</H3></A>
	<P><I>ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.1.2</I></P>

	<BR>
	<HR>
	<A HREF="stable-partition.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="stack-h.html"><IMG SRC="images/bnext.gif" WIDTH=20 HEIGHT=21 ALT="Next file" BORDER=O></A>

	<!-- Google Analytics tracking code -->
	<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
	</script>
	<script type="text/javascript">
	_uacct = "UA-1775151-1";
	urchinTracker();
	</script>
	<!-- end of Google Analytics tracking code -->

	</BODY>
	</HTML>