При наличии 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
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(c1))< // объясняется, почему
tolower(static_cast(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
, приведенный выше фрагмент понятен без объяснений, а если не знаете — это легко поправимо.
Читать дальше