СТРОКИ

Дисциплина «Основы алгоритмизации и программирования»

СТРОКИ

В С++ имеется набор встроенных типов данных для представления целых и вещественных чисел, символов, а также тип данных “символьный массив”, который служит для хранения символьных строк. Тип char служит для хранения отдельных символов и небольших целых чисел. Он занимает один машинный байт. Типы short, int и long предназначены для представления целых чисел. Эти типы различаются только диапазоном значений, которые могут принимать числа, а конкретные размеры перечисленных типов зависят от реализации. Обычно short занимает половину машинного слова, int – одно слово, long – одно или два слова. В 32-битных системах int и long, как правило, одного размера.

Типы float, double и long double предназначены для чисел с плавающей точкой и различаются точностью представления (количеством значащих разрядов) и диапазоном. Обычно float (одинарная точность) занимает одно машинное слово, double (двойная точность) – два, а long double (расширенная точность) – три.

char, short, int и long вместе составляют целые типы, которые, в свою очередь, могут быть знаковыми (signed) и беззнаковыми (unsigned). В знаковых типах самый левый бит служит для хранения знака (0 – плюс, 1 – минус), а оставшиеся биты содержат значение. В беззнаковых типах все биты используются для значения. 8-битовый тип signed char может представлять значения от -128 до 127, а unsigned char – от 0 до 255.

Когда в программе встречается некоторое число, например 1, то это число называется литералом, или литеральной константой. Константой, потому что мы не можем изменить его значение, и литералом, потому что его значение фигурирует в тексте программы. Литерал является неадресуемой величиной: хотя реально он, конечно, хранится в памяти машины, нет никакого способа узнать его адрес. Каждый литерал имеет определенный тип. Так, 0 имеет тип int, 3.14159 – тип double.

Литералы целых типов можно записать в десятичном, восьмеричном и шестнадцатеричном виде. Вот как выглядит число 20, представленное десятичным, восьмеричным и шестнадцатеричным литералами:

20 // десятичный

024 // восьмеричный

0х14 // шестнадцатеричный

Если литерал начинается с 0, он трактуется как восьмеричный, если с 0х или 0Х, то как шестнадцатеричный. Привычная запись рассматривается как десятичное число.

По умолчанию все целые литералы имеют тип signed int. Можно явно определить целый литерал как имеющий тип long, приписав в конце числа букву L (используется как прописная L, так и строчная l, однако для удобства чтения не следует употреблять строчную: ее легко перепутать с

1). Буква U (или u) в конце определяет литерал как unsigned int, а две буквы – UL или LU – как тип unsigned long. Например:

128u 1024UL 1L 8Lu

Литералы, представляющие действительные числа, могут быть записаны как с десятичной точкой, так и в научной (экспоненциальной) нотации. По умолчанию они имеют тип double. Для явного указания типа float нужно использовать суффикс F или f, а для long double — L или l, но только в случае записи с десятичной точкой. Например:

3.14159F 0/1f 12.345L 0.0

3el 1.0E-3E 2. 1.0L

Слова true и false являются литералами типа bool.

Представимые литеральные символьные константы записываются как символы в одинарных кавычках. Например:

‘a’ ‘2’ ‘,’ ‘ ‘ (пробел)

Специальные символы (табуляция, возврат каретки) записываются как escape-последовательности . Определены следующие такие последовательности (они начинаются с символа обратной косой черты):

новая строка \n

горизонтальная табуляция \t

забой \b

вертикальная табуляция \v

возврат каретки \r

прогон листа \f

звонок \a

обратная косая черта \\

вопрос \?

одиночная кавычка \’

двойная кавычка \»

escape-последовательность общего вида имеет форму \ooo, где ooo – от одной до трех восьмеричных цифр. Это число является кодом символа. Используя ASCII-код, мы можем написать следующие литералы:

\7 (звонок) \14 (новая строка)

\0 (null) \062 (‘2’)

Символьный литерал может иметь префикс L (например, L’a’), что означает специальный тип wchar_t – двухбайтовый символьный тип, который применяется для хранения символов национальных алфавитов, если они не могут быть представлены обычным типом char, как, например, китайские или японские буквы.

Строковый литерал – строка символов, заключенная в двойные кавычки. Такой литерал может занимать и несколько строк, в этом случае в конце строки ставится обратная косая черта. Специальные символы могут быть представлены своими escape-последовательностями. Вот примеры строковых литералов:

«» (пустая строка)

«a»

«\nCC\toptions\tfile.[cC]\n»

«a multi-line \

string literal signals its \

continuation with a backslash»

Фактически строковый литерал представляет собой массив символьных констант, где по соглашению языков С и С++ последним элементом всегда является специальный символ с кодом 0 (\0).

Литерал ‘A’ задает единственный символ А, а строковый литерал «А» – массив из двух элементов: ‘А’ и \0 (пустого символа).

Раз существует тип wchar_t, существуют и литералы этого типа, обозначаемые, как и в случае с отдельными символами, префиксом L:

L»a wide string literal»

Строковый литерал типа wchar_t – это массив символов того же типа, завершенный нулем.

Если в тесте программы идут подряд два или несколько строковых литералов (типа char или wchar_t), компилятор соединяет их в одну строку. Например, следующий текст

«two» «some»

породит массив из восьми символов – twosome и завершающий нулевой символ. Результат конкатенации строк разного типа не определен. Если написать:

// this is not a good idea

«two» L»some»

то на каком-то компьютере результатом будет некоторая осмысленная строка, а на другом может оказаться нечто совсем иное. Программы, использующие особенности реализации того или иного компилятора или операционной системы, являются непереносимыми. Мы крайне не рекомендуем пользоваться такими конструкциями.

Упражнение 1

Объясните разницу в определениях следующих литералов:

(a) ‘a’, L’a’, «a», L»a»

(b) 10, 10u, 10L, 10uL, 012, 0*C

(c) 3.14, 3.14f, 3.14L

Упражнение.2

Какие ошибки допущены в приведенных ниже примерах?

(a) «Who goes with F\144rgus?\014»

(b) 3.14e1L

(c) «two» L»some»

(d) 1024f

(e) 3.14UL

(f) «multiple line

comment»

Строковые типы

В С++ поддерживаются два типа строк – встроенный тип, доставшийся от С, и класс string из стандартной библиотеки С++. Класс string предоставляет гораздо больше возможностей и поэтому удобней в применении, однако на практике нередки ситуации, когда необходимо пользоваться встроенным типом либо хорошо понимать, как он устроен. (Одним из примеров может являться разбор параметров командной строки, передаваемых в функцию main().

Встроенный строковый тип

Как уже было сказано, встроенный строковый тип перешел к С++ по наследству от С. Строка символов хранится в памяти как массив, и доступ к ней осуществляется при помощи указателя типа char*. Стандартная библиотека С предоставляет набор функций для манипулирования строками. Например:

// возвращает длину строки

int strlen( const char* );

// сравнивает две строки

int strcmp( const char*, const char* );

// копирует одну строку в другую

char* strcpy( char*, const char* );

Стандартная библиотека С является частью библиотеки С++. Для ее использования мы должны включить заголовочный файл:

#include <cstring>

Указатель на char, с помощью которого мы обращаемся к строке, указывает на соответствующий строке массив символов. Даже когда мы пишем строковый литерал, например

const char *st = «Цена бутылки вина\n»;

компилятор помещает все символы строки в массив и затем присваивает st адрес первого элемента массива. Как можно работать со строкой, используя такой указатель?

Обычно для перебора символов строки применяется адресная арифметика. Поскольку строка всегда заканчивается нулевым символом, можно увеличивать указатель на 1, пока очередным символом не станет нуль. Например:

while (*st++ ) { … }

st разыменовывается, и получившееся значение проверяется на истинность. Любое отличное от нуля значение считается истинным, и, следовательно, цикл заканчивается, когда будет достигнут символ с кодом 0. Операция инкремента ++ прибавляет 1 к указателю st и таким образом сдвигает его к следующему символу.

Вот как может выглядеть реализация функции, возвращающей длину строки. Отметим, что, поскольку указатель может содержать нулевое значение (ни на что не указывать), перед операцией разыменования его следует проверять:

int string_length( const char *st )

{

int cnt = 0;

if ( st )

while ( *st++ )

++cnt;

return cnt;

}

Строка встроенного типа может считаться пустой в двух случаях: если указатель на строку имеет нулевое значение (тогда у нас вообще нет никакой строки) или указывает на массив, состоящий из одного нулевого символа (то есть на строку, не содержащую ни одного значимого символа).

// pc1 не адресует никакого массива символов

char *pc1 = 0;

// pc2 адресует нулевой символ

const char *pc2 = «»;

Для начинающего программиста использование строк встроенного типа чревато ошибками из-за слишком низкого уровня реализации и невозможности обойтись без адресной арифметики. Ниже мы покажем некоторые типичные погрешности, допускаемые новичками. Задача проста: вычислить длину строки. Первая версия неверна. Исправьте ее.

#include <iostream>

const char *st = «Цена бутылки вина\n»;

int main() {

int len = 0;

while ( st++ ) ++len;

cout << len << «: » << st;

return 0;

}

В этой версии указатель st не разыменовывается. Следовательно, на равенство 0 проверяется не символ, на который указывает st, а сам указатель. Поскольку изначально этот указатель имел ненулевое значение (адрес строки), то он никогда не станет равным нулю, и цикл будет выполняться бесконечно.

Во второй версии программы эта погрешность устранена. Программа успешно заканчивается, однако полученный результат неправилен. Где мы не правы на этот раз?

#include <iostream>

const char *st = «Цена бутылки вина\n»;

int main()

{

int len = 0;

while ( *st++ ) ++len;

cout << len << «: » << st << endl;

return 0;

}

Ошибка состоит в том, что после завершения цикла указатель st адресует не исходный символьный литерал, а символ, расположенный в памяти после завершающего нуля этого литерала. В этом месте может находиться что угодно, и выводом программы будет случайная последовательность символов.

Можно попробовать исправить эту ошибку:

st = st – len;

cout << len << «: » << st;

Теперь наша программа выдает что-то осмысленное, но не до конца. Ответ выглядит так:

18: ена бутылки вина

Мы забыли учесть, что заключительный нулевой символ не был включен в подсчитанную длину. st должен быть смещен на длину строки плюс 1. Вот, наконец, правильный оператор:

st = st – len — 1;

а вот и и правильный результат:

18: Цена бутылки вина

Однако нельзя сказать, что наша программа выглядит элегантно. Оператор

st = st – len — 1;

добавлен для того, чтобы исправить ошибку, допущенную на раннем этапе проектирования программы, – непосредственное увеличение указателя st. Этот оператор не вписывается в логику программы, и код теперь трудно понять. Исправления такого рода часто называют заплатками – нечто, призванное заткнуть дыру в существующей программе. Гораздо лучшим решением было бы пересмотреть логику. Одним из вариантов в нашем случае может быть определение второго указателя, инициализированного значением st:

const char *p = st;

Теперь p можно использовать в цикле вычисления длины, оставив значение st неизменным:

while ( *p++ )

3.4.2. Класс string

Как мы только что видели, применение встроенного строкового типа чревато ошибками и не очень удобно из-за того, что он реализован на слишком низком уровне. Поэтому достаточно распространена разработка собственного класса или классов для представления строкового типа – чуть ли не каждая компания, отдел или индивидуальный проект имели свою собственную реализацию строки. Да что говорить, в предыдущих двух

изданиях этой книги мы делали то же самое! Это порождало проблемы совместимости и переносимости программ. Реализация стандартного класса string стандартной библиотекой С++ призвана была положить конец этому изобретению велосипедов.

Попробуем специфицировать минимальный набор операций, которыми должен обладать класс string:

инициализация массивом символов (строкой встроенного типа) или другим объектом типа string. Встроенный тип не обладает второй возможностью;

копирование одной строки в другую. Для встроенного типа приходится использовать функцию strcpy();

доступ к отдельным символам строки для чтения и записи. Во встроенном массиве для этого применяется операция взятия индекса или косвенная адресация;

сравнение двух строк на равенство. Для встроенного типа используется функция strcmp();

конкатенация двух строк, получая результат либо как третью строку, либо вместо одной из исходных. Для встроенного типа применяется функция strcat(), однако чтобы получить результат в новой строке, необходимо последовательно задействовать функции strcpy() и strcat();

вычисление длины строки. Узнать длину строки встроенного типа можно с помощью функции strlen();

возможность узнать, пуста ли строка. У встроенных строк для этой цели приходится проверять два условия:

char str = 0;

//…

if ( ! str || ! *str )

return;

Класс string стандартной библиотеки С++ реализует все перечисленные операции (и гораздо больше, как мы увидим в главе 6). В данном разделе мы научимся пользоваться основными операциями этого класса.

Для того чтобы использовать объекты класса string, необходимо включить соответствующий заголовочный файл:

#include <string>

Вот пример строки из предыдущего раздела, представленной объектом типа string и инициализированной строкой символов:

#include <string>

string st( «Цена бутылки вина\n» );

Длину строки возвращает функция-член size() (длина не включает завершающий нулевой символ).

cout << «Длина «

<< st

<< «: » << st.size()

<< » символов, включая символ новой строки\n»;

Вторая форма определения строки задает пустую строку:

string st2; // пустая строка

Как мы узнаем, пуста ли строка? Конечно, можно сравнить ее длину с 0:

if ( ! st.size() )

// правильно: пустая

Однако есть и специальный метод empty(), возвращающий true для пустой строки и false для непустой:

if ( st.empty() )

// правильно: пустая

Третья форма конструктора инициализирует объект типа string другим объектом того же типа:

string st3( st );

Строка st3 инициализируется строкой st. Как мы можем убедиться, что эти строки совпадают? Воспользуемся оператором сравнения (==):

if ( st == st3 )

// инициализация сработала

Как скопировать одну строку в другую? С помощью обычной операции присваивания:

st2 = st3; // копируем st3 в st2

Для конкатенации строк используется операция сложения (+) или операция сложения с присваиванием (+=). Пусть даны две строки:

string s1( «hello, » );

string s2( «world\n» );

Мы можем получить третью строку, состоящую из конкатенации первых двух, таким образом:

string s3 = s1 + s2;

Если же мы хотим добавить s2 в конец s1, мы должны написать:

s1 += s2;

Операция сложения может конкатенировать объекты класса string не только между собой, но и со строками встроенного типа. Можно переписать пример, приведенный выше, так, чтобы специальные символы и знаки препинания представлялись встроенным типом, а значимые слова – объектами класса string:

const char *pc = «, «;

string s1( «hello» );

string s2( «world» );

string s3 = s1 + pc + s2 + «\n»;

Подобные выражения работают потому, что компилятор знает, как автоматически преобразовывать объекты встроенного типа в объекты класса string. Возможно и простое присваивание встроенной строки объекту string:

string s1;

const char *pc = «a character array»;

s1 = pc; // правильно

Обратное преобразование, однако, не работает. Попытка выполнить следующую инициализацию строки встроенного типа вызовет ошибку компиляции:

char *str = s1; // ошибка компиляции

Чтобы осуществить такое преобразование, необходимо явно вызвать функцию-член с несколько странным названием c_str():

char *str = s1.c_str(); // почти правильно

Функция c_str() возвращает указатель на символьный массив, содержащий строку объекта string в том виде, в каком она находилась бы во встроенном строковом типе.

Приведенный выше пример инициализации указателя char *str все еще не совсем корректен. c_str() возвращает указатель на константный массив, чтобы предотвратить возможность непосредственной модификации содержимого объекта через этот указатель, имеющий тип

const char *

(В следующем разделе мы расскажем о ключевом слове const). Правильный вариант инициализации выглядит так:

const char *str = s1.c_str(); // правильно

К отдельным символам объекта типа string, как и встроенного типа, можно обращаться с помощью операции взятия индекса. Вот, например, фрагмент кода, заменяющего все точки символами подчеркивания:

string str( «fa.disney.com» );

int size = str.size();

for ( int ix = 0; ix < size; ++ix )

if ( str[ ix ] == ‘.’ )

str[ ix ] = ‘_’;

Вот и все, что мы хотели сказать о классе string прямо сейчас. На самом деле, этот класс обладает еще многими интересными свойствами и возможностями. Скажем, предыдущий пример реализуется также вызовом одной-единственной функции replace():

replace( str.begin(), str.end(), ‘.’, ‘_’ );

replace() – один из обобщенных алгоритмов, с которыми мы познакомились в разделе 2.8 и которые будут детально разобраны в главе 12. Эта функция пробегает

диапазон от begin() до end(), которые возвращают указатели на начало и конец строки, и заменяет элементы, равные третьему своему параметру, на четвертый.

Упражнение 3.

Найдите ошибки в приведенных ниже операторах:

(a) char ch = «The long and winding road»;

(b) int ival = &ch;

(c) char *pc = &ival;

(d) string st( &ch );

(e) pc = 0; (i) pc = ‘0’;

(f) st = pc; (j) st = &ival;

(g) ch = pc[0]; (k) ch = *pc;

(h) pc = st; (l) *pc = ival;

Упражнение 4

Объясните разницу в поведении следующих операторов цикла:

while ( st++ )

++cnt;

while ( *st++ )

++cnt;

Упражнение 5

Даны две семантически эквивалентные программы. Первая использует встроенный строковый тип, вторая – класс string:

// ***** Реализация с использованием C-строк *****

#include <iostream>

#include <cstring>

int main()

{

int errors = 0;

const char *pc = «a very long literal string»;

for ( int ix = 0; ix < 1000000; ++ix )

{

int len = strlen( pc );

char *pc2 = new char[ len + 1 ];

strcpy( pc2, pc );

if ( strcmp( pc2, pc ))

++errors;

delete [] pc2;

}

cout << «C-строки: «

<< errors << » ошибок.\n»;

}

// ***** Реализация с использованием класса string *****

#include <iostream>

#include <string>

int main()

{

int errors = 0;

string str( «a very long literal string» );

for ( int ix = 0; ix < 1000000; ++ix )

{

int len = str.size();

string str2 = str;

if ( str != str2 )

}

cout << «класс string: «

<< errors << » ошибок.\n;

}

Что эти программы делают?

Оказывается, вторая реализация выполняется в два раза быстрее первой. Ожидали ли вы такого результата? Как вы его объясните?

Упражнение 6

Могли бы вы что-нибудь улучшить или дополнить в наборе операций класса string, приведенных в последнем разделе? Поясните свои предложения