1 |
742 |
jeremybenn |
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
|
2 |
|
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
|
3 |
|
|
<html xmlns="http://www.w3.org/1999/xhtml"><head><title>Chapter 7. Strings</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"/><meta name="keywords" content=" ISO C++ , library "/><meta name="keywords" content=" ISO C++ , runtime , library "/><link rel="home" href="../index.html" title="The GNU C++ Library"/><link rel="up" href="bk01pt02.html" title="Part II. Standard Contents"/><link rel="prev" href="traits.html" title="Traits"/><link rel="next" href="localization.html" title="Chapter 8. Localization"/></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 7.
|
4 |
|
|
Strings
|
5 |
|
|
|
6 |
|
|
</th></tr><tr><td align="left"><a accesskey="p" href="traits.html">Prev</a> </td><th width="60%" align="center">Part II.
|
7 |
|
|
Standard Contents
|
8 |
|
|
</th><td align="right"> <a accesskey="n" href="localization.html">Next</a></td></tr></table><hr/></div><div class="chapter" title="Chapter 7. Strings"><div class="titlepage"><div><div><h2 class="title"><a id="std.strings"/>Chapter 7.
|
9 |
|
|
Strings
|
10 |
|
|
<a id="id499563" class="indexterm"/>
|
11 |
|
|
</h2></div></div></div><div class="toc"><p><strong>Table of Contents</strong></p><dl><dt><span class="section"><a href="strings.html#std.strings.string">String Classes</a></span></dt><dd><dl><dt><span class="section"><a href="strings.html#strings.string.simple">Simple Transformations</a></span></dt><dt><span class="section"><a href="strings.html#strings.string.case">Case Sensitivity</a></span></dt><dt><span class="section"><a href="strings.html#strings.string.character_types">Arbitrary Character Types</a></span></dt><dt><span class="section"><a href="strings.html#strings.string.token">Tokenizing</a></span></dt><dt><span class="section"><a href="strings.html#strings.string.shrink">Shrink to Fit</a></span></dt><dt><span class="section"><a href="strings.html#strings.string.Cstring">CString (MFC)</a></span></dt></dl></dd></dl></div><div class="section" title="String Classes"><div class="titlepage"><div><div><h2 class="title"><a id="std.strings.string"/>String Classes</h2></div></div></div><div class="section" title="Simple Transformations"><div class="titlepage"><div><div><h3 class="title"><a id="strings.string.simple"/>Simple Transformations</h3></div></div></div><p>
|
12 |
|
|
Here are Standard, simple, and portable ways to perform common
|
13 |
|
|
transformations on a <code class="code">string</code> instance, such as
|
14 |
|
|
"convert to all upper case." The word transformations
|
15 |
|
|
is especially apt, because the standard template function
|
16 |
|
|
<code class="code">transform<></code> is used.
|
17 |
|
|
</p><p>
|
18 |
|
|
This code will go through some iterations. Here's a simple
|
19 |
|
|
version:
|
20 |
|
|
</p><pre class="programlisting">
|
21 |
|
|
#include <string>
|
22 |
|
|
#include <algorithm>
|
23 |
|
|
#include <cctype> // old <ctype.h>
|
24 |
|
|
|
25 |
|
|
struct ToLower
|
26 |
|
|
{
|
27 |
|
|
char operator() (char c) const { return std::tolower(c); }
|
28 |
|
|
};
|
29 |
|
|
|
30 |
|
|
struct ToUpper
|
31 |
|
|
{
|
32 |
|
|
char operator() (char c) const { return std::toupper(c); }
|
33 |
|
|
};
|
34 |
|
|
|
35 |
|
|
int main()
|
36 |
|
|
{
|
37 |
|
|
std::string s ("Some Kind Of Initial Input Goes Here");
|
38 |
|
|
|
39 |
|
|
// Change everything into upper case
|
40 |
|
|
std::transform (s.begin(), s.end(), s.begin(), ToUpper());
|
41 |
|
|
|
42 |
|
|
// Change everything into lower case
|
43 |
|
|
std::transform (s.begin(), s.end(), s.begin(), ToLower());
|
44 |
|
|
|
45 |
|
|
// Change everything back into upper case, but store the
|
46 |
|
|
// result in a different string
|
47 |
|
|
std::string capital_s;
|
48 |
|
|
capital_s.resize(s.size());
|
49 |
|
|
std::transform (s.begin(), s.end(), capital_s.begin(), ToUpper());
|
50 |
|
|
}
|
51 |
|
|
</pre><p>
|
52 |
|
|
<span class="emphasis"><em>Note</em></span> that these calls all
|
53 |
|
|
involve the global C locale through the use of the C functions
|
54 |
|
|
<code class="code">toupper/tolower</code>. This is absolutely guaranteed to work --
|
55 |
|
|
but <span class="emphasis"><em>only</em></span> if the string contains <span class="emphasis"><em>only</em></span> characters
|
56 |
|
|
from the basic source character set, and there are <span class="emphasis"><em>only</em></span>
|
57 |
|
|
96 of those. Which means that not even all English text can be
|
58 |
|
|
represented (certain British spellings, proper names, and so forth).
|
59 |
|
|
So, if all your input forevermore consists of only those 96
|
60 |
|
|
characters (hahahahahaha), then you're done.
|
61 |
|
|
</p><p><span class="emphasis"><em>Note</em></span> that the
|
62 |
|
|
<code class="code">ToUpper</code> and <code class="code">ToLower</code> function objects
|
63 |
|
|
are needed because <code class="code">toupper</code> and <code class="code">tolower</code>
|
64 |
|
|
are overloaded names (declared in <code class="code"><cctype></code> and
|
65 |
|
|
<code class="code"><locale></code>) so the template-arguments for
|
66 |
|
|
<code class="code">transform<></code> cannot be deduced, as explained in
|
67 |
|
|
<a class="link" href="http://gcc.gnu.org/ml/libstdc++/2002-11/msg00180.html">this
|
68 |
|
|
message</a>.
|
69 |
|
|
|
70 |
|
|
At minimum, you can write short wrappers like
|
71 |
|
|
</p><pre class="programlisting">
|
72 |
|
|
char toLower (char c)
|
73 |
|
|
{
|
74 |
|
|
return std::tolower(c);
|
75 |
|
|
} </pre><p>(Thanks to James Kanze for assistance and suggestions on all of this.)
|
76 |
|
|
</p><p>Another common operation is trimming off excess whitespace. Much
|
77 |
|
|
like transformations, this task is trivial with the use of string's
|
78 |
|
|
<code class="code">find</code> family. These examples are broken into multiple
|
79 |
|
|
statements for readability:
|
80 |
|
|
</p><pre class="programlisting">
|
81 |
|
|
std::string str (" \t blah blah blah \n ");
|
82 |
|
|
|
83 |
|
|
// trim leading whitespace
|
84 |
|
|
string::size_type notwhite = str.find_first_not_of(" \t\n");
|
85 |
|
|
str.erase(0,notwhite);
|
86 |
|
|
|
87 |
|
|
// trim trailing whitespace
|
88 |
|
|
notwhite = str.find_last_not_of(" \t\n");
|
89 |
|
|
str.erase(notwhite+1); </pre><p>Obviously, the calls to <code class="code">find</code> could be inserted directly
|
90 |
|
|
into the calls to <code class="code">erase</code>, in case your compiler does not
|
91 |
|
|
optimize named temporaries out of existence.
|
92 |
|
|
</p></div><div class="section" title="Case Sensitivity"><div class="titlepage"><div><div><h3 class="title"><a id="strings.string.case"/>Case Sensitivity</h3></div></div></div><p>
|
93 |
|
|
</p><p>The well-known-and-if-it-isn't-well-known-it-ought-to-be
|
94 |
|
|
<a class="link" href="http://www.gotw.ca/gotw/">Guru of the Week</a>
|
95 |
|
|
discussions held on Usenet covered this topic in January of 1998.
|
96 |
|
|
Briefly, the challenge was, <span class="quote">“<span class="quote">write a 'ci_string' class which
|
97 |
|
|
is identical to the standard 'string' class, but is
|
98 |
|
|
case-insensitive in the same way as the (common but nonstandard)
|
99 |
|
|
C function stricmp()</span>”</span>.
|
100 |
|
|
</p><pre class="programlisting">
|
101 |
|
|
ci_string s( "AbCdE" );
|
102 |
|
|
|
103 |
|
|
// case insensitive
|
104 |
|
|
assert( s == "abcde" );
|
105 |
|
|
assert( s == "ABCDE" );
|
106 |
|
|
|
107 |
|
|
// still case-preserving, of course
|
108 |
|
|
assert( strcmp( s.c_str(), "AbCdE" ) == 0 );
|
109 |
|
|
assert( strcmp( s.c_str(), "abcde" ) != 0 ); </pre><p>The solution is surprisingly easy. The original answer was
|
110 |
|
|
posted on Usenet, and a revised version appears in Herb Sutter's
|
111 |
|
|
book <span class="emphasis"><em>Exceptional C++</em></span> and on his website as <a class="link" href="http://www.gotw.ca/gotw/029.htm">GotW 29</a>.
|
112 |
|
|
</p><p>See? Told you it was easy!</p><p>
|
113 |
|
|
<span class="emphasis"><em>Added June 2000:</em></span> The May 2000 issue of C++
|
114 |
|
|
Report contains a fascinating <a class="link" href="http://lafstern.org/matt/col2_new.pdf"> article</a> by
|
115 |
|
|
Matt Austern (yes, <span class="emphasis"><em>the</em></span> Matt Austern) on why
|
116 |
|
|
case-insensitive comparisons are not as easy as they seem, and
|
117 |
|
|
why creating a class is the <span class="emphasis"><em>wrong</em></span> way to go
|
118 |
|
|
about it in production code. (The GotW answer mentions one of
|
119 |
|
|
the principle difficulties; his article mentions more.)
|
120 |
|
|
</p><p>Basically, this is "easy" only if you ignore some things,
|
121 |
|
|
things which may be too important to your program to ignore. (I chose
|
122 |
|
|
to ignore them when originally writing this entry, and am surprised
|
123 |
|
|
that nobody ever called me on it...) The GotW question and answer
|
124 |
|
|
remain useful instructional tools, however.
|
125 |
|
|
</p><p><span class="emphasis"><em>Added September 2000:</em></span> James Kanze provided a link to a
|
126 |
|
|
<a class="link" href="http://www.unicode.org/reports/tr21/tr21-5.html">Unicode
|
127 |
|
|
Technical Report discussing case handling</a>, which provides some
|
128 |
|
|
very good information.
|
129 |
|
|
</p></div><div class="section" title="Arbitrary Character Types"><div class="titlepage"><div><div><h3 class="title"><a id="strings.string.character_types"/>Arbitrary Character Types</h3></div></div></div><p>
|
130 |
|
|
</p><p>The <code class="code">std::basic_string</code> is tantalizingly general, in that
|
131 |
|
|
it is parameterized on the type of the characters which it holds.
|
132 |
|
|
In theory, you could whip up a Unicode character class and instantiate
|
133 |
|
|
<code class="code">std::basic_string<my_unicode_char></code>, or assuming
|
134 |
|
|
that integers are wider than characters on your platform, maybe just
|
135 |
|
|
declare variables of type <code class="code">std::basic_string<int></code>.
|
136 |
|
|
</p><p>That's the theory. Remember however that basic_string has additional
|
137 |
|
|
type parameters, which take default arguments based on the character
|
138 |
|
|
type (called <code class="code">CharT</code> here):
|
139 |
|
|
</p><pre class="programlisting">
|
140 |
|
|
template <typename CharT,
|
141 |
|
|
typename Traits = char_traits<CharT>,
|
142 |
|
|
typename Alloc = allocator<CharT> >
|
143 |
|
|
class basic_string { .... };</pre><p>Now, <code class="code">allocator<CharT></code> will probably Do The Right
|
144 |
|
|
Thing by default, unless you need to implement your own allocator
|
145 |
|
|
for your characters.
|
146 |
|
|
</p><p>But <code class="code">char_traits</code> takes more work. The char_traits
|
147 |
|
|
template is <span class="emphasis"><em>declared</em></span> but not <span class="emphasis"><em>defined</em></span>.
|
148 |
|
|
That means there is only
|
149 |
|
|
</p><pre class="programlisting">
|
150 |
|
|
template <typename CharT>
|
151 |
|
|
struct char_traits
|
152 |
|
|
{
|
153 |
|
|
static void foo (type1 x, type2 y);
|
154 |
|
|
...
|
155 |
|
|
};</pre><p>and functions such as char_traits<CharT>::foo() are not
|
156 |
|
|
actually defined anywhere for the general case. The C++ standard
|
157 |
|
|
permits this, because writing such a definition to fit all possible
|
158 |
|
|
CharT's cannot be done.
|
159 |
|
|
</p><p>The C++ standard also requires that char_traits be specialized for
|
160 |
|
|
instantiations of <code class="code">char</code> and <code class="code">wchar_t</code>, and it
|
161 |
|
|
is these template specializations that permit entities like
|
162 |
|
|
<code class="code">basic_string<char,char_traits<char>></code> to work.
|
163 |
|
|
</p><p>If you want to use character types other than char and wchar_t,
|
164 |
|
|
such as <code class="code">unsigned char</code> and <code class="code">int</code>, you will
|
165 |
|
|
need suitable specializations for them. For a time, in earlier
|
166 |
|
|
versions of GCC, there was a mostly-correct implementation that
|
167 |
|
|
let programmers be lazy but it broke under many situations, so it
|
168 |
|
|
was removed. GCC 3.4 introduced a new implementation that mostly
|
169 |
|
|
works and can be specialized even for <code class="code">int</code> and other
|
170 |
|
|
built-in types.
|
171 |
|
|
</p><p>If you want to use your own special character class, then you have
|
172 |
|
|
<a class="link" href="http://gcc.gnu.org/ml/libstdc++/2002-08/msg00163.html">a lot
|
173 |
|
|
of work to do</a>, especially if you with to use i18n features
|
174 |
|
|
(facets require traits information but don't have a traits argument).
|
175 |
|
|
</p><p>Another example of how to specialize char_traits was given <a class="link" href="http://gcc.gnu.org/ml/libstdc++/2002-08/msg00260.html">on the
|
176 |
|
|
mailing list</a> and at a later date was put into the file <code class="code">
|
177 |
|
|
include/ext/pod_char_traits.h</code>. We agree
|
178 |
|
|
that the way it's used with basic_string (scroll down to main())
|
179 |
|
|
doesn't look nice, but that's because <a class="link" href="http://gcc.gnu.org/ml/libstdc++/2002-08/msg00236.html">the
|
180 |
|
|
nice-looking first attempt</a> turned out to <a class="link" href="http://gcc.gnu.org/ml/libstdc++/2002-08/msg00242.html">not
|
181 |
|
|
be conforming C++</a>, due to the rule that CharT must be a POD.
|
182 |
|
|
(See how tricky this is?)
|
183 |
|
|
</p></div><div class="section" title="Tokenizing"><div class="titlepage"><div><div><h3 class="title"><a id="strings.string.token"/>Tokenizing</h3></div></div></div><p>
|
184 |
|
|
</p><p>The Standard C (and C++) function <code class="code">strtok()</code> leaves a lot to
|
185 |
|
|
be desired in terms of user-friendliness. It's unintuitive, it
|
186 |
|
|
destroys the character string on which it operates, and it requires
|
187 |
|
|
you to handle all the memory problems. But it does let the client
|
188 |
|
|
code decide what to use to break the string into pieces; it allows
|
189 |
|
|
you to choose the "whitespace," so to speak.
|
190 |
|
|
</p><p>A C++ implementation lets us keep the good things and fix those
|
191 |
|
|
annoyances. The implementation here is more intuitive (you only
|
192 |
|
|
call it once, not in a loop with varying argument), it does not
|
193 |
|
|
affect the original string at all, and all the memory allocation
|
194 |
|
|
is handled for you.
|
195 |
|
|
</p><p>It's called stringtok, and it's a template function. Sources are
|
196 |
|
|
as below, in a less-portable form than it could be, to keep this
|
197 |
|
|
example simple (for example, see the comments on what kind of
|
198 |
|
|
string it will accept).
|
199 |
|
|
</p><pre class="programlisting">
|
200 |
|
|
#include <string>
|
201 |
|
|
template <typename Container>
|
202 |
|
|
void
|
203 |
|
|
stringtok(Container &container, string const &in,
|
204 |
|
|
const char * const delimiters = " \t\n")
|
205 |
|
|
{
|
206 |
|
|
const string::size_type len = in.length();
|
207 |
|
|
string::size_type i = 0;
|
208 |
|
|
|
209 |
|
|
while (i < len)
|
210 |
|
|
{
|
211 |
|
|
// Eat leading whitespace
|
212 |
|
|
i = in.find_first_not_of(delimiters, i);
|
213 |
|
|
if (i == string::npos)
|
214 |
|
|
return; // Nothing left but white space
|
215 |
|
|
|
216 |
|
|
// Find the end of the token
|
217 |
|
|
string::size_type j = in.find_first_of(delimiters, i);
|
218 |
|
|
|
219 |
|
|
// Push token
|
220 |
|
|
if (j == string::npos)
|
221 |
|
|
{
|
222 |
|
|
container.push_back(in.substr(i));
|
223 |
|
|
return;
|
224 |
|
|
}
|
225 |
|
|
else
|
226 |
|
|
container.push_back(in.substr(i, j-i));
|
227 |
|
|
|
228 |
|
|
// Set up for next loop
|
229 |
|
|
i = j + 1;
|
230 |
|
|
}
|
231 |
|
|
}
|
232 |
|
|
</pre><p>
|
233 |
|
|
The author uses a more general (but less readable) form of it for
|
234 |
|
|
parsing command strings and the like. If you compiled and ran this
|
235 |
|
|
code using it:
|
236 |
|
|
</p><pre class="programlisting">
|
237 |
|
|
std::list<string> ls;
|
238 |
|
|
stringtok (ls, " this \t is\t\n a test ");
|
239 |
|
|
for (std::list<string>const_iterator i = ls.begin();
|
240 |
|
|
i != ls.end(); ++i)
|
241 |
|
|
{
|
242 |
|
|
std::cerr << ':' << (*i) << ":\n";
|
243 |
|
|
} </pre><p>You would see this as output:
|
244 |
|
|
</p><pre class="programlisting">
|
245 |
|
|
:this:
|
246 |
|
|
:is:
|
247 |
|
|
:a:
|
248 |
|
|
:test: </pre><p>with all the whitespace removed. The original <code class="code">s</code> is still
|
249 |
|
|
available for use, <code class="code">ls</code> will clean up after itself, and
|
250 |
|
|
<code class="code">ls.size()</code> will return how many tokens there were.
|
251 |
|
|
</p><p>As always, there is a price paid here, in that stringtok is not
|
252 |
|
|
as fast as strtok. The other benefits usually outweigh that, however.
|
253 |
|
|
</p><p><span class="emphasis"><em>Added February 2001:</em></span> Mark Wilden pointed out that the
|
254 |
|
|
standard <code class="code">std::getline()</code> function can be used with standard
|
255 |
|
|
<code class="code">istringstreams</code> to perform
|
256 |
|
|
tokenizing as well. Build an istringstream from the input text,
|
257 |
|
|
and then use std::getline with varying delimiters (the three-argument
|
258 |
|
|
signature) to extract tokens into a string.
|
259 |
|
|
</p></div><div class="section" title="Shrink to Fit"><div class="titlepage"><div><div><h3 class="title"><a id="strings.string.shrink"/>Shrink to Fit</h3></div></div></div><p>
|
260 |
|
|
</p><p>From GCC 3.4 calling <code class="code">s.reserve(res)</code> on a
|
261 |
|
|
<code class="code">string s</code> with <code class="code">res < s.capacity()</code> will
|
262 |
|
|
reduce the string's capacity to <code class="code">std::max(s.size(), res)</code>.
|
263 |
|
|
</p><p>This behaviour is suggested, but not required by the standard. Prior
|
264 |
|
|
to GCC 3.4 the following alternative can be used instead
|
265 |
|
|
</p><pre class="programlisting">
|
266 |
|
|
std::string(str.data(), str.size()).swap(str);
|
267 |
|
|
</pre><p>This is similar to the idiom for reducing
|
268 |
|
|
a <code class="code">vector</code>'s memory usage
|
269 |
|
|
(see <a class="link" href="../faq.html#faq.size_equals_capacity" title="7.8.">this FAQ
|
270 |
|
|
entry</a>) but the regular copy constructor cannot be used
|
271 |
|
|
because libstdc++'s <code class="code">string</code> is Copy-On-Write.
|
272 |
|
|
</p><p>In <a class="link" href="status.html#status.iso.2011" title="C++ 2011">C++11</a> mode you can call
|
273 |
|
|
<code class="code">s.shrink_to_fit()</code> to achieve the same effect as
|
274 |
|
|
<code class="code">s.reserve(s.size())</code>.
|
275 |
|
|
</p></div><div class="section" title="CString (MFC)"><div class="titlepage"><div><div><h3 class="title"><a id="strings.string.Cstring"/>CString (MFC)</h3></div></div></div><p>
|
276 |
|
|
</p><p>A common lament seen in various newsgroups deals with the Standard
|
277 |
|
|
string class as opposed to the Microsoft Foundation Class called
|
278 |
|
|
CString. Often programmers realize that a standard portable
|
279 |
|
|
answer is better than a proprietary nonportable one, but in porting
|
280 |
|
|
their application from a Win32 platform, they discover that they
|
281 |
|
|
are relying on special functions offered by the CString class.
|
282 |
|
|
</p><p>Things are not as bad as they seem. In
|
283 |
|
|
<a class="link" href="http://gcc.gnu.org/ml/gcc/1999-04n/msg00236.html">this
|
284 |
|
|
message</a>, Joe Buck points out a few very important things:
|
285 |
|
|
</p><div class="itemizedlist"><ul class="itemizedlist"><li class="listitem"><p>The Standard <code class="code">string</code> supports all the operations
|
286 |
|
|
that CString does, with three exceptions.
|
287 |
|
|
</p></li><li class="listitem"><p>Two of those exceptions (whitespace trimming and case
|
288 |
|
|
conversion) are trivial to implement. In fact, we do so
|
289 |
|
|
on this page.
|
290 |
|
|
</p></li><li class="listitem"><p>The third is <code class="code">CString::Format</code>, which allows formatting
|
291 |
|
|
in the style of <code class="code">sprintf</code>. This deserves some mention:
|
292 |
|
|
</p></li></ul></div><p>
|
293 |
|
|
The old libg++ library had a function called form(), which did much
|
294 |
|
|
the same thing. But for a Standard solution, you should use the
|
295 |
|
|
stringstream classes. These are the bridge between the iostream
|
296 |
|
|
hierarchy and the string class, and they operate with regular
|
297 |
|
|
streams seamlessly because they inherit from the iostream
|
298 |
|
|
hierarchy. An quick example:
|
299 |
|
|
</p><pre class="programlisting">
|
300 |
|
|
#include <iostream>
|
301 |
|
|
#include <string>
|
302 |
|
|
#include <sstream>
|
303 |
|
|
|
304 |
|
|
string f (string& incoming) // incoming is "foo N"
|
305 |
|
|
{
|
306 |
|
|
istringstream incoming_stream(incoming);
|
307 |
|
|
string the_word;
|
308 |
|
|
int the_number;
|
309 |
|
|
|
310 |
|
|
incoming_stream >> the_word // extract "foo"
|
311 |
|
|
>> the_number; // extract N
|
312 |
|
|
|
313 |
|
|
ostringstream output_stream;
|
314 |
|
|
output_stream << "The word was " << the_word
|
315 |
|
|
<< " and 3*N was " << (3*the_number);
|
316 |
|
|
|
317 |
|
|
return output_stream.str();
|
318 |
|
|
} </pre><p>A serious problem with CString is a design bug in its memory
|
319 |
|
|
allocation. Specifically, quoting from that same message:
|
320 |
|
|
</p><pre class="programlisting">
|
321 |
|
|
CString suffers from a common programming error that results in
|
322 |
|
|
poor performance. Consider the following code:
|
323 |
|
|
|
324 |
|
|
CString n_copies_of (const CString& foo, unsigned n)
|
325 |
|
|
{
|
326 |
|
|
CString tmp;
|
327 |
|
|
for (unsigned i = 0; i < n; i++)
|
328 |
|
|
tmp += foo;
|
329 |
|
|
return tmp;
|
330 |
|
|
}
|
331 |
|
|
|
332 |
|
|
This function is O(n^2), not O(n). The reason is that each +=
|
333 |
|
|
causes a reallocation and copy of the existing string. Microsoft
|
334 |
|
|
applications are full of this kind of thing (quadratic performance
|
335 |
|
|
on tasks that can be done in linear time) -- on the other hand,
|
336 |
|
|
we should be thankful, as it's created such a big market for high-end
|
337 |
|
|
ix86 hardware. :-)
|
338 |
|
|
|
339 |
|
|
If you replace CString with string in the above function, the
|
340 |
|
|
performance is O(n).
|
341 |
|
|
</pre><p>Joe Buck also pointed out some other things to keep in mind when
|
342 |
|
|
comparing CString and the Standard string class:
|
343 |
|
|
</p><div class="itemizedlist"><ul class="itemizedlist"><li class="listitem"><p>CString permits access to its internal representation; coders
|
344 |
|
|
who exploited that may have problems moving to <code class="code">string</code>.
|
345 |
|
|
</p></li><li class="listitem"><p>Microsoft ships the source to CString (in the files
|
346 |
|
|
MFC\SRC\Str{core,ex}.cpp), so you could fix the allocation
|
347 |
|
|
bug and rebuild your MFC libraries.
|
348 |
|
|
<span class="emphasis"><em><span class="emphasis"><em>Note:</em></span> It looks like the CString shipped
|
349 |
|
|
with VC++6.0 has fixed this, although it may in fact have been
|
350 |
|
|
one of the VC++ SPs that did it.</em></span>
|
351 |
|
|
</p></li><li class="listitem"><p><code class="code">string</code> operations like this have O(n) complexity
|
352 |
|
|
<span class="emphasis"><em>if the implementors do it correctly</em></span>. The libstdc++
|
353 |
|
|
implementors did it correctly. Other vendors might not.
|
354 |
|
|
</p></li><li class="listitem"><p>While chapters of the SGI STL are used in libstdc++, their
|
355 |
|
|
string class is not. The SGI <code class="code">string</code> is essentially
|
356 |
|
|
<code class="code">vector<char></code> and does not do any reference
|
357 |
|
|
counting like libstdc++'s does. (It is O(n), though.)
|
358 |
|
|
So if you're thinking about SGI's string or rope classes,
|
359 |
|
|
you're now looking at four possibilities: CString, the
|
360 |
|
|
libstdc++ string, the SGI string, and the SGI rope, and this
|
361 |
|
|
is all before any allocator or traits customizations! (More
|
362 |
|
|
choices than you can shake a stick at -- want fries with that?)
|
363 |
|
|
</p></li></ul></div></div></div></div><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td align="left"><a accesskey="p" href="traits.html">Prev</a> </td><td align="center"><a accesskey="u" href="bk01pt02.html">Up</a></td><td align="right"> <a accesskey="n" href="localization.html">Next</a></td></tr><tr><td align="left" valign="top">Traits </td><td align="center"><a accesskey="h" href="../index.html">Home</a></td><td align="right" valign="top"> Chapter 8.
|
364 |
|
|
Localization
|
365 |
|
|
|
366 |
|
|
</td></tr></table></div></body></html>
|