1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Other Algorithms</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="../index.html" title="The Boost Algorithm Library"> 9<link rel="prev" href="CXX17.html" title="C++17 Algorithms"> 10<link rel="next" href="not_yet_documented_cxx17_algos.html" title="Not-yet-documented C++17 Algorithms"> 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="CXX17.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.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="not_yet_documented_cxx17_algos.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 27<a name="algorithm.Misc"></a><a class="link" href="Misc.html" title="Other Algorithms">Other Algorithms</a> 28</h2></div></div></div> 29<div class="toc"><dl class="toc"> 30<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms"></a></span></dt> 31<dd><dl> 32<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.none_of_equal">none_of_equal 33 </a></span></dt> 34<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.one_of_equal">one_of_equal 35 </a></span></dt> 36<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.is_decreasing">is_decreasing 37 </a></span></dt> 38<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.is_increasing">is_increasing 39 </a></span></dt> 40<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.is_strictly_decreasing">is_strictly_decreasing 41 </a></span></dt> 42<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.is_strictly_increasing">is_strictly_increasing 43 </a></span></dt> 44<dt><span class="section"><a href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.clamp">clamp</a></span></dt> 45<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.clamp_range">clamp_range 46 </a></span></dt> 47<dt><span class="section"><a href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not">find_not 48 </a></span></dt> 49<dt><span class="section"><a href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward">find_backward 50 </a></span></dt> 51<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.find_not_backward">find_not_backward 52 </a></span></dt> 53<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.find_if_backward">find_if_backward 54 </a></span></dt> 55<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.find_if_not">find_if_not 56 </a></span></dt> 57<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.find_if_not_backward">find_if_not_backward 58 </a></span></dt> 59<dt><span class="section"><a href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.gather">gather</a></span></dt> 60<dt><span class="section"><a href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.hex">hex</a></span></dt> 61<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.unhex">unhex 62 </a></span></dt> 63<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.hex_lower">hex_lower 64 </a></span></dt> 65<dt><span class="section"><a href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome">is_palindrome</a></span></dt> 66<dt><span class="section"><a href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until">is_partitioned_until 67 </a></span></dt> 68<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.apply_reverse_permutation">apply_reverse_permutation 69 </a></span></dt> 70<dt><span class="section"><a href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation">apply_permutation</a></span></dt> 71<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.copy_until">copy_until 72 </a></span></dt> 73<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.copy_while">copy_while 74 </a></span></dt> 75<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.iota_n">iota_n 76 </a></span></dt> 77<dt><span class="section"><a href="Misc.html#algorithm.Misc.misc_inner_algorithms.power">power 78 </a></span></dt> 79</dl></dd> 80</dl></div> 81<div class="section"> 82<div class="titlepage"></div> 83<div class="section"> 84<div class="titlepage"><div><div><h4 class="title"> 85<a name="algorithm.Misc.misc_inner_algorithms.none_of_equal"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.none_of_equal" title="none_of_equal">none_of_equal 86 </a> 87</h4></div></div></div> 88<p> 89 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/cxx11/none_of_hpp.html" title="Header <boost/algorithm/cxx11/none_of.hpp>">none_of_equal</a> 90 </code> </strong></span> Whether none of a range's elements matches a value 91 </p> 92</div> 93<div class="section"> 94<div class="titlepage"><div><div><h4 class="title"> 95<a name="algorithm.Misc.misc_inner_algorithms.one_of_equal"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.one_of_equal" title="one_of_equal">one_of_equal 96 </a> 97</h4></div></div></div> 98<p> 99 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/cxx11/one_of_hpp.html" title="Header <boost/algorithm/cxx11/one_of.hpp>">one_of_equal</a> 100 </code> </strong></span> Whether only one of a range's elements matches a 101 value 102 </p> 103</div> 104<div class="section"> 105<div class="titlepage"><div><div><h4 class="title"> 106<a name="algorithm.Misc.misc_inner_algorithms.is_decreasing"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.is_decreasing" title="is_decreasing">is_decreasing 107 </a> 108</h4></div></div></div> 109<p> 110 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/cxx11/is_sorted_hpp.html" title="Header <boost/algorithm/cxx11/is_sorted.hpp>">is_decreasing</a> 111 </code> </strong></span> Whether an entire sequence is decreasing; i.e, each 112 item is less than or equal to the previous one 113 </p> 114</div> 115<div class="section"> 116<div class="titlepage"><div><div><h4 class="title"> 117<a name="algorithm.Misc.misc_inner_algorithms.is_increasing"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.is_increasing" title="is_increasing">is_increasing 118 </a> 119</h4></div></div></div> 120<p> 121 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/cxx11/is_sorted_hpp.html" title="Header <boost/algorithm/cxx11/is_sorted.hpp>">is_increasing</a> 122 </code> </strong></span> Whether an entire sequence is increasing; i.e, each 123 item is greater than or equal to the previous one 124 </p> 125</div> 126<div class="section"> 127<div class="titlepage"><div><div><h4 class="title"> 128<a name="algorithm.Misc.misc_inner_algorithms.is_strictly_decreasing"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.is_strictly_decreasing" title="is_strictly_decreasing">is_strictly_decreasing 129 </a> 130</h4></div></div></div> 131<p> 132 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/cxx11/is_sorted_hpp.html" title="Header <boost/algorithm/cxx11/is_sorted.hpp>">is_strictly_decreasing</a> 133 </code> </strong></span> Whether an entire sequence is strictly decreasing; 134 i.e, each item is less than the previous one 135 </p> 136</div> 137<div class="section"> 138<div class="titlepage"><div><div><h4 class="title"> 139<a name="algorithm.Misc.misc_inner_algorithms.is_strictly_increasing"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.is_strictly_increasing" title="is_strictly_increasing">is_strictly_increasing 140 </a> 141</h4></div></div></div> 142<p> 143 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/cxx11/is_sorted_hpp.html" title="Header <boost/algorithm/cxx11/is_sorted.hpp>">is_strictly_increasing</a> 144 </code> </strong></span> Whether an entire sequence is strictly increasing; 145 i.e, each item is greater than the previous one 146 </p> 147</div> 148<div class="section"> 149<div class="titlepage"><div><div><h4 class="title"> 150<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.clamp"></a><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.clamp" title="clamp">clamp</a> 151</h4></div></div></div> 152<p> 153 The header file clamp.hpp contains two functions for "clamping" 154 a value between a pair of boundary values. 155 </p> 156<h6> 157<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.clamp.h0"></a> 158 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.clamp.clamp"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.clamp.clamp">clamp</a> 159 </h6> 160<p> 161 The function <code class="computeroutput"><span class="identifier">clamp</span> <span class="special">(</span><span class="identifier">v</span><span class="special">,</span> <span class="identifier">lo</span><span class="special">,</span> <span class="identifier">hi</span><span class="special">)</span></code> returns: 162 </p> 163<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 164<li class="listitem"> 165 lo if v < lo 166 </li> 167<li class="listitem"> 168 hi if hi < v 169 </li> 170<li class="listitem"> 171 otherwise, v 172 </li> 173</ul></div> 174<p> 175 Note: using <code class="computeroutput"><span class="identifier">clamp</span></code> with 176 floating point numbers may give unexpected results if one of the values 177 is <code class="computeroutput"><span class="identifier">NaN</span></code>. 178 </p> 179<p> 180 There is also a version that allows the caller to specify a comparison 181 predicate to use instead of <code class="computeroutput"><span class="keyword">operator</span> 182 <span class="special"><</span></code>. 183 </p> 184<p> 185</p> 186<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">T</span><span class="special">></span> 187<span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">clamp</span> <span class="special">(</span> <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">val</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">lo</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">hi</span> <span class="special">);</span> 188 189<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Pred</span><span class="special">></span> 190<span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">clamp</span> <span class="special">(</span> <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">val</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">lo</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span> <span class="identifier">hi</span><span class="special">,</span> <span class="identifier">Pred</span> <span class="identifier">p</span> <span class="special">);</span> 191</pre> 192<p> 193 </p> 194<p> 195 The following code: 196</p> 197<pre class="programlisting"><span class="keyword">int</span> <span class="identifier">foo</span> <span class="special">=</span> <span class="number">23</span><span class="special">;</span> 198<span class="identifier">foo</span> <span class="special">=</span> <span class="identifier">clamp</span> <span class="special">(</span> <span class="identifier">foo</span><span class="special">,</span> <span class="number">1</span><span class="special">,</span> <span class="number">10</span> <span class="special">);</span> 199</pre> 200<p> 201 will leave <code class="computeroutput"><span class="identifier">foo</span></code> with a value 202 of 10 203 </p> 204<p> 205 Complexity: <code class="computeroutput"><span class="identifier">clamp</span></code> will 206 make either one or two calls to the comparison predicate before returning 207 one of the three parameters. 208 </p> 209<h6> 210<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.clamp.h1"></a> 211 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.clamp.clamp_range"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.clamp.clamp_range">clamp_range</a> 212 </h6> 213<p> 214 There are also four range-based versions of clamp, that apply clamping 215 to a series of values. You could write them yourself with std::transform 216 and bind, like this: <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">transform</span> 217 <span class="special">(</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">last</span><span class="special">,</span> <span class="identifier">out</span><span class="special">,</span> <span class="identifier">bind</span> <span class="special">(</span> <span class="identifier">clamp</span> <span class="special">(</span> <span class="identifier">_1</span><span class="special">,</span> <span class="identifier">lo</span><span class="special">,</span> <span class="identifier">hi</span> <span class="special">)))</span></code>, but they are provided here for your 218 convenience. 219 </p> 220<p> 221</p> 222<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">InputIterator</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">OutputIterator</span><span class="special">></span> 223<span class="identifier">OutputIterator</span> <span class="identifier">clamp_range</span> <span class="special">(</span> <span class="identifier">InputIterator</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">InputIterator</span> <span class="identifier">last</span><span class="special">,</span> <span class="identifier">OutputIterator</span> <span class="identifier">out</span><span class="special">,</span> 224 <span class="keyword">typename</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="identifier">InputIterator</span><span class="special">>::</span><span class="identifier">value_type</span> <span class="identifier">lo</span><span class="special">,</span> 225 <span class="keyword">typename</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="identifier">InputIterator</span><span class="special">>::</span><span class="identifier">value_type</span> <span class="identifier">hi</span> <span class="special">);</span> 226 227<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">Range</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">OutputIterator</span><span class="special">></span> 228<span class="identifier">OutputIterator</span> <span class="identifier">clamp_range</span> <span class="special">(</span> <span class="keyword">const</span> <span class="identifier">Range</span> <span class="special">&</span><span class="identifier">r</span><span class="special">,</span> <span class="identifier">OutputIterator</span> <span class="identifier">out</span><span class="special">,</span> 229 <span class="keyword">typename</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special"><</span><span class="keyword">const</span> <span class="identifier">Range</span><span class="special">>::</span><span class="identifier">type</span><span class="special">>::</span><span class="identifier">value_type</span> <span class="identifier">lo</span><span class="special">,</span> 230 <span class="keyword">typename</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special"><</span><span class="keyword">const</span> <span class="identifier">Range</span><span class="special">>::</span><span class="identifier">type</span><span class="special">>::</span><span class="identifier">value_type</span> <span class="identifier">hi</span> <span class="special">);</span> 231 232<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">InputIterator</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">OutputIterator</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Pred</span><span class="special">></span> 233<span class="identifier">OutputIterator</span> <span class="identifier">clamp_range</span> <span class="special">(</span> <span class="identifier">InputIterator</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">InputIterator</span> <span class="identifier">last</span><span class="special">,</span> <span class="identifier">OutputIterator</span> <span class="identifier">out</span><span class="special">,</span> 234 <span class="keyword">typename</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="identifier">InputIterator</span><span class="special">>::</span><span class="identifier">value_type</span> <span class="identifier">lo</span><span class="special">,</span> 235 <span class="keyword">typename</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="identifier">InputIterator</span><span class="special">>::</span><span class="identifier">value_type</span> <span class="identifier">hi</span><span class="special">,</span> <span class="identifier">Pred</span> <span class="identifier">p</span> <span class="special">);</span> 236 237<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">Range</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">OutputIterator</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Pred</span><span class="special">></span> 238<span class="identifier">OutputIterator</span> <span class="identifier">clamp_range</span> <span class="special">(</span> <span class="keyword">const</span> <span class="identifier">Range</span> <span class="special">&</span><span class="identifier">r</span><span class="special">,</span> <span class="identifier">OutputIterator</span> <span class="identifier">out</span><span class="special">,</span> 239 <span class="keyword">typename</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special"><</span><span class="keyword">const</span> <span class="identifier">Range</span><span class="special">>::</span><span class="identifier">type</span><span class="special">>::</span><span class="identifier">value_type</span> <span class="identifier">lo</span><span class="special">,</span> 240 <span class="keyword">typename</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special"><</span><span class="keyword">const</span> <span class="identifier">Range</span><span class="special">>::</span><span class="identifier">type</span><span class="special">>::</span><span class="identifier">value_type</span> <span class="identifier">hi</span><span class="special">,</span> 241 <span class="identifier">Pred</span> <span class="identifier">p</span> <span class="special">);</span> 242</pre> 243<p> 244 </p> 245</div> 246<div class="section"> 247<div class="titlepage"><div><div><h4 class="title"> 248<a name="algorithm.Misc.misc_inner_algorithms.clamp_range"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.clamp_range" title="clamp_range">clamp_range 249 </a> 250</h4></div></div></div> 251<p> 252 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/clamp_hpp.html" title="Header <boost/algorithm/clamp.hpp>">clamp_range</a> 253 </code> </strong></span> Perform <code class="literal">clamp</code> on the elements 254 of a range and write the results into an output iterator 255 </p> 256</div> 257<div class="section"> 258<div class="titlepage"><div><div><h4 class="title"> 259<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not"></a><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not" title="find_not">find_not 260 </a> 261</h4></div></div></div> 262<p> 263 The header file 'find_not.hpp' contains a variants of a the stl algorithm 264 <code class="computeroutput"><span class="identifier">find</span></code>. The algorithm finds 265 the first value in the given sequence that is not equal to the given value. 266 </p> 267<p> 268 Consider this use of <code class="computeroutput"><span class="identifier">find</span><span class="special">()</span></code>: 269 </p> 270<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="keyword">int</span><span class="special">></span> <span class="identifier">vec</span> <span class="special">=</span> <span class="special">{</span> <span class="number">1</span><span class="special">,</span> <span class="number">1</span><span class="special">,</span> <span class="number">2</span> <span class="special">};</span> 271<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">vec</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">vec</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="number">1</span><span class="special">);</span> 272</pre> 273<p> 274 This gives us the first occurance of <code class="computeroutput"><span class="number">1</span></code> 275 in <code class="computeroutput"><span class="identifier">vec</span></code>. What if we want 276 to find the first occurrance of any number besides <code class="computeroutput"><span class="number">1</span></code> 277 in <code class="computeroutput"><span class="identifier">vec</span></code>? We have to write 278 an unfortunate amount of code: 279 </p> 280<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="keyword">int</span><span class="special">></span> <span class="identifier">vec</span> <span class="special">=</span> <span class="special">{</span> <span class="number">1</span><span class="special">,</span> <span class="number">1</span><span class="special">,</span> <span class="number">2</span> <span class="special">};</span> 281<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_if</span><span class="special">(</span><span class="identifier">vec</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">vec</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> 282</pre> 283<p> 284 With <code class="computeroutput"><span class="identifier">find_not</span><span class="special">()</span></code> 285 the code gets much more terse: 286 </p> 287<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="keyword">int</span><span class="special">></span> <span class="identifier">vec</span> <span class="special">=</span> <span class="special">{</span> <span class="number">1</span><span class="special">,</span> <span class="number">1</span><span class="special">,</span> <span class="number">2</span> <span class="special">};</span> 288<span class="keyword">auto</span> <span class="identifier">it</span> <span class="special">=</span> <span class="identifier">find_not</span><span class="special">(</span><span class="identifier">vec</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">vec</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="number">1</span><span class="special">);</span> 289</pre> 290<p> 291 The existing <code class="computeroutput"><span class="identifier">find</span></code> variants 292 are: <code class="computeroutput"><span class="identifier">find</span><span class="special">()</span></code>, 293 <code class="computeroutput"><span class="identifier">find_if</span><span class="special">()</span></code>, 294 and <code class="computeroutput"><span class="identifier">find_if_not</span><span class="special">()</span></code>. 295 It seems natural to also have <code class="computeroutput"><span class="identifier">find_not</span><span class="special">()</span></code>, for the very reason that we have <code class="computeroutput"><span class="identifier">find_if_not</span><span class="special">()</span></code> 296 -- to avoid having to write a lambda to wrap the negation of the find condition. 297 </p> 298<h6> 299<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.h0"></a> 300 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.interface"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.interface">interface</a> 301 </h6> 302<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">InputIter</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Sentinel</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">T</span><span class="special">></span> 303<span class="identifier">InputIter</span> <span class="identifier">find_not</span><span class="special">(</span><span class="identifier">InputIter</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">Sentinel</span> <span class="identifier">last</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span> <span class="special">&</span> <span class="identifier">x</span><span class="special">);</span> 304 305<span class="keyword">template</span><span class="special"><</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">></span> 306<span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special"><</span><span class="identifier">Range</span><span class="special">></span> <span class="identifier">find_not</span><span class="special">(</span><span class="identifier">Range</span> <span class="special">&</span> <span class="identifier">r</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span> <span class="special">&</span> <span class="identifier">x</span><span class="special">);</span> 307</pre> 308<p> 309 These overloads of <code class="computeroutput"><span class="identifier">find_not</span></code> 310 return the first value that is not equal to <code class="computeroutput"><span class="identifier">x</span></code> 311 in the sequence <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>, 312 respectively. 313 </p> 314<h6> 315<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.h1"></a> 316 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.examples"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.examples">Examples</a> 317 </h6> 318<p> 319 Given the container <code class="computeroutput"><span class="identifier">c1</span></code> 320 containing <code class="computeroutput"><span class="special">{</span> <span class="number">0</span><span class="special">,</span> <span class="number">1</span><span class="special">,</span> 321 <span class="number">2</span> <span class="special">}</span></code>, 322 then 323 </p> 324<pre class="programlisting"><span class="identifier">find_not</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">--></span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()</span> 325<span class="identifier">find_not</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">0</span> <span class="special">)</span> <span class="special">--></span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">next</span><span class="special">(</span><span class="identifier">c1</span><span class="special">.</span><span class="identifier">begin</span><span class="special">())</span> 326</pre> 327<h6> 328<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.h2"></a> 329 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.iterator_requirements"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.iterator_requirements">Iterator 330 Requirements</a> 331 </h6> 332<p> 333 <code class="computeroutput"><span class="identifier">find_not</span></code> works on all iterators 334 except output iterators. 335 </p> 336<p> 337 The template parameter <code class="computeroutput"><span class="identifier">Sentinel</span></code> 338 is allowed to be different from <code class="computeroutput"><span class="identifier">InputIter</span></code>, 339 or they may be the same. For an <code class="computeroutput"><span class="identifier">InputIter</span></code> 340 <code class="computeroutput"><span class="identifier">it</span></code> and a <code class="computeroutput"><span class="identifier">Sentinel</span></code> <code class="computeroutput"><span class="identifier">end</span></code>, 341 <code class="computeroutput"><span class="identifier">it</span> <span class="special">==</span> 342 <span class="identifier">end</span></code> and <code class="computeroutput"><span class="identifier">it</span> 343 <span class="special">!=</span> <span class="identifier">end</span></code> 344 must be well-formed expressions. 345 </p> 346<h6> 347<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.h3"></a> 348 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.complexity"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.complexity">Complexity</a> 349 </h6> 350<p> 351 Linear. 352 </p> 353<h6> 354<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.h4"></a> 355 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.exception_safety"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.exception_safety">Exception 356 Safety</a> 357 </h6> 358<p> 359 <code class="computeroutput"><span class="identifier">find_not</span></code> takes its parameters 360 by value and do not depend upon any global state. Therefore, it provides 361 the strong exception guarantee. 362 </p> 363<h6> 364<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.h5"></a> 365 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.notes"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not.notes">Notes</a> 366 </h6> 367<p> 368 <code class="computeroutput"><span class="keyword">constexpr</span></code> in C++14 or later. 369 </p> 370</div> 371<div class="section"> 372<div class="titlepage"><div><div><h4 class="title"> 373<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward"></a><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward" title="find_backward">find_backward 374 </a> 375</h4></div></div></div> 376<p> 377 The header file 'find_backward.hpp' contains variants of the stl algorithm 378 <code class="computeroutput"><span class="identifier">find</span></code>. These variants are 379 like <code class="computeroutput"><span class="identifier">find</span></code>, except that 380 the evaluate the elements of the given sequence in reverse order. 381 </p> 382<p> 383 Consider how finding the last element that is equal to <code class="computeroutput"><span class="identifier">x</span></code> 384 in a range is typically done: 385 </p> 386<pre class="programlisting"><span class="comment">// Assume a valid range if elements delimited by [first, last).</span> 387<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> 388 <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> 389 <span class="comment">// Use last here...</span> 390 <span class="special">}</span> 391<span class="special">}</span> 392</pre> 393<p> 394 Raw loops are icky though. Perhaps we should do a bit of extra work to 395 allow 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>: 396 </p> 397<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> 398<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> 399<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> 400<span class="comment">// Use it here...</span> 401</pre> 402<p> 403 That seems nicer in that there is no raw loop, but it has two major drawbacks. 404 First, it requires an unpleasant amount of typing. Second, it is less efficient 405 than forward-iterator <code class="computeroutput"><span class="identifier">find</span></code> 406 , 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 407 <code class="computeroutput"><span class="keyword">operator</span><span class="special">--()</span></code> 408 in most of its member functions before doing the work that the member function 409 requires. 410 </p> 411<h6> 412<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.h0"></a> 413 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.interface"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.interface">interface</a> 414 </h6> 415<pre class="programlisting"><span class="keyword">template</span><span class="special"><</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">></span> 416<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">&</span> <span class="identifier">x</span><span class="special">);</span> 417 418<span class="keyword">template</span><span class="special"><</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">></span> 419<span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special"><</span><span class="identifier">Range</span><span class="special">></span> <span class="identifier">find_backward</span><span class="special">(</span><span class="identifier">Range</span> <span class="special">&</span> <span class="identifier">range</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span> <span class="special">&</span> <span class="identifier">x</span><span class="special">);</span> 420</pre> 421<p> 422 These overloads of <code class="computeroutput"><span class="identifier">find_backward</span></code> 423 return an iterator to the last element that is equal to <code class="computeroutput"><span class="identifier">x</span></code> 424 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>, 425 respectively. 426 </p> 427<pre class="programlisting"><span class="keyword">template</span><span class="special"><</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">></span> 428<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">&</span> <span class="identifier">x</span><span class="special">);</span> 429 430<span class="keyword">template</span><span class="special"><</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">></span> 431<span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special"><</span><span class="identifier">Range</span><span class="special">></span> <span class="identifier">find_not_backward</span><span class="special">(</span><span class="identifier">Range</span> <span class="special">&</span> <span class="identifier">range</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span> <span class="special">&</span> <span class="identifier">x</span><span class="special">);</span> 432</pre> 433<p> 434 These overloads of <code class="computeroutput"><span class="identifier">find_not_backward</span></code> 435 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> 436 or <code class="computeroutput"><span class="identifier">r</span></code>, respectively. 437 </p> 438<pre class="programlisting"><span class="keyword">template</span><span class="special"><</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">></span> 439<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> 440 441<span class="keyword">template</span><span class="special"><</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">></span> 442<span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special"><</span><span class="identifier">Range</span><span class="special">></span> <span class="identifier">find_if_backward</span><span class="special">(</span><span class="identifier">Range</span> <span class="special">&</span> <span class="identifier">range</span><span class="special">,</span> <span class="identifier">Pred</span> <span class="identifier">p</span><span class="special">);</span> 443</pre> 444<p> 445 These overloads of <code class="computeroutput"><span class="identifier">find_if_backward</span></code> 446 return an iterator to the last element for which <code class="computeroutput"><span class="identifier">pred</span></code> 447 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>, 448 respectively. 449 </p> 450<pre class="programlisting"><span class="keyword">template</span><span class="special"><</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">></span> 451<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> 452 453<span class="keyword">template</span><span class="special"><</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">></span> 454<span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special"><</span><span class="identifier">Range</span><span class="special">></span> <span class="identifier">find_if_not_backward</span><span class="special">(</span><span class="identifier">Range</span> <span class="special">&</span> <span class="identifier">range</span><span class="special">,</span> <span class="identifier">Pred</span> <span class="identifier">p</span><span class="special">);</span> 455</pre> 456<p> 457 These overloads of <code class="computeroutput"><span class="identifier">find_if_not_backward</span></code> 458 return an iterator to the last element for which <code class="computeroutput"><span class="identifier">pred</span></code> 459 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>, 460 respectively. 461 </p> 462<h6> 463<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.h1"></a> 464 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.examples"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.examples">Examples</a> 465 </h6> 466<p> 467 Given the container <code class="computeroutput"><span class="identifier">c1</span></code> 468 containing <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> 469 <span class="number">2</span> <span class="special">}</span></code>, 470 then 471 </p> 472<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">--></span> <span class="special">--</span><span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">()</span> 473<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">--></span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">()</span> 474<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">--></span> <span class="special">--</span><span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">()</span> 475<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">--></span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">()</span> 476<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">--></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> 477<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">--></span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">()</span> 478<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">--></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> 479<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">--></span> <span class="identifier">c1</span><span class="special">.</span><span class="identifier">end</span><span class="special">()</span> 480</pre> 481<h6> 482<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.h2"></a> 483 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.iterator_requirements"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.iterator_requirements">Iterator 484 Requirements</a> 485 </h6> 486<p> 487 All variants work on bidirectional iterators. 488 </p> 489<h6> 490<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.h3"></a> 491 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.complexity"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.complexity">Complexity</a> 492 </h6> 493<p> 494 Linear. 495 </p> 496<h6> 497<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.h4"></a> 498 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.exception_safety"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.exception_safety">Exception 499 Safety</a> 500 </h6> 501<p> 502 All of the variants take their parameters by value and do not depend upon 503 any global state. Therefore, all the routines in this file provide the 504 strong exception guarantee. 505 </p> 506<h6> 507<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.h5"></a> 508 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.notes"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward.notes">Notes</a> 509 </h6> 510<p> 511 All variants are <code class="computeroutput"><span class="keyword">constexpr</span></code> 512 in C++14 or later. 513 </p> 514</div> 515<div class="section"> 516<div class="titlepage"><div><div><h4 class="title"> 517<a name="algorithm.Misc.misc_inner_algorithms.find_not_backward"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.find_not_backward" title="find_not_backward">find_not_backward 518 </a> 519</h4></div></div></div> 520<p> 521 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/find_backward_hpp.html" title="Header <boost/algorithm/find_backward.hpp>">find_not_backward</a> 522 </code> </strong></span> Find the last element in a sequence that does not 523 equal a value. See <a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward" title="find_backward">find_backward</a>. 524 </p> 525</div> 526<div class="section"> 527<div class="titlepage"><div><div><h4 class="title"> 528<a name="algorithm.Misc.misc_inner_algorithms.find_if_backward"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.find_if_backward" title="find_if_backward">find_if_backward 529 </a> 530</h4></div></div></div> 531<p> 532 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/find_backward_hpp.html" title="Header <boost/algorithm/find_backward.hpp>">find_if_backward</a> 533 </code> </strong></span> Find the last element in a sequence that satisfies 534 a predicate. See <a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward" title="find_backward">find_backward</a>. 535 </p> 536</div> 537<div class="section"> 538<div class="titlepage"><div><div><h4 class="title"> 539<a name="algorithm.Misc.misc_inner_algorithms.find_if_not"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.find_if_not" title="find_if_not">find_if_not 540 </a> 541</h4></div></div></div> 542<p> 543 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/cxx11/find_if_not_hpp.html" title="Header <boost/algorithm/cxx11/find_if_not.hpp>">find_if_not</a> 544 </code> </strong></span> Find the first element in a sequence that does not 545 satisfy a predicate. See <a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not" title="find_not">find_not</a>. 546 </p> 547</div> 548<div class="section"> 549<div class="titlepage"><div><div><h4 class="title"> 550<a name="algorithm.Misc.misc_inner_algorithms.find_if_not_backward"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.find_if_not_backward" title="find_if_not_backward">find_if_not_backward 551 </a> 552</h4></div></div></div> 553<p> 554 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/find_backward_hpp.html" title="Header <boost/algorithm/find_backward.hpp>">find_if_not_backward</a> 555 </code> </strong></span> Find the last element in a sequence that does not 556 satisfy a predicate. See <a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward" title="find_backward">find_backward</a>. 557 </p> 558</div> 559<div class="section"> 560<div class="titlepage"><div><div><h4 class="title"> 561<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather"></a><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.gather" title="gather">gather</a> 562</h4></div></div></div> 563<p> 564 The header file 'boost/algorithm/gather.hpp' contains two variants of a 565 single algorithm, <code class="computeroutput"><span class="identifier">gather</span></code>. 566 </p> 567<p> 568 <code class="computeroutput"><span class="identifier">gather</span><span class="special">()</span></code> 569 takes a collection of elements defined by a pair of iterators and moves 570 the ones satisfying a predicate to them to a position (called the pivot) 571 within the sequence. The algorithm is stable. The result is a pair of iterators 572 that contains the items that satisfy the predicate. 573 </p> 574<h6> 575<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.h0"></a> 576 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.interface"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.interface">Interface</a> 577 </h6> 578<p> 579 The function <code class="computeroutput"><span class="identifier">gather</span></code> returns 580 a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span></code> of iterators that denote the elements 581 that satisfy the predicate. 582 </p> 583<p> 584 There are two versions; one takes two iterators, and the other takes a 585 range. 586 </p> 587<p> 588</p> 589<pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span> <span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">algorithm</span> <span class="special">{</span> 590 591<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">BidirectionalIterator</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Pred</span><span class="special">></span> 592<span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span><span class="identifier">BidirectionalIterator</span><span class="special">,</span><span class="identifier">BidirectionalIterator</span><span class="special">></span> 593<span class="identifier">gather</span> <span class="special">(</span> <span class="identifier">BidirectionalIterator</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">BidirectionalIterator</span> <span class="identifier">last</span><span class="special">,</span> <span class="identifier">BidirectionalIterator</span> <span class="identifier">pivot</span><span class="special">,</span> <span class="identifier">Pred</span> <span class="identifier">pred</span> <span class="special">);</span> 594 595<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">BidirectionalRange</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Pred</span><span class="special">></span> 596<span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special"><</span><span class="keyword">const</span> <span class="identifier">BidirectionalRange</span><span class="special">>::</span><span class="identifier">type</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special"><</span><span class="keyword">const</span> <span class="identifier">BidirectionalRange</span><span class="special">>::</span><span class="identifier">type</span><span class="special">></span> 597<span class="identifier">gather</span> <span class="special">(</span> <span class="keyword">const</span> <span class="identifier">BidirectionalRange</span> <span class="special">&</span><span class="identifier">range</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special"><</span><span class="keyword">const</span> <span class="identifier">BidirectionalRange</span><span class="special">>::</span><span class="identifier">type</span> <span class="identifier">pivot</span><span class="special">,</span> <span class="identifier">Pred</span> <span class="identifier">pred</span> <span class="special">);</span> 598 599<span class="special">}}</span> 600</pre> 601<p> 602 </p> 603<h6> 604<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.h1"></a> 605 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.examples"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.examples">Examples</a> 606 </h6> 607<p> 608 Given an sequence containing: 609</p> 610<pre class="programlisting"><span class="number">0</span> <span class="number">1</span> <span class="number">2</span> <span class="number">3</span> <span class="number">4</span> <span class="number">5</span> <span class="number">6</span> <span class="number">7</span> <span class="number">8</span> <span class="number">9</span> 611</pre> 612<p> 613 </p> 614<p> 615 a call to gather ( arr, arr + 10, arr + 4, IsEven ) will result in: 616 </p> 617<p> 618</p> 619<pre class="programlisting"><span class="number">1</span> <span class="number">3</span> <span class="number">0</span> <span class="number">2</span> <span class="number">4</span> <span class="number">6</span> <span class="number">8</span> <span class="number">5</span> <span class="number">7</span> <span class="number">9</span> 620 <span class="special">|---|-----|</span> 621 <span class="identifier">first</span> <span class="special">|</span> <span class="identifier">second</span> 622 <span class="identifier">pivot</span> 623</pre> 624<p> 625 where <code class="computeroutput"><span class="identifier">first</span></code> and <code class="computeroutput"><span class="identifier">second</span></code> are the fields of the pair that 626 is returned by the call. 627 </p> 628<h6> 629<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.h2"></a> 630 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.iterator_requirements"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.iterator_requirements">Iterator 631 Requirements</a> 632 </h6> 633<p> 634 <code class="computeroutput"><span class="identifier">gather</span></code> work on bidirectional 635 iterators or better. This requirement comes from the usage of <code class="computeroutput"><span class="identifier">stable_partition</span></code>, which requires bidirectional 636 iterators. Some standard libraries (libstdc++ and libc++, for example) 637 have implementations of <code class="computeroutput"><span class="identifier">stable_partition</span></code> 638 that work with forward iterators. If that is the case, then <code class="computeroutput"><span class="identifier">gather</span></code> will work with forward iterators 639 as well. 640 </p> 641<h6> 642<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.h3"></a> 643 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.storage_requirements"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.storage_requirements">Storage 644 Requirements</a> 645 </h6> 646<p> 647 <code class="computeroutput"><span class="identifier">gather</span></code> uses <code class="computeroutput"><span class="identifier">stable_partition</span></code>, which will attempt 648 to allocate temporary memory, but will work in-situ if there is none available. 649 </p> 650<h6> 651<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.h4"></a> 652 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.complexity"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.complexity">Complexity</a> 653 </h6> 654<p> 655 If there is sufficient memory available, the run time is linear: <code class="computeroutput"><span class="identifier">O</span><span class="special">(</span><span class="identifier">N</span><span class="special">)</span></code> 656 </p> 657<p> 658 If there is not any memory available, then the run time is <code class="computeroutput"><span class="identifier">O</span><span class="special">(</span><span class="identifier">N</span> 659 <span class="identifier">log</span> <span class="identifier">N</span><span class="special">)</span></code>. 660 </p> 661<h6> 662<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.h5"></a> 663 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.exception_safety"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.exception_safety">Exception 664 Safety</a> 665 </h6> 666<h6> 667<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.h6"></a> 668 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.notes"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.gather.notes">Notes</a> 669 </h6> 670</div> 671<div class="section"> 672<div class="titlepage"><div><div><h4 class="title"> 673<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex"></a><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.hex" title="hex">hex</a> 674</h4></div></div></div> 675<p> 676 The header file <code class="computeroutput"><span class="char">'boost/algorithm/hex.hpp'</span></code> 677 contains three variants each of two algorithms, <code class="computeroutput"><span class="identifier">hex</span></code> 678 and <code class="computeroutput"><span class="identifier">unhex</span></code>. They are inverse 679 algorithms; that is, one undoes the effort of the other. <code class="computeroutput"><span class="identifier">hex</span></code> takes a sequence of values, and turns 680 them into hexadecimal characters. <code class="computeroutput"><span class="identifier">unhex</span></code> 681 takes a sequence of hexadecimal characters, and outputs a sequence of values. 682 </p> 683<p> 684 <code class="computeroutput"><span class="identifier">hex</span></code> and <code class="computeroutput"><span class="identifier">unhex</span></code> 685 come from MySQL, where they are used in database queries and stored procedures. 686 </p> 687<h6> 688<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.h0"></a> 689 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.interface"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.interface">interface</a> 690 </h6> 691<p> 692 The function <code class="computeroutput"><span class="identifier">hex</span></code> takes 693 a sequence of values and writes hexadecimal characters. There are three 694 different interfaces, differing only in how the input sequence is specified. 695 </p> 696<p> 697 The first one takes an iterator pair. The second one takes a pointer to 698 the start of a zero-terminated sequence, such as a c string, and the third 699 takes a range as defined by the Boost.Range library. 700 </p> 701<p> 702</p> 703<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">InputIterator</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">OutputIterator</span><span class="special">></span> 704<span class="identifier">OutputIterator</span> <span class="identifier">hex</span> <span class="special">(</span> <span class="identifier">InputIterator</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">InputIterator</span> <span class="identifier">last</span><span class="special">,</span> <span class="identifier">OutputIterator</span> <span class="identifier">out</span> <span class="special">);</span> 705 706<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">OutputIterator</span><span class="special">></span> 707<span class="identifier">OutputIterator</span> <span class="identifier">hex</span> <span class="special">(</span> <span class="keyword">const</span> <span class="identifier">T</span> <span class="special">*</span><span class="identifier">ptr</span><span class="special">,</span> <span class="identifier">OutputIterator</span> <span class="identifier">out</span> <span class="special">);</span> 708 709<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">Range</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">OutputIterator</span><span class="special">></span> 710<span class="identifier">OutputIterator</span> <span class="identifier">hex</span> <span class="special">(</span> <span class="keyword">const</span> <span class="identifier">Range</span> <span class="special">&</span><span class="identifier">r</span><span class="special">,</span> <span class="identifier">OutputIterator</span> <span class="identifier">out</span> <span class="special">);</span> 711</pre> 712<p> 713 </p> 714<p> 715 <code class="computeroutput"><span class="identifier">hex</span></code> writes only values 716 in the range '0'..'9' and 'A'..'F', but is not limited to character output. 717 The output iterator could refer to a wstring, or a vector of integers, 718 or any other integral type. 719 </p> 720<p> 721 The function <code class="computeroutput"><span class="identifier">unhex</span></code> takes 722 the output of <code class="computeroutput"><span class="identifier">hex</span></code> and turns 723 it back into a sequence of values. 724 </p> 725<p> 726 The input parameters for the different variations of <code class="computeroutput"><span class="identifier">unhex</span></code> 727 are the same as <code class="computeroutput"><span class="identifier">hex</span></code>. 728 </p> 729<p> 730</p> 731<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">InputIterator</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">OutputIterator</span><span class="special">></span> 732<span class="identifier">OutputIterator</span> <span class="identifier">unhex</span> <span class="special">(</span> <span class="identifier">InputIterator</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">InputIterator</span> <span class="identifier">last</span><span class="special">,</span> <span class="identifier">OutputIterator</span> <span class="identifier">out</span> <span class="special">);</span> 733 734<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">OutputIterator</span><span class="special">></span> 735<span class="identifier">OutputIterator</span> <span class="identifier">unhex</span> <span class="special">(</span> <span class="keyword">const</span> <span class="identifier">T</span> <span class="special">*</span><span class="identifier">ptr</span><span class="special">,</span> <span class="identifier">OutputIterator</span> <span class="identifier">out</span> <span class="special">);</span> 736 737<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">Range</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">OutputIterator</span><span class="special">></span> 738<span class="identifier">OutputIterator</span> <span class="identifier">unhex</span> <span class="special">(</span> <span class="keyword">const</span> <span class="identifier">Range</span> <span class="special">&</span><span class="identifier">r</span><span class="special">,</span> <span class="identifier">OutputIterator</span> <span class="identifier">out</span> <span class="special">);</span> 739</pre> 740<p> 741 </p> 742<h6> 743<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.h1"></a> 744 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.error_handling"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.error_handling">Error 745 Handling</a> 746 </h6> 747<p> 748 The header 'hex.hpp' defines three exception classes: 749</p> 750<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">hex_decode_error</span><span class="special">:</span> <span class="keyword">virtual</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">exception</span><span class="special">,</span> <span class="keyword">virtual</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">exception</span> <span class="special">{};</span> 751<span class="keyword">struct</span> <span class="identifier">not_enough_input</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">hex_decode_error</span><span class="special">;</span> 752<span class="keyword">struct</span> <span class="identifier">non_hex_input</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">hex_decode_error</span><span class="special">;</span> 753</pre> 754<p> 755 </p> 756<p> 757 If the input to <code class="computeroutput"><span class="identifier">unhex</span></code> does 758 not contain an "even number" of hex digits, then an exception 759 of type <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">algorithm</span><span class="special">::</span><span class="identifier">not_enough_input</span></code> is thrown. 760 </p> 761<p> 762 If the input to <code class="computeroutput"><span class="identifier">unhex</span></code> contains 763 any non-hexadecimal characters, then an exception of type <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">algorithm</span><span class="special">::</span><span class="identifier">non_hex_input</span></code> is thrown. 764 </p> 765<p> 766 If you want to catch all the decoding errors, you can catch exceptions 767 of type <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">algorithm</span><span class="special">::</span><span class="identifier">hex_decode_error</span></code>. 768 </p> 769<h6> 770<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.h2"></a> 771 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.examples"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.examples">Examples</a> 772 </h6> 773<p> 774 Assuming that <code class="computeroutput"><span class="identifier">out</span></code> is an 775 iterator that accepts <code class="computeroutput"><span class="keyword">char</span></code> 776 values, and <code class="computeroutput"><span class="identifier">wout</span></code> accepts 777 <code class="computeroutput"><span class="keyword">wchar_t</span></code> values (and that sizeof 778 ( wchar_t ) == 2) 779 </p> 780<p> 781</p> 782<pre class="programlisting"><span class="identifier">hex</span> <span class="special">(</span> <span class="string">"abcdef"</span><span class="special">,</span> <span class="identifier">out</span> <span class="special">)</span> <span class="special">--></span> <span class="string">"616263646566"</span> 783<span class="identifier">hex</span> <span class="special">(</span> <span class="string">"32"</span><span class="special">,</span> <span class="identifier">out</span> <span class="special">)</span> <span class="special">--></span> <span class="string">"3332"</span> 784<span class="identifier">hex</span> <span class="special">(</span> <span class="string">"abcdef"</span><span class="special">,</span> <span class="identifier">wout</span> <span class="special">)</span> <span class="special">--></span> <span class="string">"006100620063006400650066"</span> 785<span class="identifier">hex</span> <span class="special">(</span> <span class="string">"32"</span><span class="special">,</span> <span class="identifier">wout</span> <span class="special">)</span> <span class="special">--></span> <span class="string">"00330032"</span> 786 787<span class="identifier">unhex</span> <span class="special">(</span> <span class="string">"616263646566"</span><span class="special">,</span> <span class="identifier">out</span> <span class="special">)</span> <span class="special">--></span> <span class="string">"abcdef"</span> 788<span class="identifier">unhex</span> <span class="special">(</span> <span class="string">"3332"</span><span class="special">,</span> <span class="identifier">out</span> <span class="special">)</span> <span class="special">--></span> <span class="string">"32"</span> 789<span class="identifier">unhex</span> <span class="special">(</span> <span class="string">"616263646566"</span><span class="special">,</span> <span class="identifier">wout</span> <span class="special">)</span> <span class="special">--></span> <span class="string">"\6162\6364\6566"</span> <span class="special">(</span> <span class="identifier">i</span><span class="special">.</span><span class="identifier">e</span><span class="special">,</span> <span class="identifier">a</span> <span class="number">3</span> <span class="identifier">character</span> <span class="identifier">string</span> <span class="special">)</span> 790<span class="identifier">unhex</span> <span class="special">(</span> <span class="string">"3332"</span><span class="special">,</span> <span class="identifier">wout</span> <span class="special">)</span> <span class="special">--></span> <span class="string">"\3233"</span> <span class="special">(</span> <span class="identifier">U</span><span class="special">+</span><span class="number">3332</span><span class="special">,</span> <span class="identifier">SQUARE</span> <span class="identifier">HUARADDO</span> <span class="special">)</span> 791 792<span class="identifier">unhex</span> <span class="special">(</span> <span class="string">"3"</span><span class="special">,</span> <span class="identifier">out</span> <span class="special">)</span> <span class="special">--></span> <span class="identifier">Error</span> <span class="special">-</span> <span class="keyword">not</span> <span class="identifier">enough</span> <span class="identifier">input</span> 793<span class="identifier">unhex</span> <span class="special">(</span> <span class="string">"32"</span><span class="special">,</span> <span class="identifier">wout</span> <span class="special">)</span> <span class="special">--></span> <span class="identifier">Error</span> <span class="special">-</span> <span class="keyword">not</span> <span class="identifier">enough</span> <span class="identifier">input</span> 794 795<span class="identifier">unhex</span> <span class="special">(</span> <span class="string">"ACEG"</span><span class="special">,</span> <span class="identifier">out</span> <span class="special">)</span> <span class="special">--></span> <span class="identifier">Error</span> <span class="special">-</span> <span class="identifier">non</span><span class="special">-</span><span class="identifier">hex</span> <span class="identifier">input</span> 796</pre> 797<p> 798 </p> 799<h6> 800<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.h3"></a> 801 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.iterator_requirements"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.iterator_requirements">Iterator 802 Requirements</a> 803 </h6> 804<p> 805 <code class="computeroutput"><span class="identifier">hex</span></code> and <code class="computeroutput"><span class="identifier">unhex</span></code> 806 work on all iterator types. 807 </p> 808<h6> 809<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.h4"></a> 810 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.complexity"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.complexity">Complexity</a> 811 </h6> 812<p> 813 All of the variants of <code class="computeroutput"><span class="identifier">hex</span></code> 814 and <code class="computeroutput"><span class="identifier">unhex</span></code> run in <span class="emphasis"><em>O(N)</em></span> 815 (linear) time; that is, that is, they process each element in the input 816 sequence once. 817 </p> 818<h6> 819<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.h5"></a> 820 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.exception_safety"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.exception_safety">Exception 821 Safety</a> 822 </h6> 823<p> 824 All of the variants of <code class="computeroutput"><span class="identifier">hex</span></code> 825 and <code class="computeroutput"><span class="identifier">unhex</span></code> take their parameters 826 by value or const reference, and do not depend upon any global state. Therefore, 827 all the routines in this file provide the strong exception guarantee. However, 828 when working on input iterators, if an exception is thrown, the input iterators 829 will not be reset to their original values (i.e, the characters read from 830 the iterator cannot be un-read) 831 </p> 832<h6> 833<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.h6"></a> 834 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.notes"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.hex.notes">Notes</a> 835 </h6> 836<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"> 837 <code class="computeroutput"><span class="identifier">hex</span></code> and <code class="computeroutput"><span class="identifier">unhex</span></code> both do nothing when passed 838 empty ranges. 839 </li></ul></div> 840</div> 841<div class="section"> 842<div class="titlepage"><div><div><h4 class="title"> 843<a name="algorithm.Misc.misc_inner_algorithms.unhex"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.unhex" title="unhex">unhex 844 </a> 845</h4></div></div></div> 846<p> 847 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/hex_hpp.html" title="Header <boost/algorithm/hex.hpp>">unhex</a> 848 </code> </strong></span> Convert a sequence of hexadecimal characters into 849 a sequence of integers or characters 850 </p> 851</div> 852<div class="section"> 853<div class="titlepage"><div><div><h4 class="title"> 854<a name="algorithm.Misc.misc_inner_algorithms.hex_lower"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.hex_lower" title="hex_lower">hex_lower 855 </a> 856</h4></div></div></div> 857<p> 858 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/hex_hpp.html" title="Header <boost/algorithm/hex.hpp>">hex_lower</a> 859 </code> </strong></span> Convert a sequence of integral types into a lower 860 case hexadecimal sequence of characters 861 </p> 862</div> 863<div class="section"> 864<div class="titlepage"><div><div><h4 class="title"> 865<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome"></a><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome" title="is_palindrome">is_palindrome</a> 866</h4></div></div></div> 867<p> 868 The header file 'is_palindrome.hpp' contains six variants of a single algorithm, 869 is_palindrome. The algorithm tests the sequence and returns true if the 870 sequence is a palindrome; i.e, it is identical when traversed either backwards 871 or frontwards. 872 </p> 873<p> 874 The routine <code class="computeroutput"><span class="identifier">is_palindrome</span></code> 875 takes a sequence and, optionally, a predicate. It will return true if the 876 predicate returns true for tested elements by algorithm in the sequence. 877 </p> 878<p> 879 The routine come in 6 forms; the first one takes two iterators to define 880 the range. The second form takes two iterators to define the range and 881 a predicate. The third form takes a single range parameter, and uses Boost.Range 882 to traverse it. The fourth form takes a single range parameter ( uses Boost.Range 883 to traverse it) and a predicate. The fifth form takes a single C-string 884 and a predicate. The sixth form takes a single C-string. 885 </p> 886<h6> 887<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.h0"></a> 888 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.interface"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.interface">interface</a> 889 </h6> 890<p> 891 The function <code class="computeroutput"><span class="identifier">is_palindrome</span></code> 892 returns true if the predicate returns true any tested by algorithm items 893 in the sequence. There are six versions: 1) takes two iterators. 2) takes 894 two iterators and a predicate. 3) takes a range. 4) takes a range and a 895 predicate. 5) takes a C-string and a predicate. 6) takes a C-string. 896 </p> 897<p> 898</p> 899<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">BidirectionalIterator</span><span class="special">></span> 900 <span class="keyword">bool</span> <span class="identifier">is_palindrome</span> <span class="special">(</span> <span class="identifier">BidirectionalIterator</span> <span class="identifier">begin</span><span class="special">,</span> <span class="identifier">BidirectionalIterator</span> <span class="identifier">end</span> <span class="special">);</span> 901<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">BidirectionalIterator</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Predicate</span><span class="special">></span> 902 <span class="keyword">bool</span> <span class="identifier">is_palindrome</span> <span class="special">(</span> <span class="identifier">BidirectionalIterator</span> <span class="identifier">begin</span><span class="special">,</span> <span class="identifier">BidirectionalIterator</span> <span class="identifier">end</span><span class="special">,</span> <span class="identifier">Predicate</span> <span class="identifier">p</span> <span class="special">);</span> 903<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">Range</span><span class="special">></span> 904 <span class="keyword">bool</span> <span class="identifier">is_palindrome</span> <span class="special">(</span> <span class="keyword">const</span> <span class="identifier">Range</span> <span class="special">&</span><span class="identifier">r</span> <span class="special">);</span> 905<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">Range</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Predicate</span><span class="special">></span> 906 <span class="keyword">bool</span> <span class="identifier">is_palindrome</span> <span class="special">(</span> <span class="keyword">const</span> <span class="identifier">Range</span> <span class="special">&</span><span class="identifier">r</span><span class="special">,</span> <span class="identifier">Predicate</span> <span class="identifier">p</span> <span class="special">);</span> 907<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">Predicate</span><span class="special">></span> 908 <span class="keyword">bool</span> <span class="identifier">is_palindrome</span> <span class="special">(</span> <span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">str</span><span class="special">,</span> <span class="identifier">Predicate</span> <span class="identifier">p</span> <span class="special">);</span> 909<span class="keyword">bool</span> <span class="identifier">is_palindrome</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">str</span><span class="special">);</span> 910</pre> 911<p> 912 </p> 913<h6> 914<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.h1"></a> 915 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.examples"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.examples">Examples</a> 916 </h6> 917<p> 918 Given the containers: const std::list<int> empty, const std::vector<char> 919 singleElement{'z'}, int oddNonPalindrome[] = {3,2,2}, const int oddPalindrome[] 920 = {1,2,3,2,1}, const int evenPalindrome[] = {1,2,2,1}, int evenNonPalindrome[] 921 = {1,4,8,8}, then 922</p> 923<pre class="programlisting"><span class="identifier">is_palindrome</span><span class="special">(</span><span class="identifier">empty</span><span class="special">))</span> <span class="special">--></span> <span class="keyword">true</span> <span class="comment">//empty range </span> 924<span class="identifier">is_palindrome</span><span class="special">(</span><span class="identifier">singleElement</span><span class="special">))</span> <span class="special">--></span> <span class="keyword">true</span> 925<span class="identifier">is_palindrome</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">begin</span><span class="special">(</span><span class="identifier">oddNonPalindrome</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">end</span><span class="special">(</span><span class="identifier">oddNonPalindrome</span><span class="special">)))</span> <span class="special">--></span> <span class="keyword">false</span> 926<span class="identifier">is_palindrome</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">begin</span><span class="special">(</span><span class="identifier">evenPalindrome</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">end</span><span class="special">(</span><span class="identifier">evenPalindrome</span><span class="special">)))</span> <span class="special">--></span> <span class="keyword">true</span> 927<span class="identifier">is_palindrome</span><span class="special">(</span><span class="identifier">empty</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">empty</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="identifier">functorComparator</span><span class="special">()))</span> <span class="special">--></span> <span class="keyword">true</span> <span class="comment">//empty range </span> 928<span class="identifier">is_palindrome</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">begin</span><span class="special">(</span><span class="identifier">oddNonPalindrome</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">end</span><span class="special">(</span><span class="identifier">oddNonPalindrome</span><span class="special">),</span> <span class="identifier">funcComparator</span><span class="special"><</span><span class="keyword">int</span><span class="special">>))</span> <span class="special">--></span> <span class="keyword">false</span> 929<span class="identifier">is_palindrome</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">begin</span><span class="special">(</span><span class="identifier">oddPalindrome</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">end</span><span class="special">(</span><span class="identifier">oddPalindrome</span><span class="special">))</span> <span class="special">--></span> <span class="keyword">true</span> 930<span class="identifier">is_palindrome</span><span class="special">(</span><span class="identifier">evenPalindrome</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">equal_to</span><span class="special"><</span><span class="keyword">int</span><span class="special">>()))</span> <span class="special">--></span> <span class="keyword">true</span> 931<span class="identifier">is_palindrome</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">begin</span><span class="special">(</span><span class="identifier">evenNonPalindrome</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">end</span><span class="special">(</span><span class="identifier">evenNonPalindrome</span><span class="special">))</span> <span class="special">--></span> <span class="keyword">false</span> 932<span class="identifier">is_palindrome</span><span class="special">(</span><span class="string">"a"</span><span class="special">)</span> <span class="special">--></span> <span class="keyword">true</span> 933<span class="identifier">is_palindrome</span><span class="special">(</span><span class="string">"aba"</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">equal_to</span><span class="special"><</span><span class="keyword">char</span><span class="special">>())</span> <span class="special">--></span> <span class="keyword">true</span> 934</pre> 935<p> 936 </p> 937<h6> 938<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.h2"></a> 939 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.iterator_requirements"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.iterator_requirements">Iterator 940 Requirements</a> 941 </h6> 942<p> 943 <code class="computeroutput"><span class="identifier">is_palindrome</span></code> work on Bidirectional 944 and RandomAccess iterators. 945 </p> 946<h6> 947<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.h3"></a> 948 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.complexity"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.complexity">Complexity</a> 949 </h6> 950<p> 951 All of the variants of <code class="computeroutput"><span class="identifier">is_palindrome</span></code> 952 run in <span class="emphasis"><em>O(N)</em></span> (linear) time; that is, they compare against 953 each element in the list once. If any of the comparisons not succeed, the 954 algorithm will terminate immediately, without examining the remaining members 955 of the sequence. 956 </p> 957<h6> 958<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.h4"></a> 959 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.exception_safety"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.exception_safety">Exception 960 Safety</a> 961 </h6> 962<p> 963 All of the variants of <code class="computeroutput"><span class="identifier">is_palindrome</span></code> 964 take their parameters by value, const pointer or const reference, and do 965 not depend upon any global state. Therefore, all the routines in this file 966 provide the strong exception guarantee. 967 </p> 968<h6> 969<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.h5"></a> 970 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.notes"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome.notes">Notes</a> 971 </h6> 972<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 973<li class="listitem"> 974 <code class="computeroutput"><span class="identifier">is_palindrome</span></code> returns 975 true for empty ranges, const char* null pointers and for single element 976 ranges. 977 </li> 978<li class="listitem"> 979 If you use version of 'is_palindrome' without custom predicate, 'is_palindrome' 980 uses default 'operator==()' for elements. 981 </li> 982<li class="listitem"> 983 Be careful with using not null pointer 'const char*' without '\0' - 984 if you use it with 'is_palindrome', it's a undefined behaviour. 985 </li> 986</ul></div> 987</div> 988<div class="section"> 989<div class="titlepage"><div><div><h4 class="title"> 990<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until"></a><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until" title="is_partitioned_until">is_partitioned_until 991 </a> 992</h4></div></div></div> 993<p> 994 The header file 'is_partitioned_until.hpp' contains two variants of a single 995 algorithm, <code class="computeroutput"><span class="identifier">is_partitioned_until</span></code>. 996 The algorithm tests to see if a sequence is partitioned according to a 997 predicate; in other words, all the items in the sequence that satisfy the 998 predicate are at the beginning of the sequence. 999 </p> 1000<p> 1001 The routine <code class="computeroutput"><span class="identifier">is_partitioned_until</span></code> 1002 takes a sequence and a predicate. It returns the last iterator 'it' in 1003 the sequence [begin, end) for which the is_partitioned(begin, it) is true. 1004 </p> 1005<p> 1006 <code class="computeroutput"><span class="identifier">is_partitioned_until</span></code> come 1007 in two forms; the first one takes two iterators to define the range. The 1008 second form takes a single range parameter, and uses Boost.Range to traverse 1009 it. 1010 </p> 1011<h6> 1012<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.h0"></a> 1013 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.interface"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.interface">interface</a> 1014 </h6> 1015<p> 1016 The function <code class="computeroutput"><span class="identifier">is_partitioned_until</span></code> 1017 returns the last iterator 'it' in the sequence [begin, end) for which the 1018 is_partitioned(begin, it) is true. There are two versions; one takes two 1019 iterators, and the other takes a range. 1020 </p> 1021<p> 1022</p> 1023<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">InputIterator</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Predicate</span><span class="special">></span> 1024 <span class="identifier">InputIterator</span> <span class="identifier">is_partitioned_until</span> <span class="special">(</span> <span class="identifier">InputIterator</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">InputIterator</span> <span class="identifier">last</span><span class="special">,</span> <span class="identifier">Predicate</span> <span class="identifier">p</span> <span class="special">);</span> 1025<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">Range</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Predicate</span><span class="special">></span> 1026 <span class="keyword">typename</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">range_iterator</span><span class="special"><</span><span class="keyword">const</span> <span class="identifier">Range</span><span class="special">>::</span><span class="identifier">type</span> <span class="identifier">is_partitioned_until</span> <span class="special">(</span> <span class="keyword">const</span> <span class="identifier">Range</span> <span class="special">&</span><span class="identifier">r</span><span class="special">,</span> <span class="identifier">Predicate</span> <span class="identifier">p</span> <span class="special">);</span> 1027</pre> 1028<p> 1029 </p> 1030<h6> 1031<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.h1"></a> 1032 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.examples"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.examples">Examples</a> 1033 </h6> 1034<p> 1035 Given the container <code class="computeroutput"><span class="identifier">c</span></code> containing 1036 <code class="computeroutput"><span class="special">{</span> <span class="number">0</span><span class="special">,</span> <span class="number">1</span><span class="special">,</span> 1037 <span class="number">2</span><span class="special">,</span> <span class="number">3</span><span class="special">,</span> <span class="number">14</span><span class="special">,</span> <span class="number">15</span> <span class="special">}</span></code>, 1038 then 1039</p> 1040<pre class="programlisting"><span class="keyword">bool</span> <span class="identifier">isOdd</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="number">1</span><span class="special">;</span> <span class="special">}</span> 1041<span class="keyword">bool</span> <span class="identifier">lessThan10</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">10</span><span class="special">;</span> <span class="special">}</span> 1042 1043<span class="identifier">is_partitioned_until</span> <span class="special">(</span> <span class="identifier">c</span><span class="special">,</span> <span class="identifier">isOdd</span> <span class="special">)</span> <span class="special">--></span> <span class="identifier">iterator</span> <span class="identifier">to</span> <span class="char">'1'</span> 1044<span class="identifier">is_partitioned_until</span> <span class="special">(</span> <span class="identifier">c</span><span class="special">,</span> <span class="identifier">lessThan10</span> <span class="special">)</span> <span class="special">--></span> <span class="identifier">end</span> 1045<span class="identifier">is_partitioned_until</span> <span class="special">(</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span> <span class="special">(),</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span> <span class="special">(),</span> <span class="identifier">lessThan10</span> <span class="special">)</span> <span class="special">--></span> <span class="identifier">end</span> 1046<span class="identifier">is_partitioned_until</span> <span class="special">(</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span> <span class="special">(),</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span> <span class="special">()</span> <span class="special">+</span> <span class="number">3</span><span class="special">,</span> <span class="identifier">lessThan10</span> <span class="special">)</span> <span class="special">--></span> <span class="identifier">end</span> 1047<span class="identifier">is_partitioned_until</span> <span class="special">(</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span> <span class="special">(),</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span> <span class="special">(),</span> <span class="identifier">isOdd</span> <span class="special">)</span> <span class="special">--></span> <span class="identifier">end</span> <span class="comment">// empty range</span> 1048</pre> 1049<p> 1050 </p> 1051<h6> 1052<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.h2"></a> 1053 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.iterator_requirements"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.iterator_requirements">Iterator 1054 Requirements</a> 1055 </h6> 1056<p> 1057 <code class="computeroutput"><span class="identifier">is_partitioned_until</span></code> works 1058 on all iterators except output iterators. 1059 </p> 1060<h6> 1061<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.h3"></a> 1062 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.complexity"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.complexity">Complexity</a> 1063 </h6> 1064<p> 1065 Both of the variants of <code class="computeroutput"><span class="identifier">is_partitioned_until</span></code> 1066 run in <span class="emphasis"><em>O(N)</em></span> (linear) time; that is, they compare against 1067 each element in the list once. If the sequence is found to be not partitioned 1068 at any point, the routine will terminate immediately, without examining 1069 the rest of the elements. 1070 </p> 1071<h6> 1072<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.h4"></a> 1073 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.exception_safety"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.exception_safety">Exception 1074 Safety</a> 1075 </h6> 1076<p> 1077 Both of the variants of <code class="computeroutput"><span class="identifier">is_partitioned_until</span></code> 1078 take their parameters by value or const reference, and do not depend upon 1079 any global state. Therefore, all the routines in this file provide the 1080 strong exception guarantee. 1081 </p> 1082<h6> 1083<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.h5"></a> 1084 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.notes"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until.notes">Notes</a> 1085 </h6> 1086<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"> 1087 <code class="computeroutput"><span class="identifier">is_partitioned_until</span></code> 1088 returns iterator to the end for empty and single-element ranges, no 1089 matter what predicate is passed to test against. 1090 </li></ul></div> 1091</div> 1092<div class="section"> 1093<div class="titlepage"><div><div><h4 class="title"> 1094<a name="algorithm.Misc.misc_inner_algorithms.apply_reverse_permutation"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.apply_reverse_permutation" title="apply_reverse_permutation">apply_reverse_permutation 1095 </a> 1096</h4></div></div></div> 1097<p> 1098 See below 1099 </p> 1100</div> 1101<div class="section"> 1102<div class="titlepage"><div><div><h4 class="title"> 1103<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation"></a><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation" title="apply_permutation">apply_permutation</a> 1104</h4></div></div></div> 1105<p> 1106 The header file <code class="literal"><a class="link" href="../header/boost/algorithm/apply_permutation_hpp.html" title="Header <boost/algorithm/apply_permutation.hpp>">apply_permutation.hpp</a></code> 1107 contains two algorithms, <code class="computeroutput"><span class="identifier">apply_permutation</span></code> 1108 and <code class="computeroutput"><span class="identifier">apply_reverse_permutation</span></code>. 1109 There are also range-based versions. The algorithms transform the item 1110 sequence according to index sequence order. 1111 </p> 1112<p> 1113 The routine <code class="computeroutput"><span class="identifier">apply_permutation</span></code> 1114 takes a item sequence and a order sequence. It reshuffles item sequence 1115 according to order sequence. Every value in order sequence means where 1116 the item comes from. Order sequence needs to be exactly a permutation of 1117 the sequence [0, 1, ... , N], where N is the biggest index in the item 1118 sequence (zero-indexed). The routine <code class="computeroutput"><span class="identifier">apply_reverse_permutation</span></code> 1119 takes a item sequence and a order sequence. It will reshuffle item sequence 1120 according to order sequence. Every value in order sequence means where 1121 the item goes to. Order sequence needs to be exactly a permutation of the 1122 sequence [0, 1, ... , N], where N is the biggest index in the item sequence 1123 (zero-indexed). 1124 </p> 1125<p> 1126 Implementations are based on these articles: https://blogs.msdn.microsoft.com/oldnewthing/20170102-00/?p=95095 1127 https://blogs.msdn.microsoft.com/oldnewthing/20170103-00/?p=95105 https://blogs.msdn.microsoft.com/oldnewthing/20170104-00/?p=95115 1128 https://blogs.msdn.microsoft.com/oldnewthing/20170109-00/?p=95145 https://blogs.msdn.microsoft.com/oldnewthing/20170110-00/?p=95155 1129 https://blogs.msdn.microsoft.com/oldnewthing/20170111-00/?p=95165 1130 </p> 1131<p> 1132 The routines come in 2 forms; the first one takes two iterators to define 1133 the item range and one iterator to define the beginning of index range. 1134 The second form takes range to define the item sequence and range to define 1135 index sequence. 1136 </p> 1137<h6> 1138<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.h0"></a> 1139 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.interface"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.interface">interface</a> 1140 </h6> 1141<p> 1142 There are two versions of algorithms: 1) takes four iterators. 2) takes 1143 two ranges. 1144</p> 1145<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">RandomAccessIterator1</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">RandomAccessIterator2</span><span class="special">></span> 1146<span class="keyword">void</span> <span class="identifier">apply_permutation</span><span class="special">(</span><span class="identifier">RandomAccessIterator1</span> <span class="identifier">item_begin</span><span class="special">,</span> <span class="identifier">RandomAccessIterator1</span> <span class="identifier">item_end</span><span class="special">,</span> 1147 <span class="identifier">RandomAccessIterator2</span> <span class="identifier">ind_begin</span><span class="special">,</span> <span class="identifier">RandomAccessIterator2</span> <span class="identifier">ind_end</span><span class="special">);</span> 1148<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">Range1</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Range2</span><span class="special">></span> 1149<span class="keyword">void</span> <span class="identifier">apply_permutation</span><span class="special">(</span><span class="identifier">Range1</span><span class="special">&</span> <span class="identifier">item_range</span><span class="special">,</span> <span class="identifier">Range2</span><span class="special">&</span> <span class="identifier">ind_range</span><span class="special">);</span> 1150<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">RandomAccessIterator1</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">RandomAccessIterator2</span><span class="special">></span> 1151<span class="keyword">void</span> <span class="identifier">apply_reverse_permutation</span><span class="special">(</span><span class="identifier">RandomAccessIterator1</span> <span class="identifier">item_begin</span><span class="special">,</span> <span class="identifier">RandomAccessIterator1</span> <span class="identifier">item_end</span><span class="special">,</span> 1152 <span class="identifier">RandomAccessIterator2</span> <span class="identifier">ind_begin</span><span class="special">,</span> <span class="identifier">RandomAccessIterator2</span> <span class="identifier">ind_end</span><span class="special">);</span> 1153<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">Range1</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Range2</span><span class="special">></span> 1154<span class="keyword">void</span> <span class="identifier">apply_reverse_permutation</span><span class="special">(</span><span class="identifier">Range1</span><span class="special">&</span> <span class="identifier">item_range</span><span class="special">,</span> <span class="identifier">Range2</span><span class="special">&</span> <span class="identifier">ind_range</span><span class="special">);</span> 1155</pre> 1156<p> 1157 </p> 1158<h6> 1159<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.h1"></a> 1160 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.examples"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.examples">Examples</a> 1161 </h6> 1162<p> 1163 Given the containers: std::vector<int> emp_vec, emp_order, std::vector<int> 1164 one{1}, one_order{0}, std::vector<int> two{1,2}, two_order{1,0}, 1165 std::vector<int> vec{1, 2, 3, 4, 5}, std::vector<int> order{4, 1166 2, 3, 1, 0}, then 1167</p> 1168<pre class="programlisting"><span class="identifier">apply_permutation</span><span class="special">(</span><span class="identifier">emp_vec</span><span class="special">,</span> <span class="identifier">emp_order</span><span class="special">))</span> <span class="special">--></span> <span class="identifier">no</span> <span class="identifier">changes</span> 1169<span class="identifier">apply_reverse_permutation</span><span class="special">(</span><span class="identifier">emp_vec</span><span class="special">,</span> <span class="identifier">emp_order</span><span class="special">))</span> <span class="special">--></span> <span class="identifier">no</span> <span class="identifier">changes</span> 1170<span class="identifier">apply_permutation</span><span class="special">(</span><span class="identifier">one</span><span class="special">,</span> <span class="identifier">one_order</span><span class="special">)</span> <span class="special">--></span> <span class="identifier">no</span> <span class="identifier">changes</span> 1171<span class="identifier">apply_reverse_permutation</span><span class="special">(</span><span class="identifier">one</span><span class="special">,</span> <span class="identifier">one_order</span><span class="special">)</span> <span class="special">--></span> <span class="identifier">no</span> <span class="identifier">changes</span> 1172<span class="identifier">apply_permutation</span><span class="special">(</span><span class="identifier">two</span><span class="special">,</span> <span class="identifier">two_order</span><span class="special">)</span> <span class="special">--></span> <span class="identifier">two</span><span class="special">:{</span><span class="number">2</span><span class="special">,</span><span class="number">1</span><span class="special">}</span> 1173<span class="identifier">apply_reverse_permutation</span><span class="special">(</span><span class="identifier">two</span><span class="special">,</span> <span class="identifier">two_order</span><span class="special">)</span> <span class="special">--></span> <span class="identifier">two</span><span class="special">:{</span><span class="number">2</span><span class="special">,</span><span class="number">1</span><span class="special">}</span> 1174<span class="identifier">apply_permutation</span><span class="special">(</span><span class="identifier">vec</span><span class="special">,</span> <span class="identifier">order</span><span class="special">)</span> <span class="special">--></span> <span class="identifier">vec</span><span class="special">:{</span><span class="number">5</span><span class="special">,</span> <span class="number">3</span><span class="special">,</span> <span class="number">4</span><span class="special">,</span> <span class="number">2</span><span class="special">,</span> <span class="number">1</span><span class="special">}</span> 1175<span class="identifier">apply_reverse_permutation</span><span class="special">(</span><span class="identifier">vec</span><span class="special">,</span> <span class="identifier">order</span><span class="special">)</span> <span class="special">--></span> <span class="identifier">vec</span><span class="special">:{</span><span class="number">5</span><span class="special">,</span> <span class="number">4</span><span class="special">,</span> <span class="number">2</span><span class="special">,</span> <span class="number">3</span><span class="special">,</span> <span class="number">1</span><span class="special">}</span> 1176</pre> 1177<p> 1178 </p> 1179<h6> 1180<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.h2"></a> 1181 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.iterator_requirements"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.iterator_requirements">Iterator 1182 Requirements</a> 1183 </h6> 1184<p> 1185 <code class="computeroutput"><span class="identifier">apply_permutation</span></code> and 'apply_reverse_permutation' 1186 work only on RandomAccess iterators. RandomAccess iterators required both 1187 for item and index sequences. 1188 </p> 1189<h6> 1190<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.h3"></a> 1191 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.complexity"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.complexity">Complexity</a> 1192 </h6> 1193<p> 1194 All of the variants of <code class="computeroutput"><span class="identifier">apply_permutation</span></code> 1195 and <code class="computeroutput"><span class="identifier">apply_reverse_permutation</span></code> 1196 run in <span class="emphasis"><em>O(N)</em></span> (linear) time. More 1197 </p> 1198<h6> 1199<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.h4"></a> 1200 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.exception_safety"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.exception_safety">Exception 1201 Safety</a> 1202 </h6> 1203<p> 1204 All of the variants of <code class="computeroutput"><span class="identifier">apply_permutation</span></code> 1205 and <code class="computeroutput"><span class="identifier">apply_reverse_permutation</span></code> 1206 take their parameters by iterators or reference, and do not depend upon 1207 any global state. Therefore, all the routines in this file provide the 1208 strong exception guarantee. 1209 </p> 1210<h6> 1211<a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.h5"></a> 1212 <span class="phrase"><a name="the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.notes"></a></span><a class="link" href="Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation.notes">Notes</a> 1213 </h6> 1214<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 1215<li class="listitem"> 1216 If ItemSequence and IndexSequence are not equal, behavior is undefined. 1217 </li> 1218<li class="listitem"> 1219 <code class="computeroutput"><span class="identifier">apply_permutation</span></code> and 1220 <code class="computeroutput"><span class="identifier">apply_reverse_permutation</span></code> 1221 work also on empty sequences. 1222 </li> 1223<li class="listitem"> 1224 Order sequence must be zero-indexed. 1225 </li> 1226<li class="listitem"> 1227 Order sequence gets permuted. 1228 </li> 1229</ul></div> 1230</div> 1231<div class="section"> 1232<div class="titlepage"><div><div><h4 class="title"> 1233<a name="algorithm.Misc.misc_inner_algorithms.copy_until"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.copy_until" title="copy_until">copy_until 1234 </a> 1235</h4></div></div></div> 1236<p> 1237 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/cxx11/copy_if_hpp.html" title="Header <boost/algorithm/cxx11/copy_if.hpp>">copy_until</a> 1238 </code> </strong></span> Copy all the elements at the start of the input 1239 range that do not satisfy the predicate to the output range 1240 </p> 1241</div> 1242<div class="section"> 1243<div class="titlepage"><div><div><h4 class="title"> 1244<a name="algorithm.Misc.misc_inner_algorithms.copy_while"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.copy_while" title="copy_while">copy_while 1245 </a> 1246</h4></div></div></div> 1247<p> 1248 <span class="bold"><strong><code class="literal"><a class="link" href="../header/boost/algorithm/cxx11/copy_if_hpp.html" title="Header <boost/algorithm/cxx11/copy_if.hpp>">copy_while</a> 1249 </code> </strong></span> Copy all the elements at the start of the input 1250 range that satisfy the predicate to the output range 1251 </p> 1252</div> 1253<div class="section"> 1254<div class="titlepage"><div><div><h4 class="title"> 1255<a name="algorithm.Misc.misc_inner_algorithms.iota_n"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.iota_n" title="iota_n">iota_n 1256 </a> 1257</h4></div></div></div> 1258<p> 1259 <span class="bold"><strong><code class="literal"><a class="link" href="../boost/algorithm/iota_n.html" title="Function template iota_n">iota_n</a> 1260 </code> </strong></span> Write a sequence of n increasing values to an output 1261 iterator 1262 </p> 1263</div> 1264<div class="section"> 1265<div class="titlepage"><div><div><h4 class="title"> 1266<a name="algorithm.Misc.misc_inner_algorithms.power"></a><a class="link" href="Misc.html#algorithm.Misc.misc_inner_algorithms.power" title="power">power 1267 </a> 1268</h4></div></div></div> 1269<p> 1270 <span class="bold"><strong><code class="literal"><a class="link" href="reference.html#header.boost.algorithm.algorithm_hpp" title="Header <boost/algorithm/algorithm.hpp>">power</a> 1271 </code> </strong></span> Raise a value to an integral power (<code class="literal">constexpr</code> 1272 since C++14) 1273 </p> 1274</div> 1275</div> 1276</div> 1277<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 1278<td align="left"></td> 1279<td align="right"><div class="copyright-footer">Copyright © 2010-2012 Marshall Clow<p> 1280 Distributed under the Boost Software License, Version 1.0. (See accompanying 1281 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>) 1282 </p> 1283</div></td> 1284</tr></table> 1285<hr> 1286<div class="spirit-nav"> 1287<a accesskey="p" href="CXX17.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.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="not_yet_documented_cxx17_algos.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a> 1288</div> 1289</body> 1290</html> 1291
