1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>Design Topics</title> 6<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> 7<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 8<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> 9<link rel="up" href="../string_algo.html" title="Chapter 2. Boost String Algorithms Library"> 10<link rel="prev" href="quickref.html" title="Quick Reference"> 11<link rel="next" href="concept.html" title="Concepts"> 12</head> 13<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 14<table cellpadding="2" width="100%"><tr> 15<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> 16<td align="center"><a href="../../../index.html">Home</a></td> 17<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> 18<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 19<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 20<td align="center"><a href="../../../more/index.htm">More</a></td> 21</tr></table> 22<hr> 23<div class="spirit-nav"> 24<a accesskey="p" href="quickref.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../string_algo.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="concept.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 25</div> 26<div class="section"> 27<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 28<a name="string_algo.design"></a>Design Topics</h2></div></div></div> 29<div class="toc"><dl class="toc"> 30<dt><span class="section"><a href="design.html#string_algo.string">String Representation</a></span></dt> 31<dt><span class="section"><a href="design.html#string_algo.sequence_traits">Sequence Traits</a></span></dt> 32<dt><span class="section"><a href="design.html#string_algo.find">Find Algorithms</a></span></dt> 33<dt><span class="section"><a href="design.html#string_algo.replace">Replace Algorithms</a></span></dt> 34<dt><span class="section"><a href="design.html#string_algo.split">Find Iterators & Split Algorithms</a></span></dt> 35<dt><span class="section"><a href="design.html#string_algo.exception">Exception Safety</a></span></dt> 36</dl></div> 37<div class="section"> 38<div class="titlepage"><div><div><h3 class="title"> 39<a name="string_algo.string"></a>String Representation</h3></div></div></div> 40<p> 41 As the name suggest, this library works mainly with strings. However, in the context of this library, 42 a string is not restricted to any particular implementation (like <code class="computeroutput">std::basic_string</code>), 43 rather it is a concept. This allows the algorithms in this library to be reused for any string type, 44 that satisfies the given requirements. 45 </p> 46<p> 47 <span class="bold"><strong>Definition:</strong></span> A string is a 48 <a href="../../../libs/range/index.html" target="_top">range</a> of characters accessible in sequential 49 ordered fashion. Character is any value type with "cheap" copying and assignment. 50 </p> 51<p> 52 First requirement of string-type is that it must accessible using 53 <a href="../../../libs/range/index.html" target="_top">Boost.Range</a>. This facility allows to access 54 the elements inside the string in a uniform iterator-based fashion. 55 This is sufficient for our library 56 </p> 57<p> 58 Second requirement defines the way in which the characters are stored in the string. Algorithms in 59 this library work with an assumption that copying a character is cheaper then allocating extra 60 storage to cache results. This is a natural assumption for common character types. Algorithms will 61 work even if this requirement is not satisfied, however at the cost of performance degradation. 62 </p> 63<p> 64 </p> 65<p> 66 In addition some algorithms have additional requirements on the string-type. Particularly, it is required 67 that an algorithm can create a new string of the given type. In this case, it is required that 68 the type satisfies the sequence (Std §23.1.1) requirements. 69 </p> 70<p> 71 In the reference and also in the code, requirement on the string type is designated by the name of 72 template argument. <code class="computeroutput">RangeT</code> means that the basic range requirements must hold. 73 <code class="computeroutput">SequenceT</code> designates extended sequence requirements. 74 </p> 75</div> 76<div class="section"> 77<div class="titlepage"><div><div><h3 class="title"> 78<a name="string_algo.sequence_traits"></a>Sequence Traits</h3></div></div></div> 79<p> 80 The major difference between <code class="computeroutput">std::list</code> and <code class="computeroutput">std::vector</code> is not in the interfaces 81 they provide, but rather in the inner details of the class and the way how it performs 82 various operations. The problem is that it is not possible to infer this difference from the 83 definitions of classes without some special mechanism. 84 However, some algorithms can run significantly faster with the knowledge of the properties 85 of a particular container. 86 </p> 87<p> 88 Sequence traits allow one to specify additional properties of a sequence container (see Std.§32.2). 89 These properties are then used by algorithms to select optimized handling for some operations. 90 The sequence traits are declared in the header 91 <code class="computeroutput"><a class="link" href="reference.html#header.boost.algorithm.string.sequence_traits_hpp" title="Header <boost/algorithm/string/sequence_traits.hpp>">boost/algorithm/string/sequence_traits.hpp</a></code>. 92 </p> 93<p> 94 In the table C denotes a container and c is an object of C. 95 </p> 96<div class="table"> 97<a name="id-1.3.3.7.3.5"></a><p class="title"><b>Table 2.12. Sequence Traits</b></p> 98<div class="table-contents"><table class="table" summary="Sequence Traits"> 99<colgroup> 100<col> 101<col> 102</colgroup> 103<thead><tr> 104<th align="left">Trait</th> 105<th align="left">Description</th> 106</tr></thead> 107<tbody> 108<tr> 109<td align="left"> 110<code class="computeroutput"><a class="link" href="../boost/algorithm/has_native_replace.html" title="Class template has_native_replace">has_native_replace<C></a></code>::value</td> 111<td align="left">Specifies that the sequence has std::string like replace method</td> 112</tr> 113<tr> 114<td align="left"> 115<code class="computeroutput"><a class="link" href="../boost/algorithm/has_stable_iterators.html" title="Class template has_stable_iterators">has_stable_iterators<C></a></code>::value</td> 116<td align="left"> 117 Specifies that the sequence has stable iterators. It means, 118 that operations like <code class="computeroutput">insert</code>/<code class="computeroutput">erase</code>/<code class="computeroutput">replace</code> 119 do not invalidate iterators. 120 </td> 121</tr> 122<tr> 123<td align="left"> 124<code class="computeroutput"><a class="link" href="../boost/algorithm/has_const_time_insert.html" title="Class template has_const_time_insert">has_const_time_insert<C></a></code>::value</td> 125<td align="left"> 126 Specifies that the insert method of the sequence has 127 constant time complexity. 128 </td> 129</tr> 130<tr> 131<td align="left"> 132<code class="computeroutput"><a class="link" href="../boost/algorithm/has_const_time_erase.html" title="Class template has_const_time_erase">has_const_time_erase<C></a></code>::value</td> 133<td align="left"> 134 Specifies that the erase method of the sequence has constant time complexity 135 </td> 136</tr> 137</tbody> 138</table></div> 139</div> 140<br class="table-break"><p> 141 Current implementation contains specializations for std::list<T> and 142 std::basic_string<T> from the standard library and SGI's std::rope<T> and std::slist<T>. 143 </p> 144</div> 145<div class="section"> 146<div class="titlepage"><div><div><h3 class="title"> 147<a name="string_algo.find"></a>Find Algorithms</h3></div></div></div> 148<p> 149 Find algorithms have similar functionality to <code class="computeroutput">std::search()</code> algorithm. They provide a different 150 interface which is more suitable for common string operations. 151 Instead of returning just the start of matching subsequence they return a range which is necessary 152 when the length of the matching subsequence is not known beforehand. 153 This feature also allows a partitioning of the input sequence into three 154 parts: a prefix, a substring and a suffix. 155 </p> 156<p> 157 Another difference is an addition of various searching methods besides find_first, including find_regex. 158 </p> 159<p> 160 It the library, find algorithms are implemented in terms of 161 <a class="link" href="concept.html#string_algo.finder_concept" title="Finder Concept">Finders</a>. Finders are used also by other facilities 162 (replace,split). 163 For convenience, there are also function wrappers for these finders to simplify find operations. 164 </p> 165<p> 166 Currently the library contains only naive implementation of find algorithms with complexity 167 O(n * m) where n is the size of the input sequence and m is the size of the search sequence. 168 There are algorithms with complexity O(n), but for smaller sequence a constant overhead is 169 rather big. For small m << n (m by magnitude smaller than n) the current implementation 170 provides acceptable efficiency. 171 Even the C++ standard defines the required complexity for search algorithm as O(n * m). 172 It is possible that a future version of library will also contain algorithms with linear 173 complexity as an option 174 </p> 175</div> 176<div class="section"> 177<div class="titlepage"><div><div><h3 class="title"> 178<a name="string_algo.replace"></a>Replace Algorithms</h3></div></div></div> 179<p> 180 The implementation of replace algorithms follows the layered structure of the library. The 181 lower layer implements generic substitution of a range in the input sequence. 182 This layer takes a <a class="link" href="concept.html#string_algo.finder_concept" title="Finder Concept">Finder</a> object and a 183 <a class="link" href="concept.html#string_algo.formatter_concept" title="Formatter concept">Formatter</a> object as an input. These two 184 functors define what to replace and what to replace it with. The upper layer functions 185 are just wrapping calls to the lower layer. Finders are shared with the find and split facility. 186 </p> 187<p> 188 As usual, the implementation of the lower layer is designed to work with a generic sequence while 189 taking advantage of specific features if possible 190 (by using <a class="link" href="design.html#string_algo.sequence_traits" title="Sequence Traits">Sequence traits</a>) 191 </p> 192</div> 193<div class="section"> 194<div class="titlepage"><div><div><h3 class="title"> 195<a name="string_algo.split"></a>Find Iterators & Split Algorithms</h3></div></div></div> 196<p> 197 Find iterators are a logical extension of the <a class="link" href="design.html#string_algo.find" title="Find Algorithms">find facility</a>. 198 Instead of searching for one match, the whole input can be iteratively searched for multiple matches. 199 The result of the search is then used to partition the input. It depends on the algorithms which parts 200 are returned as the result. They can be the matching parts (<code class="computeroutput"><a class="link" href="../boost/algorithm/find_iterator.html" title="Class template find_iterator">find_iterator</a></code>) of the parts in 201 between (<code class="computeroutput"><a class="link" href="../boost/algorithm/split_iterator.html" title="Class template split_iterator">split_iterator</a></code>). 202 </p> 203<p> 204 In addition the split algorithms like <code class="computeroutput"><a class="link" href="../boost/algorithm/find_all.html" title="Function template find_all">find_all()</a></code> and <code class="computeroutput"><a class="link" href="../boost/algorithm/split.html" title="Function template split">split()</a></code> 205 can simplify the common operations. They use a find iterator to search the whole input and copy the 206 matches they found into the supplied container. 207 </p> 208</div> 209<div class="section"> 210<div class="titlepage"><div><div><h3 class="title"> 211<a name="string_algo.exception"></a>Exception Safety</h3></div></div></div> 212<p> 213 The library requires that all operations on types used as template 214 or function arguments provide the <span class="emphasis"><em>basic exception-safety guarantee</em></span>. 215 In turn, all functions and algorithms in this library, except where stated 216 otherwise, will provide the <span class="emphasis"><em>basic exception-safety guarantee</em></span>. 217 In other words: 218 The library maintains its invariants and does not leak resources in 219 the face of exceptions. Some library operations give stronger 220 guarantees, which are documented on an individual basis. 221 </p> 222<p> 223 Some functions can provide the <span class="emphasis"><em>strong exception-safety guarantee</em></span>. 224 That means that following statements are true: 225 </p> 226<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 227<li class="listitem"> 228 If an exception is thrown, there are no effects other than those 229 of the function 230 </li> 231<li class="listitem"> 232 If an exception is thrown other than by the function, there are no effects 233 </li> 234</ul></div> 235<p> 236 This guarantee can be provided under the condition that the operations 237 on the types used for arguments for these functions either 238 provide the strong exception guarantee or do not alter the global state . 239 </p> 240<p> 241 In the reference, under the term <span class="emphasis"><em>strong exception-safety guarantee</em></span>, we mean the 242 guarantee as defined above. 243 </p> 244<p> 245 For more information about the exception safety topics, follow this 246 <a href="http://www.boost.org/more/generic_exception_safety.html" target="_top">link</a> 247 </p> 248</div> 249</div> 250<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 251<td align="left"></td> 252<td align="right"><div class="copyright-footer">Copyright © 2002-2004 Pavol Droba<p>Use, modification and distribution is subject to the Boost 253 Software License, Version 1.0. (See accompanying file 254 <code class="filename">LICENSE_1_0.txt</code> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 255 </p> 256</div></td> 257</tr></table> 258<hr> 259<div class="spirit-nav"> 260<a accesskey="p" href="quickref.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../string_algo.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="concept.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 261</div> 262</body> 263</html> 264
