Забытые секреты кодинга №2: строковые операции в C

«…Я обнаружил, что понимание указателей в С — это не навык, а способность. При поступлении на факультет кибернетики набирается человек 200 вундеркиндов, писавших игрушки для Atari 800 на BASIC в возрасте 4 лет. Затем они весело проводят время, изучая Паскаль, но в один прекрасный день профессор заводит речь об указателях, и внезапно они не могут этого понять… 90% потока переходит на политехнический и становится отличниками, уверяя друзей, что на информатике мало девок. На самом же деле по неизвестной причине часть человечества просто рождается без той части мозга, которая понимает указатели».

(Джоэль Спольски, http://www.optim.ru/cs/2001/4/joel1/joel1.asp)

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

ВОПРОСЫ ПО СТАНДАРТНЫМ ФУНКЦИЯМ

Зачем нужны специальные функции для сравнения или копирования строк? Почему в Си не пользуются обычными операторами <, >, +, =, как в других языках?
Да, Си работает со строками совсем по-другому. Строка в Си — это указатель на символ (char). В какой-то области памяти находятся символы строки, заканчивающиеся нулевым символом '\0' — на рисунке это массив символов mom. Адрес этого массива можно передавать в строковые функции, можно извлекать из массива отдельные символы (например, mom[3] — четвертый символ) — словом, это обычная строка.

В другой части памяти может находиться указатель — переменная p, которая хранит адрес определенной части строки. Все операции со строками выполняются через указатели. Например, чтобы найти первую букву 'А', нужно вызвать функцию strchr(), которая вернет указатель на этот символ:

p = strchr(s, 'А'); // p будет указывать на первый символ 'А' в строке s

Указатели можно увеличивать и сравнивать. Например, чтобы найти следующую за 'А' букву, прибавим к указателю (адресу!) единицу:

p = strchr(s, 'А') + 1;

Если нужно узнать, какая буква расположена ближе к началу строки, 'А' или 'М', сравним указатели:

if( strchr(s, 'А') < strchr(s, 'М') )
...

Поэтому-то и пришлось ввести функции strcpy(), strcat(), strcmp() для присваивания, сложения и сравнения строк: операции «больше», «меньше», «равно» имеют для указателей другой смысл.
Почему обычное сравнение строк не работает в Си? Например, я складываю две строки и сравниваю их с третьей:

char str[200] = "сто";
strcat(str, "лица");
if(str == "столица")
printf("Равны!");

Ошибка заключается в том, что str и "столица" хотя и равны, но расположены в разных участках памяти. Поэтому указатели на них не равны. В этом примере строки будут расположены в памяти примерно так:

Чтобы сравнить «содержимое» строк, нужно вызвать функцию strcmp(). Обрати внимание, что эта функция возвращает 0, когда строки равны:

char str[200] = "сто";
strcat(str, "лица");
if(strcmp(str, "столица") == 0)
printf("Равны!");

Можно ли в C работать со строками как в Паскале или Бэйсике? То есть можно ли складывать строки плюсом, автоматически выделять под них память и все такое?
Да, можно. В MFC есть класс CString, кроме него можно назвать CStr из Snippets, и еще несколько похожих разработок. Но они всегда будут работать медленнее и занимать больше места в exe'шнике, чем обычные функции Си. Обобщенные функции выделения памяти страдают избыточностью, много времени уходит на создание промежуточных строк и бесполезное копирование между ними. Сишные функции strcmp, strchr и так далее не такие уж сложные, и если ты хорошо разберешься в них, твои программы станут быстрее и короче.

Как выделять память под строки и массивы? Прежде всего, память не выделяется автоматически, как в других языках программирования. Тебе придется подсчитать, сколько символов будет занимать строка, и создать массив нужного размера. Если строка выйдет за границы отведенного для нее массива, то возникнет баг, известный как «переполнение буфера». Взломщик может использовать эту ошибку, чтобы запустить свой вредительский exploit. Поэтому нужно проверять размер строк, полученных от юзера. Например, пользователь вводит текст в контрол, а нам нужно записать этот текст большими буквами. Это делается так:

char *s; int size;
size = SendMessage(hWndCtrl, WM_GETTEXTLENGTH, 0, 0) + 1; // Узнаем размер строки
s = (char*) malloc(size); // Выделяем size байт под строку
SendMessage(hWndCtrl, WM_GETTEXT, size, (LPARAM)s); // Копируем в этот буфер строку
CharUpper(s); // Меняем регистр
SendMessage(hWndCtrl, WM_SETTEXT, 0, (LPARAM)s); // Записываем в контрол
free(s); // Освобождаем память

Выделяя память, нужно помнить о последнем нулевом символе. Он также входит в массив, так что если длина строки — 10 символов, то нужно создавать массив длиной 11 байт. Вместо сишных функций malloc, free в C++ используют операторы new, delete. Разница только в синтаксисе, а по сути это одно и то же:

char *s; int size;
s = new char[size]; // Выделяем size байт под строку
... // Выполняем нужные операции
delete[] s; // Освобождаем память

Часто максимальный размер строки известен заранее. Например, путь к файлу в Windows не может быть длиннее MAX_PATH = 260 символов. Тогда проще ограничить длину вводимой строки (послать сообщение EM_SETLIMITTEXT), а затем использовать обычный статический массив:

char path[MAX_PATH];

Функции malloc/realloc/free и операторы new/delete обращаются к Windows, запрашивая у нее память. Если вместо них ты будешь пользоваться Windows'овскими функциями HeapAlloc, HeapRealloc, HeapFree, то сможешь выбросить из exe'шника стандартную библиотеку Си, и он станет короче примерно на 20 Кб. А код для выделения памяти будет очень похожим на
malloc/free:

HANDLE heap;
heap = GetProcessHeap(); // в начале программы
s = (char*) HeapAlloc(heap, 0, size); // Выделяем size байт под строку
HeapFree(heap, 0, s); // Освобождаем память

ПРОСТЫЕ ОПЕРАЦИИ СО СТРОКАМИ

Как выделить подстроку справа, например, имя файла? Просто найди символ, с которого начинается подстрока, и пользуйся указателем на него. На рисунке указатель filename показывает на строку «C:\WORK\FV.C», а указатель p — на часть этой строки «FV.C».

p = strrchr(filename, '\\') + 1; // Символ, следующий за последней обратной косой чертой

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

p = strrchr(filename, '\\');
*p = '\0'; // Теперь в filename записан путь к файлу

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

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

char *p = str; int n = 0;
while(p = strchr(p, 'А'))
p++, n++; // По окончании цикла n == число вхождений символа 'А' в строку str

В более удобочитаемом виде та же программа записывается следующим образом:

p = strchr(p, 'А');
while(p)
{ p++; // Продвигаемся к следующему за найденным символу
n++; // Засчитываем найденный символ
p = strchr(p, 'А');
}

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

for(i=0; i < strlen(s); ++i)
if(s[i] == 'A')
n++;

Чем лучше указатели? Да тем, что процессору не нужно при каждом проходе цикла складывать адрес начала строки s и переменную i, чтобы вычислить адрес
s[i]:

xor ecx, ecx ; ecx — это i
xor edx, edx ; edx — это n
LOOP:
cmp DWORD PTR s[ecx], 'A'
jne SHORT BYPASS
inc edx
BYPASS:
inc ecx
cmp ecx, eax
jb SHORT LOOP

Вместо этого хорошая программа просто увеличивает адрес, то есть указатель p, а не индекс i. Код тела цикла становится немного проще и быстрее:

mov ecx, offset s ; ecx — это p
xor edx, edx ; edx — это n
LOOP:
cmp BYTE PTR [ecx], 'A'
jne SHORT BYPASS
inc edx
BYPASS:
inc ecx
cmp ecx, eax
jb SHORT LOOP

Здесь нужно сказать, что интеллектуальный компилятор может «додуматься» преобразовать код с индексом в код с указателем, но слишком надеяться на это не стоит. Компилятор все же не так умен, как использующий его программист :).

Как найти первую гласную или согласную букву в строке? Для этого случая лучше всего подходят функции strpbrk() и
strspn().

p = strpbrk("стройка", "аеёиоуыэюя"); //
p – указатель на первую гласную
p = s + strspn(s, "аеёиоуыэюя"); // p – указатель на первую согласную

ПРОБЛЕМЫ С РУССКИМ ЯЗЫКОМ

Как преобразовать русские буквы в верхний или нижний регистр? Лучше всего использовать функции CharUpper() и CharLower() из библиотеки Windows (заголовочный файл windows.h). Во-первых, эти функции учитывают язык, установленный в Панели управления Windows, поэтому твоя программа будет работать правильно во всех странах и со всеми языками. Во-вторых, проще пользоваться этими функциями, чем пытаться настроить стандартные функции Си для работы с русским или изобретать что-то свое. Пример:

char *m="министр", *p="Президент";
CharUpper(m);
CharLower(p);
printf("%s %s", m, p); // Выведет «МИНИСТР президент»

Вместо указателя на строку можно передать отдельный символ или воспользоваться функциями с суффиксом -Buff, которые преобразуют указанное число символов строки:

char m[]="министр";
m[0] = (char)CharUpper((char*)(unsigned)(unsigned char)m[0]); // Министр
CharUpperBuff(m+2, 3); // МиНИСтр

Глядя на этот кусок кода, знатоки Си могут употребить немало интересных слов великого и могучего русского языка :). Но я пока не нашел другого работающего способа преобразовать тип (char) в (char*). Если кто-то найдет — пишите. Кстати, во многом это проблема программистов Microsoft. Им нужно было написать отдельное определение (макрос или inline-функцию) для CharUpper с аргументом типа
char.

В сравнении строк есть и еще одна тонкость, на которую обычно не обращают внимания. Дело в том, что коды символов не всегда соответствуют их порядку в алфавите. Например, русская буква «Ё» и специфические белорусские буквы «Ў» («у» краткое), «ї» («и» десятеричное) расположены в кодовой таблице Windows отдельно от всех остальных букв. И если ты сравниваешь слова «дерево» и «ёлка» с помощью strcmp (сравнение по кодам), то получишь, что «ёлка» меньше (ближе к началу алфавита), чем «дерево». Чтобы избежать этой ошибки, пользуйся функцией lstrcmp() из библиотеки Windows. Для примера приведу простейшую программу пузырьковой сортировки:

int APIENTRY WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance,
LPSTR lpCmdLine, int nCmdShow)
{ char *a[]={"кедр","дуб","желудь","дерево","ёлка","сосна"};
char *p, *x; unsigned i, j; char s[200];
#define N sizeof(a)/sizeof(a[0])
for(i=0; i Пузырьковая сортировка, strcmp
for(j=i+1; j if( strcmp(a[i], a[j]) > 0 )
{ x = a[i];
a[i] = a[j];
a[j] = x;
}
p = s;
p += sprintf(p, " strcmp:\n");
for(i=0; i p += sprintf(p, "%s\n", a[i]);