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

Локальные контексты

В совете 35 приведена реализация сравнения строк без учета регистра символов с применением алгоритмов mismatch и lexicographical_compare, но в нем также указано, что полноценное решение должно учитывать локальный контекст. Книга посвящена STL, а не вопросам интернационализации, поэтому локальным контекстам в ней не нашлось места. Тем не менее, Мэтт Остерн, автор книги «Generic Programming and the STL» [4], посвятил этой теме статью в майском номере журнала «C++ Report» [11]. Текст этой статьи приведен в настоящем приложении. Я благодарен Мэтту и фирме 101communications за то, что они разрешили мне это сделать.

Сравнение строк без учета регистра символов

Мэтт Остерн

Если вам когда-либо доводилось писать программы, в которых используются строки (а кому, спрашивается, не доводилось?), скорее всего, вы встречались с типичной ситуацией — две строки, различающиеся только регистром символов, должны были интерпретироваться как равные. В этих случаях требовалось, чтобы операции сравнения — проверка равенства, больше-меньше, выделение подстрок, сортировка — игнорировали регистр символов. Программисты очень часто спрашивают, как организовать подобные операции средствами стандартной библиотеки C++. На этот вопрос существует огромное количество ответов, многие из которых неверны.

Прежде всего необходимо избавиться от мысли о написании класса, сравнивающего строки без учета регистра. Да, с технической точки зрения это более или менее возможно. Тип std::string стандартной библиотеки в действительности является синонимом для типа std::basic_string<char, std::char_trais<char>, std::allocator<char> >. Операции сравнения определяются вторым параметром; передавая второй параметр с переопределенными операциями «равно» и «меньше», можно специализировать basic_string таким образом, что операции < и = будут игнорировать регистр символов. Такое решение возможно, но игра не стоит свеч.

• Вы не сможете выполнять операции ввода-вывода или это потребует больших дополнительных хлопот. Классы ввода-вывода стандартной библиотеки (такие как std::basic_istream и std::basic_ostream) специализируются по двум начальным параметрам std::basic_string (а std::ostream всего лишь является синонимом для std::basic_ostream<char, char_traits<char> >). Параметры характеристик (traits) должны совпадать. Если вы используете строки типа std::basic_string<char, my_traits_class>, то для вывода строк должен использоваться тип std::basic_ostream<char, my_traits_class>. Стандартные потоки cin и cout для этой цели не подойдут.

• Игнорирование регистра символов является не свойством объекта, а лишь контекстом его использования. Вполне возможно, что в одном контексте строки должны интерпретироваться с учетом регистра, а в другом контексте регистр должен игнорироваться (например, при установке соответствующего режима пользователем).

• Решение не соответствует канонам. Класс char_traits, как и все классы характеристик[5], прост, компактен и не содержит информации состояния. Как будет показано ниже, правильная реализация сравнений без учета регистра не отвечает ни одному из этих критериев.

• Этого вообще не достаточно. Даже если все функции basic_string будут игнорировать регистр, это никак не отразится на использовании внешних обобщенных алгоритмов, таких как std::search и std::find_end. Кроме того, такое решение перестает работать, если по соображениям эффективности перейти от контейнера объектов basic_string к таблице строк.

Более правильное решение, которое лучше соответствует архитектуре стандартной библиотеки, заключается в том, чтобы игнорировать регистр символов только в тех случаях, когда это действительно необходимо. Не стоит возиться с такими функциями контейнера string, как string::find_first или string::rfind; они лишь дублируют функциональные возможности, уже поддерживаемые внешними обобщенными алгоритмами. С другой стороны, алгоритмы обладают достаточной гибкостью, что позволяет реализовать в них поддержку сравнений строк без учета регистра. Например, чтобы отсортировать коллекцию строк без учета регистра, достаточно передать алгоритму працильный объект функции сравнения:

std::sort(C.begin(), C.end().compare_without_case);

Написанию таких объектов и посвящена эта статья.

Первая попытка

Существует несколько способов упорядочения слов по алфавиту. Зайдите в книжный магазин и посмотрите, как расставлены книги на полках. Предшествует ли имя

1. См. статью Александреску А. (Andrei Alexandrescu) в майском номере «C++ Report» за 2000 г. [19].

Mary McCarthy имени Bernard Malamud или следует после него? (В действительности это лишь вопрос привычки, я встречал оба варианта.) Впрочем, простейший способ сравнения строк хорошо знаком нам по школе: речь идет о лексикографическом, или «словарном», сравнении, основанном на последовательном сравнений отдельных символов двух строк.

Лексикографический критерий сравнения может оказаться неподходящим для некоторых специфических ситуаций. Более того, единого критерия вообще не существует — например, имена людей и географические названия иногда сортируются по разным критериям. С другой стороны, в большинстве случаев лексикографический критерий подходит, поэтому он был заложен в основу механизма строковых сравнений в C++. Строка представляет собой последовательность символов. Если объекты x и y относятся к типу std::string, то выражение x<y эквивалентно выражению

std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end())

В приведенном выражении алгоритм lexicographical_compare сравнивает отдельные символы оператором <, однако существует другая версия lexicographical_compare, позволяющая задать пользовательский критерий сравнения символов. Она вызывается с пятью аргументами вместо четырех; в последнем аргументе передается объект функции, двоичный предикат, определяющий, какой из двух символов предшествует другому. Таким образом, для сравнения строк без учета регистра на базе lexicographical_compare достаточно объединить этот алгоритм с объектом функции, игнорирующим различия в регистре символов.

Распространенный принцип сравнения двух символов без учета регистра заключается в том, чтобы преобразовать оба символа к верхнему регистру и сравнить результаты. Ниже приведена тривиальная формулировка этой идеи в виде объекта функции C++ с использованием хорошо известной функции toupper из стандартной библиотеки C:

struct lt_nocase:

 public std::binary_function<char, char, bool> {

 bool operator()(char x, char y) const {

  return std::toupper(static_cast<unsigned char>(x))<

   std::toupper(static_cast<unsigned char>(y));

 }

};

«У каждой сложной задачи есть решение простое, элегантное и… неправильное». Авторы книг C++ обожают этот класс за простоту и наглядность. Я тоже неоднократно использовал его в своих книгах. Он почти правилен, и все-таки не совсем, хотя недостаток весьма нетривиален. Следующий пример выявляет этот недостаток:

int main() {

 const char* s1 = "GEW334RZTRAMINER";

 const char* s2 = "gew374rztraminer";

 printf("s1=%s, s2=%sn", s1, s2);

 printf("s1<s2:%sn",

  std::lexicographical_compare(s1, s1+14, s2, s2+14, lt_nocase())

  ?"true":"false");

}

Попробуйте запустить эту программу в своей системе. На моем компьютере (Silicon Graphics О2 с системой IRIX 6.5) результат выглядел так:

s1=GEWÜRZTRAMINER,s2=gewürztraminer

s1<s2:true

Странно… Разве при сравнении без учета регистра «GEWÜRZTRAMINER» и «gewürztraminer» не должны быть равными? И еще возможен вариант с небольшой модификацией: если перед командой printf вставить строку

setlocale(LC_ALL, "de");

результат неожиданно изменяется:

s1=GEWÜRZTRAMINER,s2=gewürztraminer

s1<s2:false

Задача сравнения строк без учета регистра сложнее, чем кажется сначала. Работа элементарной на первый взгляд программы в огромной степени зависит от того, о чем многие из нас предпочли бы забыть. Речь идет о локальном контексте.

Локальный контекст

Символьный тип char в действительности представляется самым обычным целым числом. Это число можно интерпретировать как символ, но такая интерпретация ни в коем случае не является универсальной. Что должно соответствовать конкретному числу — буква, знак препинания, непечатаемый управляющий символ?

На этот вопрос невозможно дать однозначный ответ. Более того, с точки зрения базовых языков C и C++ различия между этими категориями символов не так уж существенны и проявляются лишь в некоторых библиотечных функциях: например, функция isalpha проверяет, является ли символ буквой, а функция toupper переводит символы нижнего регистра в верхний регистр и оставляет без изменений буквы верхнего регистра и символы, не являющиеся буквами. Подобная классификация символов определяется особенностями культурной и лингвистической среды. В английском языке действуют одни правила, по которым буквенные символы отличаются от «не буквенных», в шведском — другие и т. д. Преобразование из нижнего регистра в верхний имеет один смысл в латинском алфавите, другой — в кириллице, и вообще не имеет смысла в иврите.