<!--
    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>upper_bound()</TITLE>
<LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD>
<BODY BGCOLOR=#FFFFFF>
<A HREF="unique.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="use-facet.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>upper_bound()</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>An algorithm that determines the last valid position for a value in a sorted container</P>
<A NAME="sec3"><H3>Synopsis</H3></A>

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

namespace std {
  template &lt;class ForwardIterator, class T&gt; 
  ForwardIterator
  upper_bound(ForwardIterator start, ForwardIterator finish,
              const T&amp; value);

  template &lt;class ForwardIterator, class T, class Compare&gt;
  ForwardIterator
  upper_bound(ForwardIterator start, ForwardIterator finish,
              const T&amp; value, Compare comp);
}
</PRE>
<A NAME="sec4"><H3>Description</H3></A>
<P>The <SAMP>upper_bound()</SAMP> algorithm is one of a set of binary search algorithms. All of these algorithms perform binary searches on ordered sequences. Each algorithm has two versions. The first version uses <SAMP>operator&lt;()</SAMP> to perform the comparison, and assumes that the sequence has been sorted using that operator. The second version allows you to include a function object of type <SAMP>Compare</SAMP>, and assumes that <SAMP>Compare</SAMP> is the function used to sort the sequence. The function object must be a binary predicate. </P>
<P>The <SAMP>upper_bound()</SAMP> algorithm finds the last position in a sequence that <SAMP>value</SAMP> can occupy without violating the sequence's ordering. <SAMP>upper_bound()</SAMP>'s return value is the iterator for the first element in the sequence that is greater than <SAMP>value</SAMP>, or, when the comparison operator is used, the first element that does NOT satisfy the comparison function. Because the algorithm is restricted to using the less than operator or the user-defined function to perform the search, <SAMP>upper_bound()</SAMP> returns an iterator <SAMP>i</SAMP> in the range <SAMP>[start, finish)</SAMP> such that for any iterator <SAMP>j</SAMP> in the range <SAMP>[start, i)</SAMP> the appropriate version of the following conditions holds:</P>
<P><SAMP>!(value &lt; *j)</SAMP></P>
<P>or </P>
<P><SAMP>comp(value, *j) == false</SAMP></P>
<A NAME="sec5"><H3>Complexity</H3></A>
<P><SAMP>upper_bound()</SAMP> performs at most <SAMP>log(finish - start) + 1</SAMP> comparisons.</P>
<A NAME="sec6"><H3>Example</H3></A>

<UL><PRE>//
//  ul_bound.cpp
//

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

int main ()
{
    typedef std::vector&lt;int, std::allocator&lt;int&gt; &gt; Vector;
    typedef Vector::const_iterator                 Iterator;

    const int a[] = { 0, 1, 2, 2, 3, 4, 5, 5, 5, 6, 7 };

    // Set up a vector.
    const Vector v (a, a + sizeof a / sizeof *a);

    // Try lower_bound variants.
    Iterator it1 = std::lower_bound (v.begin (),v.end (), 3);
    Iterator it2 = std::lower_bound (v.begin (),v.end (), 2,
                                     std::less&lt;int&gt;());

    // Try upper_bound variants.
    Iterator it3 = std::upper_bound (v.begin (), v.end (), 3);
    Iterator it4 = std::upper_bound (v.begin (), v.end (), 2,
                                     std::less&lt;int&gt;());

    std::cout &lt;&lt; "\n\nThe upper and lower bounds of 3: ( "
              &lt;&lt; *it1 &lt;&lt; " , " &lt;&lt; *it3
              &lt;&lt; " ]\n\n\nThe upper and lower bounds of 2: ( "
              &lt;&lt; *it2 &lt;&lt; " , " &lt;&lt; *it4 &lt;&lt; " ]\n";

    return 0;
}


Program Output:
</PRE></UL>
<UL><PRE>

The upper and lower bounds of 3: ( 3 , 4 ]


The upper and lower bounds of 2: ( 2 , 3 ]
</PRE></UL>
<A NAME="sec7"><H3>See Also</H3></A>
<P><SAMP><A HREF="lower-bound.html">lower_bound()</A></SAMP>, <SAMP><A HREF="equal-range.html">equal_range()</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.3.2</I></P>

<BR>
<HR>
<A HREF="unique.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="use-facet.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>