Совет 35. Реализуйте простые сравнения строк без учета регистра символов с использованием mismatch или lexicographical_compare

Совет 35. Реализуйте простые сравнения строк без учета регистра символов с использованием mismatch или lexicographical_compare

Один из вопросов, часто задаваемых новичками в STL — «Как в STL сравниваются строки без учета регистра символов?» Простота этого вопроса обманчива. Сравнения строк без учета регистра символов могут быть очень простыми или очень сложными в зависимости от того, насколько общим должно быть ваше решение. Если игнорировать проблемы интернационализации и ограничиться строками, на которые была рассчитана функция strcmp, задача проста. Если решение должно работать со строками в языках, не поддерживаемых strcmp (то есть практически в любом языке, кроме английского), или программа должна использовать нестандартный локальный контекст, задача чрезвычайно сложна.

В этом совете рассматривается простой вариант, поскольку он достаточно наглядно демонстрирует роль STL в решении задачи (более сложный вариант связан не столько с STL, сколько с проблемами локального контекста, упоминаемыми в приложении А). Чтобы простая задача стала интереснее, мы рассмотрим два возможных решения. Программисты, разрабатывающие интерфейсы сравнения строк без учета регистра, часто определяют два разных интерфейса: первый по аналогии с strcmp возвращает отрицательное число, ноль или положительное число, а второй по аналогии с оператором < возвращает true или false. Мы рассмотрим способы реализации обоих интерфейсов вызова с применением алгоритмов STL.

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

int ciCharCompare(char c1, char c2) // Сравнение символов без учета {

// регистра. Функция возвращает -1,

// если cl<c2, 0, если cl=c2. и 1.

// если cl>c2.

int lc1 = tolower(static_cast<unsigned char>(c1));// См. Далее

int lс2 = tolower(static_cast<unsigned char>(c2));

if (lc1<lc2) return -1;

if (lc1>lc2) return 1;

return 0;

};

Функция ciCharCompare по примеру strcmp возвращает отрицательное число, ноль или положительное число в зависимости от отношения между c1 и с2. В отличие от strcmp, функция ciCharCompare перед сравнением преобразует оба параметра к нижнему регистру. Именно так и достигается игнорирование регистра символов при сравнении.

Параметр и возвращаемое значение функции tolower, как и у многих функций <cctype.h>, относятся к типу int, но эти числа (кроме EOF) должны представляться в виде unsigned char. В С и С++ тип char может быть как знаковым, так и беззнаковым (в зависимости от реализации). Если тип char является знаковым, гарантировать его возможное представление в виде unsigned char можно лишь одним способом: преобразованием типа перед вызовом tolower, этим и объясняется присутствие преобразований в приведенном выше фрагменте (в реализациях с беззнаковым типом char преобразование игнорируется). Кроме того, это объясняет сохранение возвращаемого значения tolower в переменной типа int вместо char.

При наличии chCharCompare первая из двух функций сравнения строк (с интерфейсом в стиле strcmp) пишется просто. Эта функция, ciStringCompare, возвращает отрицательное число, ноль или положительное число в зависимости от отношения между сравниваемыми строками. Функция основана на алгоритме mismatch, определяющем первую позицию в двух интервалах, в которой элементы не совпадают.

Но для вызова mismatch должны выполняться некоторые условия. В частности, необходимо проследить за тем, чтобы более короткая строка (в случае строк разной длины) передавалась в первом интервале. Вся настоящая работа выполняется функцией ciStringCompareImp, а функция ciStringCompare лишь проверяет правильность порядка аргументов и меняет знак возвращаемого значения, если аргументы пришлось переставлять:

int ciStringCompareImpl(const string& si, // Реализация приведена далее

const string& s2);

int ciStringCompare(const string& s1,const string& s2) {

if (s1.size()<=s2.size() return cStringCompareImpl(s1,s2);

else return -ciStringComparelmpl(s2,s1);

}

Внутри ciStringCompareImpl всю тяжелую работу выполняет алгоритм mismatch. Он возвращает пару итераторов, обозначающих позиции первых отличающихся символов в интервалах:

int ciStringCompareImpl(const string& si,const string& s2) {

typedef pair<string::const_iterator, // PSCI = "pair of

string::const_iterator> PSCI; // string::const_iterator"

PSCI p = mismatch( // Использование ptr_fun

s1.begin(),s1,end(), // рассматривается

s2.begin(), // в совете 41

not2(ptr_fun(сiCharCompare)));

if (p.first==s1.end()) { // Если условие истинно,

if (p.second==s2.end()) return 0; // либо si и s2 равны.

else return -1; // либо s1 короче s2

}

return ciCharCompare(*p.first,*p.second); // Отношение между строками }// соответствует отношению

// между отличающимися

// символами

Надеюсь, комментарии достаточно четко объясняют происходящее. Зная первую позицию, в которой строки различаются, можно легко определить, какая из строк предшествует другой (или же определить, что эти строки равны), В предикате, переданном mismatch, может показаться странной лишь конструкция not2(ptr_fun(ciCharCompare)). Предикат возвращает true для совпадающих символов, поскольку алгоритм mismatch прекращает работу, когда предикат возвращает false. Для этой цели нельзя использовать ciCharCompare, поскольку возвращается -1, 0 или 1, причем по аналогии с strcmp нулевое значение возвращается для совпадающих символов. Если передать ciCharCompare в качестве предиката для mismatch, С++ преобразует возвращаемое значение ciCharCompare к типу bool, а в этом типе нулю соответствует значение false — результат прямо противоположен тому, что требовалось! Аналогично, когда ciCharCompare возвращает 1 или -1, результат будет интерпретирован как true, поскольку в языке С все целые числа, отличные от нуля, считаются истинными логическими величинами. Чтобы исправить эту семантическую «смену знака», мы ставим not2 и ptr_fun перед ciCharCompare и добиваемся желаемого результата.

Второй вариант реализации ciStringCompare основан на традиционном предикате STL; такая функция может использоваться в качестве функции сравнения в ассоциативных контейнерах. Реализация проста и предельно наглядна, поскольку достаточно модифицировать ciCharCompare для получения функции сравнения символов с предикатным интерфейсом, а затем поручить всю работу по сравнению строк алгоритму lexicographical_compare, занимающему второе место в STL по длине имени:

bool ciCharLess(char c1, char c2)// Вернуть признак того,

{ // предшествует ли c1

// символу с2 без учета

return // регистра. В совете 46

tolower(static_cast<unsigned char>(c1))< // объясняется, почему

tolower(static_cast<unsigned char>(c2)); // вместо функции может

}// оказаться предпочтительным

// объект функции

bool ciStringCompare(const string& s1. const string& s2) {

return lexicographical_compare(s1.begin(),s1.end(), // Описание

s2.begin(),s2.end(), // алгоритма

ciCharLess);// приведено далее

}

Нет, я не буду долго хранить секрет. Самое длинное имя у алгоритма set_ symmetric_difference.

Если вы знаете, как работает lexicographical_compare, приведенный выше фрагмент понятен без объяснений, а если не знаете — это легко поправимо.

Алгоритм lexicographical_compare является обобщенной версией strcmp. Функция strcmp работает только с символьными массивами, а lexicographical_compare работает с интервалами значений любого типа. Кроме того, если strcmp всегда сравнивает два символа и определяет отношение между ними (равенство, меньше, больше), то lexicographical_compare может получать произвольный предикат, который определяет, удовлетворяют ли два значения пользовательскому критерию.

В предыдущем примере алгоритм lexicographical_compare должен найти первую позицию, в которой s1 и s2 различаются по критерию ciCharLess. Если для символов в этой позиции ciCharLess возвращает true, то же самое делает и lexicographical_ compare: если в первой позиции, где символы различаются, символ первой строки предшествует соответствующему символу второй строки, то первая строка предшествует второй. Алгоритм lexicographical_compare, как и strcmp, считает два интервала разных величин равными, поэтому для таких интервалов возвращается значение false: первый интервал не предшествует второму. Кроме того, по аналогии с strcmp, если первый интервал завершается до обнаружения различия, lexicographical_compare возвращает true — префикс предшествует любому интервалу, в который он входит.

Довольно о mismatch и lexicographical compare. Хотя в этой книге большое значение уделяется переносимости программ, я просто обязан упомянуть о том, что функции сравнения строк без учета регистра символов присутствуют во многих нестандартных расширениях стандартной библиотеки С. Обычно эти функции называются stricmp или strcmpi и по аналогии с функциями, приведенными в данном совете, игнорируют проблемы интернационализации. Если вы готовы частично пожертвовать переносимостью программы, если строки заведомо не содержат внутренних нуль-символов, а проблемы интернационализации вас не волнуют, то простейший способ сравнения строк без учета регистра символов вообще не связан с STL. Обе строки преобразуются в указатели const char* (см. совет 16), передаваемые при вызове stricmp или strcmpi:

int ciStringCompare(const string& si, const string& s2) {

return stricmp(sl.c_str().s2.c_str()); // В вашей системе вместо stricmp

} // может использоваться другое имя

Функции strcmp/strcmp, оптимизированные для выполнения единственной задачи, обычно обрабатывают длинные строки значительно быстрее, чем обобщенные алгоритмы msmatch и lexicographical_compare. Если быстродействие особенно важно в вашей ситуации, переход от стандартных алгоритмов STL к нестандартным функциям С вполне оправдан. Иногда самый эффективный путь использования STL заключается в том, чтобы вовремя понять, что другие способы работают лучше.