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

Мейерс Скотт

Ошибки и опечатки

• Список ошибок и опечаток в книге «Effective C++»: http://www.aristeia.com/BookErrata/ec++2e-errata.html.

[28] Список ошибок и опечаток в книге «More Effective C++»: http://www.aristeia.com/BookErrata/mec++-errata.html.

• Список ошибок и опечаток на компакт-диске «Effective C++»:aristeia.com/BookErrata/cd1e-errata.html.

[29] Обновления «More Effective C++», относящиеся к

auto_ptr

: http://www.awl.com/cseng/titles/0-201-63371-X/auto_ptr.html.

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

В совете 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] , прост,

компактен и не содержит информации состояния. Как будет показано ниже, правильная реализация сравнений без учета регистра не отвечает ни одному из этих критериев.

5

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

• Этого вообще не достаточно. Даже если все функции

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

достаточно объединить этот алгоритм с объектом функции, игнорирующим различия в регистре символов.