используется функция std:: use_facet[6]. Фасет ctype отвечает за классификацию символов, в том числе и преобразования типа. Если c1 и с2 относятся к типу char, следующий фрагмент сравнивает их без учета регистра по правилам локального контекста L.
const std::ctype<char>& ct = std::use_facet<std::ctype<char> > (L);
bool result = ct-toupper(cl)<ct.toupper(c2);
Предусмотрена особая сокращенная запись: std:: toupper (с, L), эквивалентная
std::use_facet<std::ctype<char> >(L).toupper(c)
Использование use_facet стоит свести к минимуму, поскольку оно связано с заметными затратами.
По аналогии с тем, как лексикографическое сравнение оказывается неподходящим в некоторых ситуациях, преобразования символов «один-в-один» тоже годятся не всегда (например, в немецком языке символ (3 нижнего регистра соответствует последовательности «SS» в верхнем регистре). К сожалению, средства преобразования регистра в стандартных библиотеках С и С++ работают только с отдельными символами. Если это ограничение вас не устраивает, решение со стандартными библиотеками отпадает.
Фасет collate
Если вы знакомы с локальными контекстами С++, возможно, вам уже пришел в голову другой способ сравнения строк. У фасета collate, предназначенного для инкапсуляции технических аспектов сортировки, имеется функция, по интерфейсу весьма близкая к библиотечной функции С strcmp. Существует даже специальное средство, упрощающее сравнение двух строк: для объекта локального контекста L строки х и у могут сравниваться простой записью L(x,y), что позволяет обойтись без хлопот, связанных с вызовом use_facet и функции collate.
«Классический» локальный контекст содержит фасет collate, который выполняет лексикографическое сравнение по аналогии с функцией operator< контейнера string, но другие локальные контексты выполняют сравнение, руководствуясь своими критериями. Если в системе существует локальный контекст, обеспечивающий сравнение строк без учета регистра для интересующих вас языков, воспользуйтесь им. Возможно, этот локальный контекст даже не будет ограничиваться простым сравнением отдельных символов!
К сожалению, какой бы справедливой ни была эта рекомендация, она никак не поможет тем, у кого нет таких локальных контекстов. Возможно, когда-нибудь в будущем стандартное множество таких локальных контекстов будет стандартизировано, но сейчас никаких стандартов не существует. Если функция сравнения без учета регистра для вашей системы еще не написана, вам придется сделать это самостоятельно.
Сравнение строк без учета регистра
Фасет ctype позволяет относительно легко организовать сравнение строк без учета регистра на основе сравнения отдельных символов. Приведенная ниже версия не оптимальна, но по крайней мере она верна. В ней используется практически тот же принцип, что и прежде: строки сравниваются алгоритмом lexicographical_ compare, а отдельные символы сравниваются после приведения к верхнему регистру. Впрочем, на этот раз вместо глобальной переменной используется объект локального контекста. Кстати говоря, сравнение после приведения обоих символов к верхнему регистру не всегда дает тот же результат, что и после приведения к нижнему регистру. Например, во французском языке в символах верхнего регистра принято опускать диакритические знаки, вследствие чего вызов toupper во французском локальном контексте может приводить к потере информации: символы 'ё' и 'е' преобразуются в один символ верхнего регистра 'Е'. В этом случае при сравнении на базе функции toupper символы 'ё' и 'е' будут считаться одинаковыми, а при сравнении на базе tolower они будут считаться разными. Какой из ответов правилен? Вероятно, второй, но на самом деле все зависит от языка, национальных обычаев и специфики приложения.
struct lt_str_l
:public std::binary_function<std::string.std::string.bool>{
struct lt_char{
const std::ctype<char>& ct:
lt_char(const std::ctype<char>& c):ct(c) {}
bool operator() (char x. char y) const {
return ct.toupper(x)<ct.toupper(y);
}
};
std::locale loc;
const std::ctype<char>& ct;
lt_str_l(const std::locale& L = std::locale::classic())
:loc(L),ct(std::use_facet<std::ctype<char> >(loc)) {}
bool operator()(const std::string& x, const std::string& y) const {
return std::lexicographical_compare(x.begin(),.x.end(),
y.begin(),y.end(), lt_char(ct));
}
};
Данное решение не оптимально; оно работает медленнее, чем могло бы работать. Проблема чисто техническая: функция toupper вызывается в цикле, а Стандарт С++ требует, чтобы эта функция была виртуальной. Некоторые оптимизаторы выводят вызов виртуальной функции из цикла, но чаще этого не происходит. Циклические вызовы виртуальных функций нежелательны.
В данном случае тривиального решения не существует. Возникает соблазнительная мысль — воспользоваться одной из функций объекта ctype:
const char* ctype<char>::toupper(char* f, char* i) const
Эта функция изменяет регистр символов в интервале [f,i]. К сожалению, для наших целей этот интерфейс не подходит. Чтобы воспользоваться этой функцией для сравнения двух строк, необходимо скопировать обе строки в буферы и затем преобразовать их содержимое к верхнему регистру. Но откуда возьмутся эти буферы? Они не могут быть массивами фиксированного размера (неизвестно, каким должен быть максимальный размер), а динамические массивы потребуют дорогостоящего выделения памяти.
Альтернативное решение заключается в однократном преобразовании каждого символа с кэшированием результата. Такое решение недостаточно универсально—в частности, при использовании 32-разрядных символов UCS-4 оно абсолютно неработоспособно. С другой стороны, при работе с типом char (8-разрядным в большинстве систем) идея хранения 256 байт дополнительных данных в объекте функции сравнения выглядит вполне реально.
struct lt_str_2:
public std::binary_function<std::string.std::string.bool>{
struct lt_char{
const char* tab;
lt_char(const char* t):tab(t) {}
bool operator() (char x, char y) const {
return tab[x-CHAR_MIN] < tab[y-CHAR-MIN];
}
};
char tab[CHAR_MAX-CHAR_MIN+l];
lt_str_2(const std::locale& L = std:.-locale::classic()){
const std::ctype<char>& ct = std::use_facet<std::ctype<char> >(L);
for(int i = CHAR_MIN;i<=CHAR_MAX;++i) tab[i-CHAR_MIN]=(char)i;
ct.toupper(tab. tab+(CHAR_MAX-CHAR_MIN+1));
}
bool operator()(const std::string& x. const std::string& y) const {
return std::lexicographical_compare(x.begin(),x.end(),
y.begin(),y.end(), lt_char(tab));
}
}
Как видите, различия между lt_str_1 и lt_str_2 не так уж велики. В первом случае используется объект функции сравнения символов, использующий фасет ctype напрямую, а во втором случае — объект функции сравнения с таблицей заранее вычисленных преобразований символов к верхнему регистру. Второе решение уступает первому, если создать объект функции lt_str_2, воспользоваться им для сравнения нескольких коротких строк и затем уничтожить. С другой стороны, при обработке больших объемов данных lt_str_2 работает значительно быстрее lt_str_1. В моих тестах превосходство было более чем двукратным: при использовании lt_str_l сортировка списка из 23 791 слова заняла 0,86 секунды, а при использовании lt_str_2 понадобилось только 0,4 секунды.
Итак, что же мы узнали?
•Класс строки без учета регистра символов реализуется на неправильном уровне абстракции. Обобщенные алгоритмы стандартной библиотеки С++ параметризуются, и этот факт следует использовать.
•Лексикографическое сравнение строк осуществляется сравнением отдельных символов. Если у вас имеется объект функции, сравнивающий символы без учета регистра, задача фактически решена, а этот объект может использоваться для сравнения других типов последовательностей символов, таких как vector<char>, строковые таблицы или обычные строки С.
•Задача сравнения строк без учета регистра сложнее, чем кажется на первый взгляд. Она имеет смысл лишь в конкретном локальном контексте, поэтому объект функции сравнения должен содержать информацию о текущем локальном контексте. Если сравнение должно быть оптимизировано по скорости, напишите объект функции таким образом, чтобы избежать многократного вызова дорогостоящих операций с фасетами.
