<!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.13"/> <meta name="viewport" content="width=device-width, initial-scale=1"/> <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="navtreedata.js"></script> <script type="text/javascript" src="navtree.js"></script> <script type="text/javascript"> $(document).ready(initResizable); </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 id="projectalign" style="padding-left: 0.5em;"> <div id="projectname">libstdc++ </div> </td> </tr> </tbody> </table> </div> <!-- end header part --> <!-- Generated by Doxygen 1.8.13 --> </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('a01438.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="a01433.html">Algorithms</a> » <a class="el" href="a01436.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="a01438.svg" width="219" height="36"><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="a01438.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="a01438.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"><a class="el" href="a06689.html">pair</a>< _ForwardIterator, _ForwardIterator > </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a01438.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"><a class="el" href="a06689.html">pair</a>< _ForwardIterator, _ForwardIterator > </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="a01438.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="a01438.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="a01438.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="a01438.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="a01438.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 id="ga8272a9835bf987be37a4203e336fffe4"></a> <h2 class="memtitle"><span class="permalink"><a href="#ga8272a9835bf987be37a4203e336fffe4">◆ </a></span>binary_search() <span class="overload">[1/2]</span></h2> <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 class="definition">Definition at line <a class="el" href="a00482_source.html#l02254">2254</a> of file <a class="el" href="a00482_source.html">stl_algo.h</a>.</p> </div> </div> <a id="ga97bd3506e0ba43028e0d816a841d39cf"></a> <h2 class="memtitle"><span class="permalink"><a href="#ga97bd3506e0ba43028e0d816a841d39cf">◆ </a></span>binary_search() <span class="overload">[2/2]</span></h2> <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 class="definition">Definition at line <a class="el" href="a00482_source.html#l02289">2289</a> of file <a class="el" href="a00482_source.html">stl_algo.h</a>.</p> </div> </div> <a id="ga67b70af6f618f2c566d2f1849735fb6e"></a> <h2 class="memtitle"><span class="permalink"><a href="#ga67b70af6f618f2c566d2f1849735fb6e">◆ </a></span>equal_range() <span class="overload">[1/2]</span></h2> <div class="memitem"> <div class="memproto"> <div class="memtemplate"> template<typename _ForwardIterator , typename _Tp > </div> <table class="mlabels"> <tr> <td class="mlabels-left"> <table class="memname"> <tr> <td class="memname"><a class="el" href="a06689.html">pair</a><_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> </td> <td class="mlabels-right"> <span class="mlabels"><span class="mlabel">inline</span></span> </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="a01431.html#ga0409e288f07b697cb6885d1002df0bd6">std::make_pair</a>(lower_bound(__first, __last, __val),</div><div class="line"> upper_bound(__first, __last, __val))</div></div><!-- fragment --><p> but does not actually call those functions. </p> <p class="definition">Definition at line <a class="el" href="a00482_source.html#l02181">2181</a> of file <a class="el" href="a00482_source.html">stl_algo.h</a>.</p> </div> </div> <a id="ga2d3802f907c482a269e17ec3714d3df0"></a> <h2 class="memtitle"><span class="permalink"><a href="#ga2d3802f907c482a269e17ec3714d3df0">◆ </a></span>equal_range() <span class="overload">[2/2]</span></h2> <div class="memitem"> <div class="memproto"> <div class="memtemplate"> template<typename _ForwardIterator , typename _Tp , typename _Compare > </div> <table class="mlabels"> <tr> <td class="mlabels-left"> <table class="memname"> <tr> <td class="memname"><a class="el" href="a06689.html">pair</a><_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> </td> <td class="mlabels-right"> <span class="mlabels"><span class="mlabel">inline</span></span> </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="a01431.html#ga0409e288f07b697cb6885d1002df0bd6">std::make_pair</a>(lower_bound(__first, __last, __val, __comp),</div><div class="line"> upper_bound(__first, __last, __val, __comp))</div></div><!-- fragment --><p> but does not actually call those functions. </p> <p class="definition">Definition at line <a class="el" href="a00482_source.html#l02218">2218</a> of file <a class="el" href="a00482_source.html">stl_algo.h</a>.</p> </div> </div> <a id="ga6f1d41eed9a1fabbae1d54b384b07061"></a> <h2 class="memtitle"><span class="permalink"><a href="#ga6f1d41eed9a1fabbae1d54b384b07061">◆ </a></span>lower_bound() <span class="overload">[1/2]</span></h2> <div class="memitem"> <div class="memproto"> <div class="memtemplate"> template<typename _ForwardIterator , typename _Tp > </div> <table class="mlabels"> <tr> <td class="mlabels-left"> <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> </td> <td class="mlabels-right"> <span class="mlabels"><span class="mlabel">inline</span></span> </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 class="definition">Definition at line <a class="el" href="a00485_source.html#l01000">1000</a> of file <a class="el" href="a00485_source.html">stl_algobase.h</a>.</p> <p class="reference">Referenced by <a class="el" href="a15277_source.html#l02622">std::operator>>()</a>.</p> </div> </div> <a id="ga80229c3a1e83296551a68c44bda48696"></a> <h2 class="memtitle"><span class="permalink"><a href="#ga80229c3a1e83296551a68c44bda48696">◆ </a></span>lower_bound() <span class="overload">[2/2]</span></h2> <div class="memitem"> <div class="memproto"> <div class="memtemplate"> template<typename _ForwardIterator , typename _Tp , typename _Compare > </div> <table class="mlabels"> <tr> <td class="mlabels-left"> <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> </td> <td class="mlabels-right"> <span class="mlabels"><span class="mlabel">inline</span></span> </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 class="definition">Definition at line <a class="el" href="a00482_source.html#l02018">2018</a> of file <a class="el" href="a00482_source.html">stl_algo.h</a>.</p> </div> </div> <a id="ga0a8fc99be7f8267b6eb97ff9c712c75f"></a> <h2 class="memtitle"><span class="permalink"><a href="#ga0a8fc99be7f8267b6eb97ff9c712c75f">◆ </a></span>upper_bound() <span class="overload">[1/2]</span></h2> <div class="memitem"> <div class="memproto"> <div class="memtemplate"> template<typename _ForwardIterator , typename _Tp > </div> <table class="mlabels"> <tr> <td class="mlabels-left"> <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> </td> <td class="mlabels-right"> <span class="mlabels"><span class="mlabel">inline</span></span> </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 class="definition">Definition at line <a class="el" href="a00482_source.html#l02075">2075</a> of file <a class="el" href="a00482_source.html">stl_algo.h</a>.</p> </div> </div> <a id="ga639d56cfebd6f1fbabf344c49a5c5539"></a> <h2 class="memtitle"><span class="permalink"><a href="#ga639d56cfebd6f1fbabf344c49a5c5539">◆ </a></span>upper_bound() <span class="overload">[2/2]</span></h2> <div class="memitem"> <div class="memproto"> <div class="memtemplate"> template<typename _ForwardIterator , typename _Tp , typename _Compare > </div> <table class="mlabels"> <tr> <td class="mlabels-left"> <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> </td> <td class="mlabels-right"> <span class="mlabels"><span class="mlabel">inline</span></span> </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 class="definition">Definition at line <a class="el" href="a00482_source.html#l02107">2107</a> of file <a class="el" href="a00482_source.html">stl_algo.h</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.13 </li> </ul> </div> </body> </html>