Эта функция изменяет регистр символов в интервале [f, i]. К сожалению, для наших целей этот интерфейс не подходит. Чтобы воспользоваться этой функцией для сравнения двух строк, необходимо скопировать обе строки в буферы и затем преобразовать их содержимое к верхнему регистру. Но откуда возьмутся эти буферы? Они не могут быть массивами фиксированного размера (неизвестно, каким должен быть максимальный размер), а динамические массивы потребуют дорогостоящего выделения памяти.
Альтернативное решение заключается в однократном преобразовании каждого символа с кэшированием результата. Такое решение недостаточно универсально — в частности, при использовании 32-разрядных символов UCS-4 оно абсолютно неработоспособно. С другой стороны, при работе с типом char (8-разрядным в большинстве систем) идея хранения 256 байт дополнительных данных в объекте функции сравнения выглядит вполне реально.
struct lt_str_2:
public std::binary_function
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+1];
lt_str_2(const std::locale& L = std::locale::classic) {
const std::ctype
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_1 сортировка списка из 23 791 слова заняла 0,86 секунды, а при использовании lt_str_2 понадобилось только 0,4 секунды.
Итак, что же мы узнали?
• Класс строки без учета регистра символов реализуется на неправильном уровне абстракции. Обобщенные алгоритмы стандартной библиотеки C++ параметризуются, и этот факт следует использовать.
• Лексикографическое сравнение строк осуществляется сравнением отдельных символов. Если у вас имеется объект функции, сравнивающий символы без учета регистра, задача фактически решена, а этот объект может использоваться для сравнения других типов последовательностей символов, таких как vector, строковые таблицы или обычные строки C.
• Задача сравнения строк без учета регистра сложнее, чем кажется на первый взгляд. Она имеет смысл лишь в конкретном локальном контексте, поэтому объект функции сравнения должен содержать информацию о текущем локальном контексте. Если сравнение должно быть оптимизировано по скорости, напишите объект функции таким образом, чтобы избежать многократного вызова дорогостоящих операций с фасетами.
Правильное сравнение строк без учета символов требует большого объема рутинной работы, но ее необходимо проделать только один раз. Или вам, как и большинству коллег, не хочется думать о локальных контекстах? Впрочем, лет десять назад никому не хотелось думать об «ошибке 2000 года». И все же у вас больше шансов обойти стороной эту проблему, если ваш локально-зависимый код будет с самого начала правильно работать.
В начале книги я ввел термин «платформа STL», означающий комбинацию конкретного компилятора и конкретной реализации STL. Различие между компилятором и библиотекой особенно важно при использовании компилятора Microsoft Visual C++ версий 6 и ниже (то есть компилятора, входившего в комплект поставки Microsoft Visual Studio версий 6 и ниже), поскольку компилятор иногда способен на большее, чем прилагаемая реализация STL. В настоящем приложении описаны важные недостатки старых платформ STL от Microsoft и предложены обходные решения, делающие работу на этих платформах значительно более удобной.
