Эффективное использование STL, Мейерс Скотт

Эффективное использование STL

на обложку

Мейерс Скотт

Шрифт:

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

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

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

// если c1 < c2, 0, если c1 = c2, и 1,

// если c1 > 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

возвращает отрицательное число, ноль или положительное число в зависимости от отношения между

. В отличие от strcmp, функция

ciCharCompare

перед сравнением преобразует оба параметра к нижнему регистру. Именно так и достигается игнорирование регистра символов при сравнении.

Параметр и возвращаемое значение функции

tolower

, как и у многих функций

<cctype.h>

, относятся к типу

int

, но эти числа (кроме

EOF

) должны представляться в виде

unsigned char

. В C и C++ тип

char

может быть как знаковым, так и беззнаковым (в зависимости от реализации). Если тип

char

является знаковым, гарантировать его возможное представление в виде

unsigned char

можно лишь одним способом: преобразованием типа перед вызовом

tolower

, этим и объясняется присутствие преобразований в приведенном выше фрагменте (в реализациях с беззнаковым типом

char

преобразование игнорируется). Кроме того, это объясняет сохранение возвращаемого значения

tolower

в переменной типа

int

вместо

char

При наличии

chCharCompare

первая из двух функций сравнения строк (с интерфейсом в стиле

strcmp

) пишется просто. Эта функция,

ciStringCompare

, возвращает отрицательное число, ноль или положительное число в зависимости от отношения между сравниваемыми строками. Функция основана на алгоритме

mismatch

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

Но для вызова

mismatch

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

ciStringCompareImpl

, а функция

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; // либо s1 и 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

, C++ преобразует возвращаемое значение

ciCharCompare

к типу

bool

, а в этом типе нулю соответствует

значение

false — результат прямо противоположен тому, что требовалось! Аналогично, когда

ciCharCompare

возвращает 1 или -1, результат будет интерпретирован как

true

, поскольку в языке C все целые числа, отличные от нуля, считаются истинными логическими величинами. Чтобы исправить эту семантическую «смену знака», мы ставим

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)); // вместо функции может