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

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

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

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

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

int ciCharCompareCchar cl. char c2) Сравнение символов без учета { регистра. Функция возвращает -1,

если с1<с2. О, если с1=с2. и 1.

если с1>с2.

int Icl = tolower(static cast<unsigned char>(cl)): См. далее int 1с2 = tolower(static cast<unsigned char>(c2)):

if (lcl<lc2) return -1; if (lcl>lc2) return 1; return 0;

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

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

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

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

int ciStringComparelmpKconst strings si, Реализация приведена далее const strings s2):

int ciStringCompareCconst strings si.const strings s2) {

if (si.size()<=s2.SizeO return ciStringCompareImpl(sl,s2): else return -ciStringCompareImpl(s2,sl);

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

int CiStringComparelmpKconst strings si,const strings s2) {

typedef pair<string::constJterator, PSCI = pair of

string::const iterator> PSCI: string::const iterator

PSCI p = mismatchC Использование ptr fun

sl.beginO,sl.end(). рассматривается

s2.begin(), в совете 41 not2(pt r fun(с i Cha rCompa re)));

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

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

else return -1: либо si короче s2

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

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

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

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

bool ciCharLessCchar cl, char c2) Вернуть признак того.

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

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

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

tolower(static cast<unsigned char>(cl))< объясняется, почему tolower(static cast<unsigned char>(c2)); вместо функции может } оказаться предпочтительным

объект функции bool ciStringCompareCconst strings si, const strings s2) {

return lexicographical compare(sl.begin(),sl.end(), Описание

s2.begin().s2.end(), алгоритма ciCharLess); приведено далее

Нет, я не буду долго хранить секрет. Самое длинное имя у алгоритма set synmetr i c di fference.

Если вы знаете, как работает 1 exi cographi cal compare, приведенный выше фрагмент понятен без объяснений, а если не знаете - это легко поправимо.

Алгоритм lexicographical compare является обобщенной версией strcmp. Функция strcmp работает только с символьными массивами, а lexicographical compare