doc/stdlibug/14-5.html - stdcxx - Git at Google

 <!--
     Licensed to the Apache Software  Foundation (ASF) under one or more
     contributor  license agreements.  See  the NOTICE  file distributed
     with  this  work  for  additional information  regarding  copyright
     ownership.   The ASF  licenses this  file to  you under  the Apache
     License, Version  2.0 (the  License); you may  not use  this file
     except in  compliance with the License.   You may obtain  a copy of
     the License at

     http://www.apache.org/licenses/LICENSE-2.0

     Unless required by applicable law or agreed to in writing, software
     distributed under the  License is distributed on an  "AS IS" BASIS,
     WITHOUT  WARRANTIES OR CONDITIONS  OF ANY  KIND, either  express or
     implied.   See  the License  for  the  specific language  governing
     permissions and limitations under the License.

     Copyright 1999-2007 Rogue Wave Software, Inc.
 -->

 <HTML>
 <HEAD>
 <TITLE>Merge Ordered Sequences</TITLE>
 <LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD>
 <BODY BGCOLOR=#FFFFFF>
 <A HREF="14-4.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="14-6.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library User's Guide</B></DIV>
 <H2>14.5 Merge Ordered Sequences</H2>
 <A NAME="idx360"><!></A>
 <P>The algorithm <SAMP>std::merge()</SAMP> combines two ordered sequences to form a new ordered sequence. The size of the result is the sum of the sizes of the two argument sequences. This should be contrasted with the <SAMP>std::set_union()</SAMP> operation, which eliminates elements that are duplicated in both sets. The <SAMP>std::set_union()</SAMP> function is described later in this chapter.</P>
 <P>The merge operation is stable. This means, for equal elements in the two ranges, not only is the relative ordering of values from each range preserved, but the values from the first range always precede the elements from the second. The two ranges are described by a pair of <B><I><A HREF="../stdlibref/iterator.html">iterator</A></I></B>s, whereas the result is defined by a single output <B><I>iterator</I></B>. The arguments are shown in the following declaration:</P>

 <UL><PRE>
 namespace std {
   OutputIterator merge
      (InputIterator first1, InputIterator last1,
       InputIterator first2, InputIterator last2,
       OutputIterator result [, Compare ]);
 }
 </PRE></UL>
 <P>The example program illustrates a simple merge, the use of a merge with an inserter, and the use of a merge with an output stream <B><I><A HREF="../stdlibref/iterator.html">iterator</A></I></B>.</P>

 <A NAME="idx361"><!></A>
 <UL><PRE>
 void merge_example()
 // illustrates the use of the merge algorithm
 // see alg7.cpp for complete source code

 {
   // make a list and vector of 10 random integers
   std::vector&lt;int&gt; aVec(10);
   std::list&lt;int&gt; aList(10, 0);
   std::generate(aVec.begin(), aVec.end(), randomValue);
   std::sort(aVec.begin(), aVec.end());
   std::generate_n(aList.begin(), 10, randomValue);
   aList.sort();

   // merge into a vector
   std::vector&lt;int&gt; vResult(aVec.size() + aList.size());
   std::merge(aVec.begin(), aVec.end(),
              aList.begin(), aList.end(), vResult.begin());

   // merge into a list
   std::list&lt;int&gt; lResult;
   std::merge(aVec.begin(), aVec.end(), aList.begin(),
              aList.end(), inserter(lResult, lResult.begin()));

   // merge into the output
   std::merge(aVec.begin(), aVec.end(), aList.begin(), aList.end(),
              std::ostream_iterator&lt;int,char&gt; (std::cout, " "));
   std::cout &lt;&lt; std::endl;
 }
 </PRE></UL>
 <A NAME="idx362"><!></A>
 <P>The algorithm <SAMP>std::inplace_merge()</SAMP> (<A HREF="13-4.html#1346">Section&nbsp;13.4.6</A>) can be used to merge two sections of a single sequence into one sequence.</P>

 <BR>
 <HR>
 <A HREF="14-4.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="14-6.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>
	<!--
	Licensed to the Apache Software Foundation (ASF) under one or more
	contributor license agreements. See the NOTICE file distributed
	with this work for additional information regarding copyright
	ownership. The ASF licenses this file to you under the Apache
	License, Version 2.0 (the License); you may not use this file
	except in compliance with the License. You may obtain a copy of
	the License at

	http://www.apache.org/licenses/LICENSE-2.0

	Unless required by applicable law or agreed to in writing, software
	distributed under the License is distributed on an "AS IS" BASIS,
	WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
	implied. See the License for the specific language governing
	permissions and limitations under the License.

	Copyright 1999-2007 Rogue Wave Software, Inc.
	-->

	<HTML>
	<HEAD>
	<TITLE>Merge Ordered Sequences</TITLE>
	<LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD>
	<BODY BGCOLOR=#FFFFFF>
	<A HREF="14-4.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="14-6.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library User's Guide</B></DIV>
	<H2>14.5 Merge Ordered Sequences</H2>
	<A NAME="idx360"><!></A>
	<P>The algorithm <SAMP>std::merge()</SAMP> combines two ordered sequences to form a new ordered sequence. The size of the result is the sum of the sizes of the two argument sequences. This should be contrasted with the <SAMP>std::set_union()</SAMP> operation, which eliminates elements that are duplicated in both sets. The <SAMP>std::set_union()</SAMP> function is described later in this chapter.</P>
	<P>The merge operation is stable. This means, for equal elements in the two ranges, not only is the relative ordering of values from each range preserved, but the values from the first range always precede the elements from the second. The two ranges are described by a pair of <B><I><A HREF="../stdlibref/iterator.html">iterator</A></I></B>s, whereas the result is defined by a single output <B><I>iterator</I></B>. The arguments are shown in the following declaration:</P>

	<UL><PRE>
	namespace std {
	OutputIterator merge
	(InputIterator first1, InputIterator last1,
	InputIterator first2, InputIterator last2,
	OutputIterator result [, Compare ]);
	}
	</PRE></UL>
	<P>The example program illustrates a simple merge, the use of a merge with an inserter, and the use of a merge with an output stream <B><I><A HREF="../stdlibref/iterator.html">iterator</A></I></B>.</P>

	<A NAME="idx361"><!></A>
	<UL><PRE>
	void merge_example()
	// illustrates the use of the merge algorithm
	// see alg7.cpp for complete source code

	{
	// make a list and vector of 10 random integers
	std::vector<int> aVec(10);
	std::list<int> aList(10, 0);
	std::generate(aVec.begin(), aVec.end(), randomValue);
	std::sort(aVec.begin(), aVec.end());
	std::generate_n(aList.begin(), 10, randomValue);
	aList.sort();

	// merge into a vector
	std::vector<int> vResult(aVec.size() + aList.size());
	std::merge(aVec.begin(), aVec.end(),
	aList.begin(), aList.end(), vResult.begin());

	// merge into a list
	std::list<int> lResult;
	std::merge(aVec.begin(), aVec.end(), aList.begin(),
	aList.end(), inserter(lResult, lResult.begin()));

	// merge into the output
	std::merge(aVec.begin(), aVec.end(), aList.begin(), aList.end(),
	std::ostream_iterator<int,char> (std::cout, " "));
	std::cout << std::endl;
	}
	</PRE></UL>
	<A NAME="idx362"><!></A>
	<P>The algorithm <SAMP>std::inplace_merge()</SAMP> (<A HREF="13-4.html#1346">Section 13.4.6</A>) can be used to merge two sections of a single sequence into one sequence.</P>

	<BR>
	<HR>
	<A HREF="14-4.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="14-6.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>