щенную реализацию из стандартной библиотеки. Остальные реализации исследуются в главе 4.

Различие между строкой и массивом символов связано с понятием длины. В обоих случаях представляется непрерывная область памяти, но длина массива устанавливается в момент его создания, а длина строки может изменяться в процессе выполнения профаммы. Это различие влечет интересные последствия, которые мы вкратце обсудим.

Для строки необходимо зарезервировать память либо во время компиляции, путем объявления массива символов с фиксированной длиной, либо во время выполнения, через вызов функции new[]. После выделения памяти массиву его можно заполнять символами с начала и до символа завершения строки. Без символа завершения строка представляет собой обыкновенный массив символов. Символ завершения строки позволяет применять более высокий уровень абстракции, позволяюший рассматривать только часть массива (от начала до символа завершения) как содержащую значимую информацию. Символ завершения имеет значение 0. Его также обозначают так: \0.

Например, чтобы найти длину строки, можно подсчитать количество символов от начала и до символа завершения. В табл. 3.2 перечислены простые операции, которые часто выполняются со строками. Все они предусматривают сканирование строк с начала и до конца. Многие из этих функций содержатся в библиотеках, объявленных в файле <string.h>. Однако профаммисты для простых приложений часто используют слегка измененные версии в линейном коде. Для живучести функций, реапизу-ющих те же операции, необходим дополнительный код проверки условий ошибок. Этот код представлен здесь не только с целью демонстрации его простоты, но и для наглядной демонстрации характеристик производительности.

Таблица 3.2 Элементарные операции со строками

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

Версии с индексированным массивом

Вычисление длины строки (strien(a))

for (i = 0; a[i] != 0; i++) ; return i ;

Копирование (s trcpy (a, b))

for (i = 0; (a[i] = b[i]) != 0; i++ ;

Сравнение (strcmp(a, b))

for (i = 0; a[i] = bti] != 0; i++) ;

if (a[i] == 0) return 0; return ati] - bti];

Сравнение (префикс) (strncmp(a, b, n))

for (i = 0; i < n && ati] != 0; i++)

if (ati] != bti]) return ati] - bti]; return 0;

Присоединение (strcat(a, Ь))

strcpy(a+strlen(a) , b)

Эквивалентные версии с указателями

Вычисление длины строки (strlen(a))

b = а; while (*b++) ; return b-a-1;

Копирование (s trcpy (a, b))

while (*a++ = *b++) ;

Сравнение (strcn?) (a, b))

while (*a++ = *b++)

if (*(a-l) = 0) return 0;

return *(a-l) - *(b-l);

Одной из наиболее важных является операция сравнения (compare). Она указывает, какая из двух строк должна первой значиться в словаре (dictionary). Для простоты изложения предполагается, что словарь идеализирован (поскольку реальные правила для строк, содержащих знаки пунктуации, буквы нижнего и верхнего регистра, числа и пр. довольно сложны), а строки сравниваются посимвольно от начала и до конца. Такой порядок называется лексикографическим. Кроме того, функция сравнения используется для определения эквивалентности строк. По соглашению функция сравнения возвращает отрицательное число, если строка первого аргумента находится в словаре перед второй строкой, положительное число в противном случае и ноль, когда строки идентичны. Важно отметить, что выполнение проверки равенства не то же, что определение, равны ли два указателя строк - если два указателя строк равны, то же относится к указываемым строкам (это одна и та же строка), но возможны различные указатели строк, которые ссылаются на равные строки (идентичные последовательности символов). Хранение информации в строках с последующей обработкой либо доступом к ней путем сравнения строк, применяется во множестве приложений. Поэтому операция сравнения имеет особое значение. Характерный пример содержится в разделе 3.7, а также во многих других местах книги.

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

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

for (i = 0; i < strlen(a); i++)

if (strncmp(Sa[i] , p, strlen(p)) == 0) cout i ;

К сожалению, время выполнения этого фрагмента кода пропорционально, как минимум, квадрату длины а независимо от кода тела цикла, поскольку для определения длины строки а каждый раз выполняется ее полный перебор. Эти затраты времени велики и даже неприемлемы: выполнение программы для проверки наличия определенного слова в данной книге (содержащей более миллиона символов) потребует триллионов операций. Подобные проблемы трудно обнаружить, поскольку программа может хорошо работать с небольшими строками на этапе отладки, но сильно замедляться, если не полностью затормаживаться при решении реальных задач. Более того, этих проблем можно избегать только будучи осведомленным о них!

Программа 3.15 Поиск строки

Эта программа обнаруживает все вхождения введенного из командной строки слова в строке текста (предположительно намного большей длины). Строка текста объявляется в виде массива символов фиксированной длины (можно также использовать оператор new[], как в программе 3.6). Чтение строки выполняется из стандартного ввода с помощью функции cin.get(). Память для слова (аргумента командной строки) выделяется системой перед вызовом программы, а указатель строки содержится в элементе argv[1]. Для каждой начальной позиции i в строке а предпринимается попытка сравнить подстроку, которая начинается с этой позиции, со словом р. Эквивалентность проверяется символ за символом. Как только достигается конец слова р, печатается начальная позиция i вхождения этого слова в текст.

#include <iostream.h> iinclude <string.h> static const int N = 10000; int main(int argc, char *argv[]) { int i; char t; char a[N], *p = argv[l]; for (i = 0; i < N-l; a[i] = t, i++)

if (!cin.get(t)) break; a[i] = 0;

for (i = 0; a[i] = 0; i++) { int j;

for (j = 0; p[j] != 0; j++) if (a[i+j] != p[j]) break; if (p[j] == 0) cout i ;

cout endl;

Этот вид ошибок называется потерей быстродействия (performance bug), поскольку код может быть корректным, но его выполнение окажется не настоль эффективным, как ожидалось. Прежде чем приступить к изучению эффективных алгоритмов, необходимо надежно устранить потери быстродействия подобного типа. Стандартные библиотеки обладают многими достоинствами, однако следует учитывать потенциальные недостатки их использования для реализации простых функций рассмотренного типа.

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