1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192
|
<HTML>
<!--
-- Copyright (c) 1996-1999
-- Silicon Graphics Computer Systems, Inc.
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. Silicon Graphics makes no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
--
-- Copyright (c) 1994
-- Hewlett-Packard Company
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. Hewlett-Packard Company makes no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
--
-->
<Head>
<Title>inplace_merge</Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="CorpID.gif"
ALT="SGI" HEIGHT="43" WIDTH="151">
<!--end header-->
<BR Clear>
<H1>inplace_merge</H1>
<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "algorithms.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD>
<TD Align=right><Img src = "function.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: algorithms</TD>
<TD Align=right VAlign=top><b>Component type</b>: function</TD>
</TR>
</Table>
<h3>Prototype</h3>
<tt>Inplace_merge</tt> is an overloaded name: there are actually two
<tt>inplace_merge</tt> functions.
<pre>
template <class <A href="BidirectionalIterator.html">BidirectionalIterator</A>>
inline void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template <class <A href="BidirectionalIterator.html">BidirectionalIterator</A>, class <A href="StrictWeakOrdering.html">StrictWeakOrdering</A>>
inline void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, StrictWeakOrdering comp);
</pre>
<h3>Description</h3>
<tt>Inplace_merge</tt> combines two consecutive sorted ranges <tt>[first, middle)</tt>
and <tt>[middle, last)</tt> into a single sorted range <tt>[first, last)</tt>.
That is, it starts with a range <tt>[first, last)</tt> that consists of
two pieces each of which is in ascending order, and rearranges it
so that the entire range is in ascending order. <tt>Inplace_merge</tt> is
stable, meaning both that
the relative order of elements within each input range is preserved,
and that for equivalent <A href="#1">[1]</A> elements in both input ranges the element
from the first range precedes the element from the second.
<P>
The two versions of <tt>inplace_merge</tt> differ in how elements are compared.
The first version uses <tt>operator<</tt>. That is, the input ranges and
the output range satisfy the condition that for every pair of
iterators <tt>i</tt> and <tt>j</tt> such that <tt>i</tt> precedes <tt>j</tt>, <tt>*j < *i</tt> is <tt>false</tt>.
The second version uses the <A href="functors.html">function object</A> <tt>comp</tt>.
That is, the input ranges and the output range satisfy the condition
that for every pair of
iterators <tt>i</tt> and <tt>j</tt> such that <tt>i</tt> precedes <tt>j</tt>, <tt>comp(*j, *i)</tt> is <tt>false</tt>.
<h3>Definition</h3>
Defined in <A href="algo.h">algo.h</A>.
<h3>Requirements on types</h3>
For the first version:
<UL>
<LI>
<tt>BidirectionalIterator</tt> is a model of <A href="BidirectionalIterator.html">Bidirectional Iterator</A>.
<LI>
<tt>BidirectionalIterator</tt> is mutable.
<LI>
<tt>BidirectionalIterator</tt>'s value type is a model of <A href="LessThanComparable.html">LessThan Comparable</A>.
<LI>
The ordering on objects of <tt>BidirectionalIterator</tt>'s value type is a
<i>strict weak ordering</i>, as defined in the <A href="LessThanComparable.html">LessThan Comparable</A>
requirements.
</UL>
For the second version:
<UL>
<LI>
<tt>BidirectionalIterator</tt> is a model of <A href="BidirectionalIterator.html">Bidirectional Iterator</A>.
<LI>
<tt>BidirectionalIterator</tt> is mutable.
<LI>
<tt>StrictWeakOrdering</tt> is a model of <A href="StrictWeakOrdering.html">Strict Weak Ordering</A>.
<LI>
<tt>BidirectionalIterator</tt>'s value type is convertible to
<tt>StrictWeakOrdering</tt>'s argument type.
</UL>
<h3>Preconditions</h3>
For the first version:
<UL>
<LI>
<tt>[first, middle)</tt> is a valid range.
<LI>
<tt>[middle, last)</tt> is a valid range.
<LI>
<tt>[first, middle)</tt> is in ascending order. That is, for every pair
of iterators <tt>i</tt> and <tt>j</tt> in <tt>[first, middle)</tt> such that <tt>i</tt> precedes
<tt>j</tt>, <tt>*j < *i</tt> is <tt>false</tt>.
<LI>
<tt>[middle, last)</tt> is in ascending order. That is, for every pair
of iterators <tt>i</tt> and <tt>j</tt> in <tt>[middle, last)</tt> such that <tt>i</tt> precedes
<tt>j</tt>, <tt>*j < *i</tt> is <tt>false</tt>.
</UL>
For the second version:
<UL>
<LI>
<tt>[first, middle)</tt> is a valid range.
<LI>
<tt>[middle, last)</tt> is a valid range.
<LI>
<tt>[first, middle)</tt> is in ascending order. That is, for every pair
of iterators <tt>i</tt> and <tt>j</tt> in <tt>[first, middle)</tt> such that <tt>i</tt> precedes
<tt>j</tt>, <tt>comp(*j, *i)</tt> is <tt>false</tt>.
<LI>
<tt>[middle, last)</tt> is in ascending order. That is, for every pair
of iterators <tt>i</tt> and <tt>j</tt> in <tt>[middle, last)</tt> such that <tt>i</tt> precedes
<tt>j</tt>, <tt>comp(*j, *i)</tt> is <tt>false</tt>.
</UL>
<h3>Complexity</h3>
<tt>Inplace_merge</tt>
is an <i>adaptive</i> algorithm: it attempts to
allocate a temporary memory buffer, and its run-time complexity depends
on how much memory is available.
<tt>Inplace_merge</tt> performs no comparisons if
<tt>[first, last)</tt> is an empty range.
Otherwise, worst-case behavior (if no auxiliary memory is available) is
<tt>O(N log(N))</tt>, where <tt>N</tt> is <tt>last - first</tt>,
and best case (if a large enough auxiliary memory buffer is available) is
at most <tt>(last - first) - 1</tt> comparisons.
<h3>Example</h3>
<pre>
int main()
{
int A[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
inplace_merge(A, A + 4, A + 8);
copy(A, A + 8, ostream_iterator<int>(cout, " "));
// The output is "1 2 3 4 5 6 7 8".
}
</pre>
<h3>Notes</h3>
<P><A name="1">[1]</A>
Note that you may use an ordering that is a strict weak ordering
but not a total ordering; that is, there might be values <tt>x</tt> and <tt>y</tt>
such that <tt>x < y</tt>, <tt>x > y</tt>, and <tt>x == y</tt> are all false. (See the
<A href="LessThanComparable.html">LessThan Comparable</A> requirements for a fuller discussion.)
Two elements <tt>x</tt> and <tt>y</tt> are <i>equivalent</i> if neither <tt>x < y</tt> nor
<tt>y < x</tt>. If you're using a total ordering, however (if you're
using <tt>strcmp</tt>, for example, or if you're using ordinary arithmetic
comparison on integers), then you can ignore this technical
distinction: for a total ordering, equality and equivalence are
the same.
<h3>See also</h3>
<tt><A href="merge.html">merge</A></tt>, <tt><A href="set_union.html">set_union</A></tt>, <tt><A href="sort.html">sort</A></tt>
<!--start footer-->
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54"
ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif"
HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright ©
1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML>
|