libs/algorithm/doc/html/the_boost_algorithm_library/Misc/find_backward.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>find_backward</title>
   5 <link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
   6 <meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
   7 <link rel="home" href="../../index.html" title="The Boost Algorithm Library">
   8 <link rel="up" href="../../algorithm/Misc.html" title="Other Algorithms">
   9 <link rel="prev" href="find_not.html" title="find_not">
  10 <link rel="next" href="gather.html" title="gather">
  11 </head>
  12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  13 <table cellpadding="2" width="100%"><tr>
  14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
  15 <td align="center"><a href="../../../../../../index.html">Home</a></td>
  16 <td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
  17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  19 <td align="center"><a href="../../../../../../more/index.htm">More</a></td>
  20 </tr></table>
  21 <hr>
  22 <div class="spirit-nav">
  23 <a accesskey="p" href="find_not.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../../algorithm/Misc.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="gather.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h3 class="title">
  27 <a name="the_boost_algorithm_library.Misc.find_backward"></a><a class="link" href="find_backward.html" title="find_backward">find_backward
  28       </a>
  29 </h3></div></div></div>
  30 <p>
  31         The header file 'find_backward.hpp' contains variants of the stl algorithm
  32         <code class="computeroutput"><span class="identifier">find</span></code>. These variants are
  33         like <code class="computeroutput"><span class="identifier">find</span></code>, except that the
  34         evaluate the elements of the given sequence in reverse order.
  35       </p>
  36 <p>
  37         Consider how finding the last element that is equal to <code class="computeroutput"><span class="identifier">x</span></code>
  38         in a range is typically done:
  39       </p>
  40 <pre class="programlisting"><span class="comment">// Assume a valid range if elements delimited by [first, last).</span>
  41 <span class="keyword">while</span> <span class="special">(</span><span class="identifier">last</span><span class="special">--</span> <span class="special">!=</span> <span class="identifier">first</span><span class="special">)</span> <span class="special">{</span>
  42     <span class="keyword">if</span> <span class="special">(*</span><span class="identifier">last</span> <span class="special">==</span> <span class="identifier">x</span><span class="special">)</span> <span class="special">{</span>
  43         <span class="comment">// Use last here...</span>
  44     <span class="special">}</span>
  45 <span class="special">}</span>
  46 </pre>
  47 <p>
  48         Raw loops are icky though. Perhaps we should do a bit of extra work to allow
  49         the use of <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">find</span><span class="special">()</span></code>:
  50       </p>
  51 <pre class="programlisting"><span class="keyword">auto</span> <span class="identifier">rfirst</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">make_reverse_iterator</span><span class="special">(</span><span class="identifier">last</span><span class="special">);</span>
  52 <span class="keyword">auto</span> <span class="identifier">rlast</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">make_reverse_iterator</span><span class="special">(</span><span class="identifier">first</span><span class="special">);</span>
  53 <span class="keyword">auto</span> <span class="identifier">it</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">find</span><span class="special">(</span><span class="identifier">rfirst</span><span class="special">,</span> <span class="identifier">rlast</span><span class="special">,</span> <span class="identifier">x</span><span class="special">);</span>
  54 <span class="comment">// Use it here...</span>
  55 </pre>
  56 <p>
  57         That seems nicer in that there is no raw loop, but it has two major drawbacks.
  58         First, it requires an unpleasant amount of typing. Second, it is less efficient
  59         than forward-iterator <code class="computeroutput"><span class="identifier">find</span></code>
  60         , since <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">reverse_iterator</span></code> calls its base-iterator's
  61         <code class="computeroutput"><span class="keyword">operator</span><span class="special">--()</span></code>
  62         in most of its member functions before doing the work that the member function
  63         requires.
  64       </p>
  65 <h5>
  66 <a name="the_boost_algorithm_library.Misc.find_backward.h0"></a>
  67         <span class="phrase"><a name="the_boost_algorithm_library.Misc.find_backward.interface"></a></span><a class="link" href="find_backward.html#the_boost_algorithm_library.Misc.find_backward.interface">interface</a>
  68       </h5>
  69 <pre class="programlisting"><span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">BidiIter</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">T</span><span class="special">&gt;</span>
  70 <span class="identifier">BidiIter</span> <span class="identifier">find_backward</span><span class="special">(</span><span class="identifier">BidiIter</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">BidiIter</span> <span class="identifier">last</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span> <span class="special">&amp;</span> <span class="identifier">x</span><span class="special">);</span>
  71
  72 <span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">Range</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">T</span><span class="special">&gt;</span>
  73 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special">&lt;</span><span class="identifier">Range</span><span class="special">&gt;</span> <span class="identifier">find_backward</span><span class="special">(</span><span class="identifier">Range</span> <span class="special">&amp;</span> <span class="identifier">range</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span> <span class="special">&amp;</span> <span class="identifier">x</span><span class="special">);</span>
  74 </pre>
  75 <p>
  76         These overloads of <code class="computeroutput"><span class="identifier">find_backward</span></code>
  77         return an iterator to the last element that is equal to <code class="computeroutput"><span class="identifier">x</span></code>
  78         in <code class="computeroutput"><span class="special">[</span><span class="identifier">first</span><span class="special">,</span> <span class="identifier">last</span><span class="special">)</span></code> or <code class="computeroutput"><span class="identifier">r</span></code>,
  79         respectively.
  80       </p>
  81 <pre class="programlisting"><span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">BidiIter</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">T</span><span class="special">&gt;</span>
  82 <span class="identifier">BidiIter</span> <span class="identifier">find_not_backward</span><span class="special">(</span><span class="identifier">BidiIter</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">BidiIter</span> <span class="identifier">last</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span> <span class="special">&amp;</span> <span class="identifier">x</span><span class="special">);</span>
  83
  84 <span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">Range</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">T</span><span class="special">&gt;</span>
  85 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special">&lt;</span><span class="identifier">Range</span><span class="special">&gt;</span> <span class="identifier">find_not_backward</span><span class="special">(</span><span class="identifier">Range</span> <span class="special">&amp;</span> <span class="identifier">range</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span> <span class="special">&amp;</span> <span class="identifier">x</span><span class="special">);</span>
  86 </pre>
  87 <p>
  88         These overloads of <code class="computeroutput"><span class="identifier">find_not_backward</span></code>
  89         return an iterator to the last element that is not equal to <code class="computeroutput"><span class="identifier">x</span></code> in <code class="computeroutput"><span class="special">[</span><span class="identifier">first</span><span class="special">,</span> <span class="identifier">last</span><span class="special">)</span></code> or
  90         <code class="computeroutput"><span class="identifier">r</span></code>, respectively.
  91       </p>
  92 <pre class="programlisting"><span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">BidiIter</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Pred</span><span class="special">&gt;</span>
  93 <span class="identifier">BidiIter</span> <span class="identifier">find_if_backward</span><span class="special">(</span><span class="identifier">BidiIter</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">BidiIter</span> <span class="identifier">last</span><span class="special">,</span> <span class="identifier">Pred</span> <span class="identifier">p</span><span class="special">);</span>
  94
  95 <span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">Range</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Pred</span><span class="special">&gt;</span>
  96 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special">&lt;</span><span class="identifier">Range</span><span class="special">&gt;</span> <span class="identifier">find_if_backward</span><span class="special">(</span><span class="identifier">Range</span> <span class="special">&amp;</span> <span class="identifier">range</span><span class="special">,</span> <span class="identifier">Pred</span> <span class="identifier">p</span><span class="special">);</span>
  97 </pre>
  98 <p>
  99         These overloads of <code class="computeroutput"><span class="identifier">find_if_backward</span></code>
 100         return an iterator to the last element for which <code class="computeroutput"><span class="identifier">pred</span></code>
 101         returns <code class="computeroutput"><span class="keyword">true</span></code> in <code class="computeroutput"><span class="special">[</span><span class="identifier">first</span><span class="special">,</span> <span class="identifier">last</span><span class="special">)</span></code> or <code class="computeroutput"><span class="identifier">r</span></code>,
 102         respectively.
 103       </p>
 104 <pre class="programlisting"><span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">BidiIter</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Pred</span><span class="special">&gt;</span>
 105 <span class="identifier">BidiIter</span> <span class="identifier">find_if_not_backward</span><span class="special">(</span><span class="identifier">BidiIter</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">BidiIter</span> <span class="identifier">last</span><span class="special">,</span> <span class="identifier">Pred</span> <span class="identifier">p</span><span class="special">);</span>
 106
 107 <span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">Range</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Pred</span><span class="special">&gt;</span>
 108 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special">&lt;</span><span class="identifier">Range</span><span class="special">&gt;</span> <span class="identifier">find_if_not_backward</span><span class="special">(</span><span class="identifier">Range</span> <span class="special">&amp;</span> <span class="identifier">range</span><span class="special">,</span> <span class="identifier">Pred</span> <span class="identifier">p</span><span class="special">);</span>
 109 </pre>
 110 <p>
 111         These overloads of <code class="computeroutput"><span class="identifier">find_if_not_backward</span></code>
 112         return an iterator to the last element for which <code class="computeroutput"><span class="identifier">pred</span></code>
 113         returns <code class="computeroutput"><span class="keyword">false</span></code> in <code class="computeroutput"><span class="special">[</span><span class="identifier">first</span><span class="special">,</span> <span class="identifier">last</span><span class="special">)</span></code> or <code class="computeroutput"><span class="identifier">r</span></code>,
 114         respectively.
 115       </p>
 116 <h5>
 117 <a name="the_boost_algorithm_library.Misc.find_backward.h1"></a>
 118         <span class="phrase"><a name="the_boost_algorithm_library.Misc.find_backward.examples"></a></span><a class="link" href="find_backward.html#the_boost_algorithm_library.Misc.find_backward.examples">Examples</a>
 119       </h5>
 120 <p>
 121         Given the container <code class="computeroutput"><span class="identifier">c1</span></code> containing
 122         <code class="computeroutput"><span class="special">{</span> <span class="number">2</span><span class="special">,</span> <span class="number">1</span><span class="special">,</span>
 123         <span class="number">2</span> <span class="special">}</span></code>,
 124         then
 125       </p>
 126 <pre class="programlisting"><span class="identifier">find_backward</span>        <span class="special">(</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="number">2</span>                          <span class="special">)</span> <span class="special">--&gt;</span> <span class="special">--</span><span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">()</span>
 127 <span class="identifier">find_backward</span>        <span class="special">(</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="number">3</span>                          <span class="special">)</span> <span class="special">--&gt;</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">()</span>
 128 <span class="identifier">find_if_backward</span>     <span class="special">(</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="special">[](</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">)</span> <span class="special">{</span><span class="keyword">return</span> <span class="identifier">i</span> <span class="special">==</span> <span class="number">2</span><span class="special">;}</span> <span class="special">)</span> <span class="special">--&gt;</span> <span class="special">--</span><span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">()</span>
 129 <span class="identifier">find_if_backward</span>     <span class="special">(</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="special">[](</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">)</span> <span class="special">{</span><span class="keyword">return</span> <span class="identifier">i</span> <span class="special">==</span> <span class="number">3</span><span class="special">;}</span> <span class="special">)</span> <span class="special">--&gt;</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">()</span>
 130 <span class="identifier">find_not_backward</span>    <span class="special">(</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="number">2</span>                          <span class="special">)</span> <span class="special">--&gt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">prev</span><span class="special">(</span><span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="number">2</span><span class="special">)</span>
 131 <span class="identifier">find_not_backward</span>    <span class="special">(</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="number">1</span>                          <span class="special">)</span> <span class="special">--&gt;</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">()</span>
 132 <span class="identifier">find_if_not_backward</span> <span class="special">(</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="special">[](</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">)</span> <span class="special">{</span><span class="keyword">return</span> <span class="identifier">i</span> <span class="special">==</span> <span class="number">2</span><span class="special">;}</span> <span class="special">)</span> <span class="special">--&gt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">prev</span><span class="special">(</span><span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="number">2</span><span class="special">)</span>
 133 <span class="identifier">find_if_not_backward</span> <span class="special">(</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="special">[](</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">)</span> <span class="special">{</span><span class="keyword">return</span> <span class="identifier">i</span> <span class="special">==</span> <span class="number">1</span><span class="special">;}</span> <span class="special">)</span> <span class="special">--&gt;</span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">()</span>
 134 </pre>
 135 <h5>
 136 <a name="the_boost_algorithm_library.Misc.find_backward.h2"></a>
 137         <span class="phrase"><a name="the_boost_algorithm_library.Misc.find_backward.iterator_requirements"></a></span><a class="link" href="find_backward.html#the_boost_algorithm_library.Misc.find_backward.iterator_requirements">Iterator
 138         Requirements</a>
 139       </h5>
 140 <p>
 141         All variants work on bidirectional iterators.
 142       </p>
 143 <h5>
 144 <a name="the_boost_algorithm_library.Misc.find_backward.h3"></a>
 145         <span class="phrase"><a name="the_boost_algorithm_library.Misc.find_backward.complexity"></a></span><a class="link" href="find_backward.html#the_boost_algorithm_library.Misc.find_backward.complexity">Complexity</a>
 146       </h5>
 147 <p>
 148         Linear.
 149       </p>
 150 <h5>
 151 <a name="the_boost_algorithm_library.Misc.find_backward.h4"></a>
 152         <span class="phrase"><a name="the_boost_algorithm_library.Misc.find_backward.exception_safety"></a></span><a class="link" href="find_backward.html#the_boost_algorithm_library.Misc.find_backward.exception_safety">Exception
 153         Safety</a>
 154       </h5>
 155 <p>
 156         All of the variants take their parameters by value and do not depend upon
 157         any global state. Therefore, all the routines in this file provide the strong
 158         exception guarantee.
 159       </p>
 160 <h5>
 161 <a name="the_boost_algorithm_library.Misc.find_backward.h5"></a>
 162         <span class="phrase"><a name="the_boost_algorithm_library.Misc.find_backward.notes"></a></span><a class="link" href="find_backward.html#the_boost_algorithm_library.Misc.find_backward.notes">Notes</a>
 163       </h5>
 164 <p>
 165         All variants are <code class="computeroutput"><span class="keyword">constexpr</span></code> in
 166         C++14 or later.
 167       </p>
 168 </div>
 169 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 170 <td align="left"></td>
 171 <td align="right"><div class="copyright-footer">Copyright &#169; 2010-2012 Marshall Clow<p>
 172         Distributed under the Boost Software License, Version 1.0. (See accompanying
 173         file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
 174       </p>
 175 </div></td>
 176 </tr></table>
 177 <hr>
 178 <div class="spirit-nav">
 179 <a accesskey="p" href="find_not.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../../algorithm/Misc.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="gather.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
 180 </div>
 181 </body>
 182 </html>