<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.5"/>
<title>libstdc++: Binary Search</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
$(document).ready(initResizable);
$(window).load(resizeHeight);
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">libstdc++
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.5 -->
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
<div id="nav-sync" class="sync"></div>
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('a01708.html','');});
</script>
<div id="doc-content">
<div class="header">
<div class="summary">
<a href="#func-members">Functions</a> </div>
<div class="headertitle">
<div class="title">Binary Search<div class="ingroups"><a class="el" href="a01706.html">Sorting</a></div></div> </div>
</div><!--header-->
<div class="contents">
<div class="dynheader">
Collaboration diagram for Binary Search:</div>
<div class="dyncontent">
<center><table><tr><td><div class="center"><iframe scrolling="no" frameborder="0" src="a01708.svg" width="219" height="35"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe>
</div>
</td></tr></table></center>
</div>
<table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="func-members"></a>
Functions</h2></td></tr>
<tr class="memitem:ga8272a9835bf987be37a4203e336fffe4"><td class="memTemplParams" colspan="2">template<typename _ForwardIterator , typename _Tp > </td></tr>
<tr class="memitem:ga8272a9835bf987be37a4203e336fffe4"><td class="memTemplItemLeft" align="right" valign="top">bool </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a01708.html#ga8272a9835bf987be37a4203e336fffe4">std::binary_search</a> (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val)</td></tr>
<tr class="separator:ga8272a9835bf987be37a4203e336fffe4"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:ga97bd3506e0ba43028e0d816a841d39cf"><td class="memTemplParams" colspan="2">template<typename _ForwardIterator , typename _Tp , typename _Compare > </td></tr>
<tr class="memitem:ga97bd3506e0ba43028e0d816a841d39cf"><td class="memTemplItemLeft" align="right" valign="top">bool </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a01708.html#ga97bd3506e0ba43028e0d816a841d39cf">std::binary_search</a> (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)</td></tr>
<tr class="separator:ga97bd3506e0ba43028e0d816a841d39cf"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:ga67b70af6f618f2c566d2f1849735fb6e"><td class="memTemplParams" colspan="2">template<typename _ForwardIterator , typename _Tp > </td></tr>
<tr class="memitem:ga67b70af6f618f2c566d2f1849735fb6e"><td class="memTemplItemLeft" align="right" valign="top">pair< _ForwardIterator, <br class="typebreak"/>
_ForwardIterator > </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a01708.html#ga67b70af6f618f2c566d2f1849735fb6e">std::equal_range</a> (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val)</td></tr>
<tr class="separator:ga67b70af6f618f2c566d2f1849735fb6e"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:ga2d3802f907c482a269e17ec3714d3df0"><td class="memTemplParams" colspan="2">template<typename _ForwardIterator , typename _Tp , typename _Compare > </td></tr>
<tr class="memitem:ga2d3802f907c482a269e17ec3714d3df0"><td class="memTemplItemLeft" align="right" valign="top">pair< _ForwardIterator, <br class="typebreak"/>
_ForwardIterator > </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a01708.html#ga2d3802f907c482a269e17ec3714d3df0">std::equal_range</a> (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)</td></tr>
<tr class="separator:ga2d3802f907c482a269e17ec3714d3df0"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:ga6f1d41eed9a1fabbae1d54b384b07061"><td class="memTemplParams" colspan="2">template<typename _ForwardIterator , typename _Tp > </td></tr>
<tr class="memitem:ga6f1d41eed9a1fabbae1d54b384b07061"><td class="memTemplItemLeft" align="right" valign="top">_ForwardIterator </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a01708.html#ga6f1d41eed9a1fabbae1d54b384b07061">std::lower_bound</a> (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val)</td></tr>
<tr class="separator:ga6f1d41eed9a1fabbae1d54b384b07061"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:ga80229c3a1e83296551a68c44bda48696"><td class="memTemplParams" colspan="2">template<typename _ForwardIterator , typename _Tp , typename _Compare > </td></tr>
<tr class="memitem:ga80229c3a1e83296551a68c44bda48696"><td class="memTemplItemLeft" align="right" valign="top">_ForwardIterator </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a01708.html#ga80229c3a1e83296551a68c44bda48696">std::lower_bound</a> (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)</td></tr>
<tr class="separator:ga80229c3a1e83296551a68c44bda48696"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:ga0a8fc99be7f8267b6eb97ff9c712c75f"><td class="memTemplParams" colspan="2">template<typename _ForwardIterator , typename _Tp > </td></tr>
<tr class="memitem:ga0a8fc99be7f8267b6eb97ff9c712c75f"><td class="memTemplItemLeft" align="right" valign="top">_ForwardIterator </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a01708.html#ga0a8fc99be7f8267b6eb97ff9c712c75f">std::upper_bound</a> (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val)</td></tr>
<tr class="separator:ga0a8fc99be7f8267b6eb97ff9c712c75f"><td class="memSeparator" colspan="2"> </td></tr>
<tr class="memitem:ga639d56cfebd6f1fbabf344c49a5c5539"><td class="memTemplParams" colspan="2">template<typename _ForwardIterator , typename _Tp , typename _Compare > </td></tr>
<tr class="memitem:ga639d56cfebd6f1fbabf344c49a5c5539"><td class="memTemplItemLeft" align="right" valign="top">_ForwardIterator </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a01708.html#ga639d56cfebd6f1fbabf344c49a5c5539">std::upper_bound</a> (_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)</td></tr>
<tr class="separator:ga639d56cfebd6f1fbabf344c49a5c5539"><td class="memSeparator" colspan="2"> </td></tr>
</table>
<a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2>
<p>These algorithms are variations of a classic binary search, and all assume that the sequence being searched is already sorted.</p>
<p>The number of comparisons will be logarithmic (and as few as possible). The number of steps through the sequence will be logarithmic for random-access iterators (e.g., pointers), and linear otherwise.</p>
<p>The LWG has passed Defect Report 270, which notes: <em>The proposed resolution reinterprets binary search. Instead of thinking about searching for a value in a sorted range, we view that as an important special case of a more general algorithm: searching for the partition point in a partitioned range. We also add a guarantee that the old wording did not: we ensure that the upper bound is no earlier than the lower bound, that the pair returned by equal_range is a valid range, and that the first part of that pair is the lower bound.</em></p>
<p>The actual effect of the first sentence is that a comparison functor passed by the user doesn't necessarily need to induce a strict weak ordering relation. Rather, it partitions the range. </p>
<h2 class="groupheader">Function Documentation</h2>
<a class="anchor" id="ga8272a9835bf987be37a4203e336fffe4"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename _ForwardIterator , typename _Tp > </div>
<table class="memname">
<tr>
<td class="memname">bool std::binary_search </td>
<td>(</td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const _Tp & </td>
<td class="paramname"><em>__val</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Determines whether an element exists in a range. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">__first</td><td>An iterator. </td></tr>
<tr><td class="paramname">__last</td><td>Another iterator. </td></tr>
<tr><td class="paramname">__val</td><td>The search term. </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>True if <code>__val</code> (or its equivalent) is in [<code>__first</code>,<code>__last</code> ].</dd></dl>
<p>Note that this does not actually return an iterator to <code>__val</code>. For that, use std::find or a container's specialized find member functions. </p>
<p>Definition at line <a class="el" href="a01546_source.html#l02697">2697</a> of file <a class="el" href="a01546_source.html">stl_algo.h</a>.</p>
<p>References <a class="el" href="a01547_source.html#l00943">std::lower_bound()</a>.</p>
</div>
</div>
<a class="anchor" id="ga97bd3506e0ba43028e0d816a841d39cf"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename _ForwardIterator , typename _Tp , typename _Compare > </div>
<table class="memname">
<tr>
<td class="memname">bool std::binary_search </td>
<td>(</td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const _Tp & </td>
<td class="paramname"><em>__val</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">_Compare </td>
<td class="paramname"><em>__comp</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Determines whether an element exists in a range. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">__first</td><td>An iterator. </td></tr>
<tr><td class="paramname">__last</td><td>Another iterator. </td></tr>
<tr><td class="paramname">__val</td><td>The search term. </td></tr>
<tr><td class="paramname">__comp</td><td>A functor to use for comparisons. </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>True if <code>__val</code> (or its equivalent) is in <code></code>[__first,__last].</dd></dl>
<p>Note that this does not actually return an iterator to <code>__val</code>. For that, use std::find or a container's specialized find member functions.</p>
<p>The comparison function should have the same effects on ordering as the function used for the initial sort. </p>
<p>Definition at line <a class="el" href="a01546_source.html#l02730">2730</a> of file <a class="el" href="a01546_source.html">stl_algo.h</a>.</p>
<p>References <a class="el" href="a01547_source.html#l00943">std::lower_bound()</a>.</p>
</div>
</div>
<a class="anchor" id="ga67b70af6f618f2c566d2f1849735fb6e"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename _ForwardIterator , typename _Tp > </div>
<table class="memname">
<tr>
<td class="memname">pair<_ForwardIterator, _ForwardIterator> std::equal_range </td>
<td>(</td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const _Tp & </td>
<td class="paramname"><em>__val</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Finds the largest subrange in which <code>__val</code> could be inserted at any place in it without changing the ordering. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">__first</td><td>An iterator. </td></tr>
<tr><td class="paramname">__last</td><td>Another iterator. </td></tr>
<tr><td class="paramname">__val</td><td>The search term. </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>An pair of iterators defining the subrange.</dd></dl>
<p>This is equivalent to </p>
<div class="fragment"><div class="line">* <a class="code" href="a01701.html#ga0409e288f07b697cb6885d1002df0bd6">std::make_pair</a>(lower_bound(__first, __last, __val),</div>
<div class="line">* upper_bound(__first, __last, __val))</div>
<div class="line">* </div>
</div><!-- fragment --><p> but does not actually call those functions. </p>
<p>Definition at line <a class="el" href="a01546_source.html#l02574">2574</a> of file <a class="el" href="a01546_source.html">stl_algo.h</a>.</p>
<p>References <a class="el" href="a01554_source.html#l00173">std::advance()</a>, <a class="el" href="a01554_source.html#l00114">std::distance()</a>, <a class="el" href="a01547_source.html#l00943">std::lower_bound()</a>, and <a class="el" href="a01546_source.html#l02521">std::upper_bound()</a>.</p>
</div>
</div>
<a class="anchor" id="ga2d3802f907c482a269e17ec3714d3df0"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename _ForwardIterator , typename _Tp , typename _Compare > </div>
<table class="memname">
<tr>
<td class="memname">pair<_ForwardIterator, _ForwardIterator> std::equal_range </td>
<td>(</td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const _Tp & </td>
<td class="paramname"><em>__val</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">_Compare </td>
<td class="paramname"><em>__comp</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Finds the largest subrange in which <code>__val</code> could be inserted at any place in it without changing the ordering. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">__first</td><td>An iterator. </td></tr>
<tr><td class="paramname">__last</td><td>Another iterator. </td></tr>
<tr><td class="paramname">__val</td><td>The search term. </td></tr>
<tr><td class="paramname">__comp</td><td>A functor to use for comparisons. </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>An pair of iterators defining the subrange.</dd></dl>
<p>This is equivalent to </p>
<div class="fragment"><div class="line">* <a class="code" href="a01701.html#ga0409e288f07b697cb6885d1002df0bd6">std::make_pair</a>(lower_bound(__first, __last, __val, __comp),</div>
<div class="line">* upper_bound(__first, __last, __val, __comp))</div>
<div class="line">* </div>
</div><!-- fragment --><p> but does not actually call those functions. </p>
<p>Definition at line <a class="el" href="a01546_source.html#l02636">2636</a> of file <a class="el" href="a01546_source.html">stl_algo.h</a>.</p>
<p>References <a class="el" href="a01554_source.html#l00173">std::advance()</a>, <a class="el" href="a01554_source.html#l00114">std::distance()</a>, <a class="el" href="a01547_source.html#l00943">std::lower_bound()</a>, and <a class="el" href="a01546_source.html#l02521">std::upper_bound()</a>.</p>
</div>
</div>
<a class="anchor" id="ga6f1d41eed9a1fabbae1d54b384b07061"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename _ForwardIterator , typename _Tp > </div>
<table class="memname">
<tr>
<td class="memname">_ForwardIterator std::lower_bound </td>
<td>(</td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const _Tp & </td>
<td class="paramname"><em>__val</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Finds the first position in which <em>val</em> could be inserted without changing the ordering. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">__first</td><td>An iterator. </td></tr>
<tr><td class="paramname">__last</td><td>Another iterator. </td></tr>
<tr><td class="paramname">__val</td><td>The search term. </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>An iterator pointing to the first element <em>not less than</em> <em>val</em>, or end() if every element is less than <em>val</em>. </dd></dl>
<p>Definition at line <a class="el" href="a01547_source.html#l00943">943</a> of file <a class="el" href="a01547_source.html">stl_algobase.h</a>.</p>
<p>References <a class="el" href="a01554_source.html#l00173">std::advance()</a>, and <a class="el" href="a01554_source.html#l00114">std::distance()</a>.</p>
<p>Referenced by <a class="el" href="a01546_source.html#l02934">std::__merge_adaptive()</a>, <a class="el" href="a01546_source.html#l03047">std::__merge_without_buffer()</a>, <a class="el" href="a01546_source.html#l02697">std::binary_search()</a>, and <a class="el" href="a01546_source.html#l02574">std::equal_range()</a>.</p>
</div>
</div>
<a class="anchor" id="ga80229c3a1e83296551a68c44bda48696"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename _ForwardIterator , typename _Tp , typename _Compare > </div>
<table class="memname">
<tr>
<td class="memname">_ForwardIterator std::lower_bound </td>
<td>(</td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const _Tp & </td>
<td class="paramname"><em>__val</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">_Compare </td>
<td class="paramname"><em>__comp</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Finds the first position in which <code>__val</code> could be inserted without changing the ordering. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">__first</td><td>An iterator. </td></tr>
<tr><td class="paramname">__last</td><td>Another iterator. </td></tr>
<tr><td class="paramname">__val</td><td>The search term. </td></tr>
<tr><td class="paramname">__comp</td><td>A functor to use for comparisons. </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>An iterator pointing to the first element <em>not less than</em> <code>__val</code>, or end() if every element is less than <code>__val</code>.</dd></dl>
<p>The comparison function should have the same effects on ordering as the function used for the initial sort. </p>
<p>Definition at line <a class="el" href="a01546_source.html#l02425">2425</a> of file <a class="el" href="a01546_source.html">stl_algo.h</a>.</p>
<p>References <a class="el" href="a01554_source.html#l00173">std::advance()</a>, and <a class="el" href="a01554_source.html#l00114">std::distance()</a>.</p>
</div>
</div>
<a class="anchor" id="ga0a8fc99be7f8267b6eb97ff9c712c75f"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename _ForwardIterator , typename _Tp > </div>
<table class="memname">
<tr>
<td class="memname">_ForwardIterator std::upper_bound </td>
<td>(</td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const _Tp & </td>
<td class="paramname"><em>__val</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Finds the last position in which <code>__val</code> could be inserted without changing the ordering. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">__first</td><td>An iterator. </td></tr>
<tr><td class="paramname">__last</td><td>Another iterator. </td></tr>
<tr><td class="paramname">__val</td><td>The search term. </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>An iterator pointing to the first element greater than <code>__val</code>, or end() if no elements are greater than <code>__val</code>. </dd></dl>
<p>Definition at line <a class="el" href="a01546_source.html#l02472">2472</a> of file <a class="el" href="a01546_source.html">stl_algo.h</a>.</p>
<p>References <a class="el" href="a01554_source.html#l00173">std::advance()</a>, and <a class="el" href="a01554_source.html#l00114">std::distance()</a>.</p>
</div>
</div>
<a class="anchor" id="ga639d56cfebd6f1fbabf344c49a5c5539"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename _ForwardIterator , typename _Tp , typename _Compare > </div>
<table class="memname">
<tr>
<td class="memname">_ForwardIterator std::upper_bound </td>
<td>(</td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__first</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">_ForwardIterator </td>
<td class="paramname"><em>__last</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const _Tp & </td>
<td class="paramname"><em>__val</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">_Compare </td>
<td class="paramname"><em>__comp</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Finds the last position in which <code>__val</code> could be inserted without changing the ordering. </p>
<dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramname">__first</td><td>An iterator. </td></tr>
<tr><td class="paramname">__last</td><td>Another iterator. </td></tr>
<tr><td class="paramname">__val</td><td>The search term. </td></tr>
<tr><td class="paramname">__comp</td><td>A functor to use for comparisons. </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>An iterator pointing to the first element greater than <code>__val</code>, or end() if no elements are greater than <code>__val</code>.</dd></dl>
<p>The comparison function should have the same effects on ordering as the function used for the initial sort. </p>
<p>Definition at line <a class="el" href="a01546_source.html#l02521">2521</a> of file <a class="el" href="a01546_source.html">stl_algo.h</a>.</p>
<p>References <a class="el" href="a01554_source.html#l00173">std::advance()</a>, and <a class="el" href="a01554_source.html#l00114">std::distance()</a>.</p>
<p>Referenced by <a class="el" href="a01546_source.html#l02934">std::__merge_adaptive()</a>, <a class="el" href="a01546_source.html#l03047">std::__merge_without_buffer()</a>, and <a class="el" href="a01546_source.html#l02574">std::equal_range()</a>.</p>
</div>
</div>
</div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<li class="footer">Generated by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.5 </li>
</ul>
</div>
</body>
</html>
