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